All Questions
Tagged with combinatorics algorithms
1,045
questions
1
vote
0
answers
45
views
Counting the deduplicated list
You are given $2n$ positive integers $x_i, d_i$ ($1 \leq i \leq n$). Let $l := [x_1, 2x_1, ..., d_1x_1, x_2, 2x_2, ..., d_2x_2, ..., x_n, 2x_n, ..., d_nx_n]$. Let $s = set(l)$, i.e., the set by ...
- 1,008
0
votes
1
answer
224
views
Algorithm to compute number of combinations
I have to compute (m+n)!/(m!)(n!) where m>=n.
Due to overflow constraints, I cannot calculate (m+n)! as it might exceed size of variable (int). To overcome this difficulty, one solution is to do ...
- 345
3
votes
1
answer
80
views
Block Game: Dynamic vs Greedy approach
This is a question from an old exam in a Combinatorial Algorithms class, I am reviewing for a midterm. I understand the game but I don't understand the "optimal" approach, ie. implementing a ...
- 31
5
votes
0
answers
56
views
Bracelet isomorphism algorithms
I feel like the problem should have been studied, but I wasn't able to find anything precise.
Given two bracelets with $n$ beads and $m$ colors, given that the multiplicity of each color is the same, ...
- 2,103
0
votes
0
answers
46
views
Colored hypercubes isomorphism
I would like to extend the method to verify isomorphism between cubes with colored faces in this answer to $4$-cubes (tesseracts) with colored faces ($2$-faces), allowing rotations and reflections, ...
- 2,103
2
votes
2
answers
110
views
Counting integers $n \leq x$ such that $rad(n)=r$
Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-...
- 1,022
1
vote
2
answers
105
views
Bin packing with load fairness across the bins
The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description:
My question is :...
- 131
3
votes
0
answers
99
views
What set of angles uniquely defines a convex quadrilateral?
I am trying to characterize the set of angles in a (convex) quadrilateral that distinguishes it from any other quadrilateral that is not similar to it. Such a set will be said to uniquely define a ...
- 1,022
1
vote
0
answers
73
views
How to quickly eyeball maximum sum subarray?
Given an integer array, I want to find the continuous subarray (containing at least one number) which has the largest sum. There are some algorithmic solutions to this here: https://en.wikipedia.org/...
- 1,415
1
vote
2
answers
66
views
Finding perfect matchings
Given a connected graph $G$, do you have an idea how to calculate the amount of perfect matchings
this graph has (given at least one exists)? I dont worry about the calculation being efficient in any ...
- 13
0
votes
0
answers
277
views
Count the integers that conform another integer
I have to count all the integers than conform to integer A.
We say that integer B conforms to integer A if, in all positions where A has bits set to 1, B has corresponding bits set to 1.
If I have a ...
- 378
1
vote
0
answers
61
views
Counting number of length k non-overlapping paths on an $n \times n$ grid
Suppose we have a square grid of size $n \times n$, where each node is connected to its immediate neighbors (up, down, left, right, and the four diagonals when they exist). I'd like to count all of ...
3
votes
2
answers
87
views
Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards
I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly.
However, I know that some people cannot have some cards due to the rules of the card game.
...
- 2,305
0
votes
0
answers
68
views
Finding the general formula for the last standing soldier
Suppose there are 'n' soldiers standing in a circle who have decided to kill each other (just because they don't want to surrender to the opposition).
Lets say they are denoted from a1 to an in the ...
- 1
0
votes
0
answers
109
views
Binary sequences of length $N$ including all numbers upto $N$ [duplicate]
Consider numbers $n$ and $N = 2^n$ and define a binary sequence $b = [b_0,\dots,b_{N-1}]$, $b_i \in \{0,1\}$, to be complete or to include all numbers upto $N$ when for each number $0 \leq i < N$ ...
- 18.2k
-1
votes
1
answer
59
views
Is there an efficient way to loop through this problem? [closed]
So I saw this very interesting problem. Let's say you have a length of 2, and a base length of 5
l = 2, b = 5
this would be translated to :
...
- 9
1
vote
1
answer
62
views
How to discover a recursive relation in a data set?
For a set of data, $x(n)$, where $n = 1, 2, 3, ...$, we know there are some kind of recursive relations among those data, $x(n)$ somehow depends on previous data $x(n-1), x(n-2), ...x(1)$, but we do ...
- 553
0
votes
4
answers
195
views
Get all the methods to break 100% into certain number of parts?
Being straight about the question, for a program I'm writing, I need to divide 100% into 5 parts. In my program, percentages incremented/decremented by 10%. So I can express my requirement in the ...
- 103
2
votes
1
answer
57
views
Computing subset reciprocals, $\frac1{a+b}+\frac1{a+c}+\frac1{b+c}$
I'm interested in computing the sum
$$
H_k = \sum_{S\subseteq T, |S|=k} \frac{1}{\sum_{s\in S} s},
$$
where $T$ is some set of integers.
Obviously this can be done in $|T|^k$ time, enumerating all ...
- 4,854
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,520
0
votes
1
answer
266
views
Algorithm verification: Get all the combinations of possible words
I wanted to know if the algorithm that i wrotte just below in python is correct.
My goal is to find an algorithm that print/find all the possible combinaison of words that can be done using the ...
- 805
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