All Questions
Tagged with combinatorics algorithms
1,044
questions
1
vote
0
answers
78
views
+50
Calculation of special subsets in high-dimensional binary matrices
I need to solve a rather specific problem related to binary matrices. The task is to count the number of specific "combinations", where "combination" means the following:
this is ...
0
votes
0
answers
34
views
How to permute the rows and cols of a matrix to maximize the set of pivots?
Given an $m\times n$ matrix $A$, how can I find permutations $\sigma,\tau$, such that for the matrix $B=A[\sigma,\tau]$ with shuffled columns and rows, the number of nonzero entries that have zeros ...
0
votes
0
answers
16
views
Counting cliques in polynomial time
Let $G$ be a disconnected graph such that every connected component is a $k$-clique, $k \geq 2$. That is, a connected component of $G$ can be a single edge, or a triangle, or a $K_4$ and so on. Is it ...
11
votes
0
answers
165
views
What is the current best algorithm to find if a simply connected region is uniquely tileable with dominoes?
I was reading both Thurston's and Fournier's papers on algorithms which detect whether or not a simply connected region is tileable using dominoes (1 by 2 rectangles) when I came across the section in ...
2
votes
0
answers
48
views
Dividing $N$ coins into at most $K$ groups such that I can get any number of coins by selecting whole groups
Problem
Inspired from Dividing $100$ coins into $7$ groups such that I can choose any number of coins by selecting whole groups . I am interested in the number of possible ways we can get such a split....
1
vote
0
answers
27
views
Knapsack with fixed number of bins?
Constant: d, a fixed number of bins/sacks
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
1
vote
1
answer
33
views
Testing for strong homomorphism in polynomial time
Let $G$ and $H$ be graphs. We say that a map $f:V(G)\rightarrow V(H)$ is a strong homomorphism if for all $u,v\in V(G)$ it holds that $(u,v)\in E(G)$ if, and only if, $(f(u),f(g))\in E(H)$.
Fix $H$ ...
0
votes
0
answers
35
views
Minimum number of measurements required to find heaviest and lightest from a group of idetntical looking balls having distinct weights.
You are given 68 identical looking balls, each with a distinct weight. You are given a common balance using which you can compare weights of any two pair of balls with a single measurement. Describe ...
2
votes
0
answers
45
views
Does every collection of edges between two sets of vertices in a plane have a "perimeter" edge suitable for induction inwards?
Joel Hamkins posted this nice problem: https://x.com/JDHamkins/status/1790582025977577591
I quote:
Suppose you have 1000 white points and 1000 black points in the plane, no three collinear. Can you ...
3
votes
1
answer
161
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
1
vote
0
answers
87
views
Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
1
vote
1
answer
44
views
find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom
here is the full question:
Use inclusion/exclusion to find the number of ways of distributing 30
students into six classrooms assuming that each classroom has a maximum capacity
of six students.
Let $...
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
1
vote
1
answer
74
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
0
votes
1
answer
56
views
Reordering algorithm to fragment consecutive sequences of ones as much as possible
Recently, I came across the following problem:
Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$.
We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$.
We call a &...