All Questions
Tagged with combinatorics algorithms
118
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.8k
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