All Questions
Tagged with combinatorics algorithms
1,046
questions
2
votes
0
answers
50
views
How many ways are there to place the ball in N different bags under given condition? [duplicate]
Possible Duplicate:
In how many ways we can put $r$ distinct objects into $n$ baskets?
I have a doubt in following Combinatorics question :
There are N bags, and there several balls of 4 colors ...
- 327
4
votes
1
answer
118
views
Computing binomial symbols modulo m
While procrastinating, I decided to play around with computing binomial symbols modulo $m$, $$\binom{n}{r} \equiv q \pmod{m}, 0 \leq q < m.$$ Using Pascal's formula, I discovered that this may be ...
- 870
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
1
vote
1
answer
159
views
List number of moves to defeat the opponent
Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one (...
- 165
2
votes
0
answers
398
views
Finding the minimum length of an addition chain
It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the ...
- 782
1
vote
1
answer
569
views
A question about Flajolet-Martin algorithm
I am reading this algorithm in these notes for counting the number of distinct items in a stream.
From my understanding, the basic idea is that if such number is big enough, the distance between ...
- 1,511
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
7
votes
1
answer
169
views
Put a mouse to the last cell
We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.
At each step, we can do one of two operations:
$\mathbf{P}$: Put only in the first cell $C_1$ 2 mice.
$\mathbf{M}$: Move ...
- 1,356
11
votes
3
answers
5k
views
What's the proof of correctness for Robert Floyd's algorithm for selecting a single, random combination of values?
I read about it in a SO answer:
Algorithm to select a single, random combination of values?
...
- 235
6
votes
0
answers
178
views
$k$-covering of the set of all possible n-length words
Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.
We call a $...
- 173
0
votes
1
answer
279
views
Number of leaves in a tree that represents a kind of permutations
Consider the following rooted tree, each of whose vertices (except for the root) is labeled with an integer $\in\{1,\dots,n\}$: let $s(v)$ be the sequence consists of the labels on the path from the ...
- 7,290
3
votes
2
answers
126
views
Possibly a combinatorial problem
I have a $5 \times 5$ grid as below
$$\begin{array}{ccccc}
0& 1& 0& 1& 1\\
1& 0& 0& 0& 0\\
1& 0& 0& 0& 0\\
1& 0& ...
- 197
2
votes
2
answers
407
views
How many divisors of a set of numbers has?
Let $S:=\{x_1,x_2,\dots,x_n\}$ be a finite set of natural numbers. Is there an efficient algorithm to find how many numbers divide at least one of $x_i$ in the set $S$?
For example. If $S=\{2,6,15\}$ ...
- 575
2
votes
1
answer
1k
views
Johnson-Cut Max-Cut Approximation
The Johnson-Cut is an $O(n^2)$ Max-Cut approximation with a factor of 2. I have these definitions for MC and none for JC so I assume they're the same:
$G = (V,E,w)$ with $|V| = n$ and $w : E \...
- 125
-2
votes
1
answer
211
views
How many possible ways are there
Suppose i have the given data set of length 11 of scores
p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1]
I want to select 6 ,5 , 5 , 4 , 2 , 2 scores from the data set.
How many ways are there?
For the above ...
- 327