All Questions
Tagged with combinatorics algorithms
1,044
questions
0
votes
0
answers
28
views
Ordering of points based on their relative positions (limited info incl. errors)
I am currently working on a problem which I assume mathematicians have already solved.
Setup: I have $N$ people standing in a line. Each of them is assigned with a different number between $1$ to $N$. ...
0
votes
0
answers
67
views
How to arrange $N$ values into $M$ buckets with fixed sum?
I am looking for an algorithm or method that can help me solve the following problem:
Given $N$ integers and $M$ buckets with a sum label
How do I arrange the $N$ numbers so that each bucket has the ...
- 131
1
vote
0
answers
42
views
Algorithm to compute monomial coefficients from Vieta's Formulas
Let's say I know the $N$ roots $\boldsymbol r$ of a polynomial $p_N(x)$ and I want to compute the coefficients $\boldsymbol \alpha $ of the representation in monomials, i.e.,
$$p_N(x) = \sum_{j=0}^N \...
- 2,274
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
0
votes
2
answers
576
views
Algorithm to derive possible combinations of a set e.g., $A = [1, 2, 3, 4]$ and $k = 3$ and $L = [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]$
Given a set of numbers A and an integer k, I want to derive a list of sets L such that all the sets in L are the distinct combinations of the elements in A picking k at a time.
For example: $A = \{1, ...
- 113
0
votes
1
answer
99
views
What is the name of this variant of n choose k but with multiple subsets to pick?
$n$ choose $k$ can be seen as permuting a binary string with $k$ of the digits set to $1$, and $n - k$ of them to $0$. For example if the string is length $n=6$ and $k=3$, one permutation would be:
$$...
- 127
1
vote
2
answers
1k
views
Efficiently distributing $N$ items in $M$ buckets
There are $d$ buckets, each one with capacity $[0,g]$. A quota of identical items $l\in \mathbb{N} $ is uniformly drawn from $[0,g\cdot d]$ and the items have to be distributed among buckets randomly. ...
- 15
2
votes
0
answers
104
views
Number of three-tuples such that $c_1a_1 + c_2a_2 + c_3a_3 = n$ and $c_1 \ge c_2 \ge c_3$
I'm trying to figure out how to find the number of three tuples that sum up to $n$ when each element has a weight of $c_i$. In other words, how many combinations are there of $(a_1, a_2, a_3)$ such ...
- 141
3
votes
2
answers
1k
views
Why do greedy coloring algorithms mess up?
It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
- 731
0
votes
1
answer
89
views
$S$ is the set of words generated by an alphabet. $A\subset S$ , $x\in S$. How to find if $x$ is generated by concatenating elements of $A$? [closed]
I am looking for references in relation to this problem. The name of the problem, texts or papers, efficient algorithms, and calculators.
Example:
$S$= the set of all finite binary strings, $A$= a ...
- 3,702
1
vote
1
answer
55
views
Create no back to back sequence from frequencies.
Given the array of frequencies, say $A = \{a_1,a_2, \dots, a_n\}$, $0 < a_i \in \mathbb{N}$.
We can create sequence which contains numbers from $1$ to $n$ such that each number's $i$ appears $a_i$ ...
- 7,316
1
vote
0
answers
54
views
Given a connected graph $G = (V, E)$, give a polynomial time algorithm that finds the set $U \subseteq V$ with the smallest boundary
So I asked something related to this a bit, but I don't think this is a duplicate in that I am providing a different version of the problem that is more generic and more easily accessible without ...
- 91
1
vote
0
answers
68
views
Polynomial time algorithm to compute minimum distance of a linear code
For general (even binary I believe) linear codes, computing the minimum distance $\min_{d \in C} \Delta(d, 0)$ is NP-complete. However, there is a special case where a polytime algorithm is possible:
...
- 91
0
votes
1
answer
50
views
Checking NP-completeness of the following problem(s)- Assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. Suppose each department $d$ is considering hiring some $C_d \subseteq \{1, 2, ... n\}$ candidates (...
- 1
2
votes
1
answer
281
views
An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 922
0
votes
1
answer
1k
views
Probability of getting 2 Consecutive heads in N throws.
We have to Find a Probability of Getting ${2}$ consecutive Heads in ${N}$ throws Given that $N^{th}$ throw will always be Head.
For Example:- N = 3,
Possible Conditions = HHH, HTH, THH, TTH = 4 ...
- 5
1
vote
0
answers
49
views
An efficiently computable infinite binary sequence satisfying a stronger disjunctiveness property
Given a natural number $n > 1$ and an infinite binary sequence $B = b_0b_1b_2b_3\ldots$ (here $b_i$ denotes an $i$-th element of $B$), let $f_n(B)$ denote the following tuple of infinite binary ...
- 922
1
vote
1
answer
94
views
Repainting of chessboard with restrictions
Assume an $8\times 8$ chessboard with the usual coloring. You may
repaint all squares (a) of a row or column (b) of a $2\times 2$
square. The goal is to attain one black square. Can you reach the
...
- 17k
0
votes
0
answers
32
views
Polynomial time "fairness" algorithm that assigns leaders for $m$ tasks amongst $n$ workers.
Suppose we have $n$ workers and $m$ tasks. Suppose each task has a workforce $S_i \subseteq \{1, 2, .., n\}$. Note that $S_i \cap S_j \neq \emptyset$ is possible (and expected).
Given this ...
- 11
2
votes
1
answer
71
views
Counting bijections of a certain type between points and lines of a finite projective plane
Consider a set $P$ of points and a set $B$ of subsets of $P$ called lines. A Projective plane is an ordered pair $(P,B)$ satisfying:
There is a unique line joining any two points.
Any two lines ...
- 4,432
0
votes
1
answer
55
views
Algorithm for finding maximal "reduction" of an integer matrix
Given a $m\times n$ matrix of non-negative integers. A "reduction" of this matrix can be done on one row/column of this matrix, by subtracting the minimum of the row/column from all other ...
- 96
0
votes
3
answers
59
views
Proof of $\exists n_0: k^n\leq n!\quad \forall n\geq n_0$
Makes total sense to me intuitively, and it's easy to check for any specific $k$, for example $k=2$:
$2^3 = 8,\quad3! = 6 \quad $ and $\quad 2^4=16, \quad 4! = 24$
$\Rightarrow2^n\leq n! \quad \forall ...
- 342
1
vote
1
answer
73
views
Randomized triangle-freeness testing algorithm.
I'm asked to use the following lemma to prove the statement below.
Theorem 1.1.1 (Triangle Removal Lemma). For every $\gamma>0$ there exists $\delta=\delta(\gamma)>0$ such that for every graph $...
- 2,307
1
vote
1
answer
257
views
Generating functions in combinatorics topic: Pascal triangle for bivariate function
Let $\displaystyle \left[\frac{n}{k}\right]$ a combinatorial element meaning the number of permutations with exactly $k$ increasing sequences. Find a Pascal Triangle type recurence formula for the ...
0
votes
1
answer
250
views
How to find the average pairwise distance in G for a "flower" graph
I need to know how to compute the sum of the distances between all pairs of “pedal” nodes of the flower graph. And the sum of the distances between all pairs of “stalk” nodes
I know that the average ...
5
votes
0
answers
203
views
Topological Minors on Simple Graphs --- Antichains?
This is a follow-up discussion on @296991, with further questions.
In the following discussion, "graphs" are finite but not necessarily simple (i.e. $|V(G)|<\infty,$ but allow loops and ...
- 51
2
votes
1
answer
148
views
Reaching the grid graph from a planar graph using graph transformations
Consider a $5$-regular undirected planar graph with $n$ vertices (a $k$-regular graph has exactly $k$ edges emanating from every node.)
Let us say we apply an arbitrary sequence (of length $\text{poly}...
- 135
3
votes
1
answer
48
views
Random seat assignments probability/algorithms question
Suppose there are $M$ seats and $N \leq M/2$ people for those seats.
The seats are assigned as follows:
Each person generates uniformly a random permutation of the $M$ seats. When it is their turn ...
- 31
0
votes
1
answer
53
views
Optimal Card Game Schedule
I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen...
Let $n,g,s \in \mathbb{N+}$ where $s \leq n$.
Let $P = \{1, 2, ...
- 213
2
votes
0
answers
63
views
A (simple?) optimization question
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be vectors in $\mathbb{R}^n$. Let $g$ be an increasing concave function ...
- 578