All Questions
Tagged with combinatorics algorithms
117
questions
9
votes
3
answers
9k
views
How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?
I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.
I've spent quite ...
- 557
2
votes
3
answers
1k
views
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
...
- 242
12
votes
2
answers
13k
views
Efficient computation of the minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
- 303
27
votes
2
answers
3k
views
Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$
More precisely,
$$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$
This is Theorem 4 ...
- 1,727
19
votes
4
answers
9k
views
Algorithm wanted: Enumerate all subsets of a set in order of increasing sums
I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time.
Given a set of ...
- 293
3
votes
4
answers
2k
views
Generate all de Bruijn sequences
There are several methods to generate a de Bruijn sequence. Is there a general algorithm to create all unique (rotations are counted as the same) De Bruijn sequences for a binary alphabet of length $n$...
- 10.9k
1
vote
2
answers
2k
views
Algorithms for mutually orthogonal latin squares - a correct one?
I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a ...
- 141
24
votes
8
answers
42k
views
How do I compute binomial coefficients efficiently?
I'm trying to reproduce Excel's COMBIN function in C#. The number of combinations is as follows, where number = n and number_chosen = k:
$${n \choose k} = \frac{n!}{k! (n-k)!}.$$
I can't use this ...
- 495
7
votes
2
answers
7k
views
Lights Out Variant: Flipping the whole row and column.
So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so:
1 0 0 00 0 0 00 1 0 0 0 0 1 0
When you selected a light (...
- 194
0
votes
1
answer
159
views
Generate some number of lists of pairs given a list of people
Given a list of people:
[
1,
2,
3,
4,
5,
6
]
The goal is to generate some number of lists of pairs.
...
20
votes
3
answers
1k
views
Finding the Robot [closed]
There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
- 827
18
votes
4
answers
7k
views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{...
- 484
17
votes
3
answers
11k
views
Generate Random Latin Squares
I'm looking for algorithms to generate randomized instances of Latin squares.
I found only one paper:
M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. ...
user14947
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
- 757
14
votes
2
answers
8k
views
Complexity of counting the number of triangles of a graph
The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle.
This procedure ...
- 5,032
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
- 419
5
votes
2
answers
3k
views
On counting and generating all $k$-permutations of a multiset
Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.)
...
- 14.5k
4
votes
1
answer
515
views
Collection of subset generating every pairs of elements
I'm looking forward to a construction with the following property:
Given a set S of n elements, find a small/the smallest collection of subsets of S of size k such that for every pair of elements a, ...
- 51
4
votes
1
answer
2k
views
Expected value when die is rolled $N$ times
Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
- 235
3
votes
2
answers
3k
views
Sum of multiplication of all combination of m element from an array of n elements
Suppose I have an array {1, 2, 3, 4} and m = 3.
I need to find:
...
- 31
3
votes
2
answers
754
views
How to calculate the number of possible multiset partitions into N disjoint sets?
I have made a Ruby program, which enumerates the possible multiset partitions, into a given number of disjoint sets (N), also called bins. The bins are indistinguishable. They can be sorted in any ...
- 155
1
vote
1
answer
283
views
Showing there exists a sequence that majorizes another
The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can ...
- 1,418
1
vote
1
answer
2k
views
Making all row sums and column sums non-negative by a sequence of moves
Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always make ...
- 3,914
11
votes
5
answers
12k
views
Secret santa problem
We decided to do secret Santa in our office. And this brought up a whole heap of problems that nobody could think of solutions for - bear with me here.. this is an important problem.
We have 4 people ...
- 221
8
votes
2
answers
2k
views
Minimum transactions to settle debts among friends
You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
- 98
7
votes
4
answers
4k
views
What is the number of full binary trees of height less than $h$
Given a integer $h$
What is $N(h)$ the number of full binary trees of height less than $h$?
For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't find ...
- 13.8k
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k
5
votes
3
answers
5k
views
How many ways to reach $Nth$ number from starting point using any number steps between $1$ to $6$
In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem ...
- 63
5
votes
2
answers
2k
views
Generating a Eulerian circuit of a complete graph with constant memory
(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian ...
- 3,315
4
votes
0
answers
2k
views
