All Questions
Tagged with combinatorics algorithms
1,042
questions
0
votes
0
answers
14
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 ...
- 339
9
votes
0
answers
117
views
+50
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 ...
- 405
2
votes
0
answers
41
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,171
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 ...
- 11
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$ ...
- 823
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 ...
- 9
2
votes
0
answers
44
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 ...
- 9,307
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 ...
- 33
1
vote
0
answers
86
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, ....
- 8,350
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 $...
- 15
0
votes
1
answer
35
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 ...
- 15
1
vote
1
answer
73
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 $...
- 129
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 &...
- 1
0
votes
1
answer
26
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
0
answers
21
views
One to one mapping that maximize the minimum absolute difference
Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that
$$
\max \min_{i} |...
1
vote
1
answer
44
views
Find Number of unique durations that can be created given a list of durations and an upper bound
Lets say we are given a list of durations (5s, 10s, 10s, 15s, 15s, 15s, 25s, 30s....) and we want to find a list of unique durations that can be created using this list of single durations.
for ...
3
votes
2
answers
184
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53
2
votes
1
answer
83
views
On an algorithm for counting triangles
This is regarding the complexity of an algorithm for counting triangles in an undirected graph which was suggested in a document I came across.
(Link - https://www.cs.cmu.edu/~15750/notes/lec1.pdf)
...
- 435
2
votes
1
answer
42
views
Algorithm to calculate a maximal string from a matrix.
I have stumbled upon an interesting question whilst working on my thesis.
You are given a matrix of pairwise distinct integers $A=(a_{i,j})$ with $1\leq i\leq k$ and $1\leq j \leq r$ and a tuple $(b_1,...
- 175
4
votes
3
answers
214
views
Proof for Particular Fair Shuffle Algorithm
I ran multiple simulations of the following function, and it seems to be fair shuffling, given that all permutations were roughly equal, but I don't understand why it works. It's just inserting at ...
- 41
0
votes
0
answers
21
views
Filtering out faulty durations
I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2:...
0
votes
0
answers
30
views
Constructing an 8x8 Table with Unique Row Patterns and Consistent Prefix-Suffix Combinations
I am looking to create an 8x8 table with specific properties related to prefix and suffix combinations. Each cell in the table represents a combination of a prefix (rows) and a suffix (columns), ...
2
votes
0
answers
73
views
Bin packing : item to be packed in a certain bin depend on previously packed items to that bin.
I am working on an engineering problem. I need to implement an algorithm that looks like a certain variant of bin packing. Specifically, in this variant of the bin packing, the size of a certain item ...
- 131
3
votes
0
answers
80
views
A strategy for number-guessing game
Let player A and player B are playing number-guessing game, which is:
Player A draws one natural number $X$ in $1,2,\cdots,N$ at random.
Player B guesses a number $Y$ in $1,2,\cdots, N$.
Player A ...
- 918
15
votes
0
answers
271
views
Recovering a binary function on a lattice by studying its sum along closed paths
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following:
Given an even ...
- 4,323
2
votes
1
answer
46
views
Maximal counterexample for a greedy approach with a non-canonical coin system
Let $1 = c_1 < c_2 < \dots < c_n$ be an integer coin system. This coin system is not necessarily canonical (that is, a greedy algorithm will not necessarily yield the fewest number of coins ...
0
votes
0
answers
48
views
Coin weighting with constraints
Consider the following $(d,k,n)$-coin weighting (with spring scale):
You possess an electronic scale, $n$ coins, and $d$ of them are magnetic. Moreover, you always need to weight at least $k$ coins at ...
- 183
6
votes
0
answers
355
views
Decrease list difference via swaps
There are four lists, each with $100$ numbers in $[0,1]$. You want to perform as few swaps between pairs of numbers as possible, so that the difference between the sums of numbers in any two lists ...
- 83
0
votes
1
answer
69
views
Stats problem, stacking cards [closed]
If I have n cards and n stacks of cards, how many ways can I split the cards between the stacks if the order of the cards in the stack is significant but the order of the stacks is insignificant and ...
0
votes
0
answers
48
views
Optimal Strategy for Identifying Lighter Balls: A Balance Scale Puzzle
There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We ...
