We want to efficiently avoid the repeating ones, i.e. to work fast for { 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5}
Generating Permutationswith Repetitions
var arr = new int[] { 3, 5, 1, 5, 5 };
Array.Sort(arr);
PermuteRep(arr, 0, arr.Length);
static void PermuteRep(int[] arr, int start, int n)
{
Print(arr);
for (int left = n - 2; left >= start; left--)
{
for (int right = left + 1; right < n; right++)
if (arr[left] != arr[right])
{
Swap(ref arr[left], ref arr[right]);
PermuteRep(arr, left + 1, n);
}
var firstElement = arr[left];
for (int i = left; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[n - 1] = firstElement;
}
}
Combinations
Order does not matter!
Two types of combinations:
Repetition is allowed
Coins in your pocket
5,5,20,20,20,10,10
No repetition
Lottery numbers
TOTO 6/49, 6/42, 5/35
2,14,15,27,30,33
Combinations without Repetition
Back to the 3 of 16 billiard balls
Many comb. will be the same
We don’t care about the order
Permutations w/o repetitionsreduced by how many ways the objects could be in order:
This is how lotteries work (TOTO 6/49)
Often called “n choose k” (Google it!)
Generate Combinationswithout Repetitions
static void Main()
{
Comb(0, 0);
}
static void Comb(int index, int start)
{
if (index >= k)
PrintCombinations();
else
for (int i = start; i < n; i++)
{
arr[index] = i;
Comb(index + 1, i + 1);
}
}
Pascal’s Triangle
The Pascal’s triangle shows you how many combinations of objects withoutrepetition are possible
Go down to row “n” (the top row is 0)
Move along “k” places
The value there is your answer
Build the triangle: start with “1” atthe top, then continue placingnumbers below it in a triangular pattern
Pascal’s Triangle’s (2)
The triangle is symmetrical
Numbers on the left side haveidentical matching numbers onthe right side, like a mirror image
Diagonals:
First diagonal – only “1”s
Second diagonal – 1, 2, 3, etc.
Third diagonal – triangular numbers
Horizontal sums: powers of 2
Binomial Coefficients
Calculate using recursion:
static decimal Binom(int n, int k)
{ if (k > n) return 0;
else if (0 == k || k == n) return 1;
else return Binom(n-1, k-1) + Binom(n-1, k);
}
Calculate using dynamic programming:
decimal m[MAX], i, j;
for (i = 0; i <= n; i++) {
m[i] = 1;
if (i > 1) {
if (k < i - 1) j = k; else j = i - 1;
for (; j >= 1; j--) m[j] += m[j - 1];
}
} // The answer is in m[k]
Combinations with Repetition
Ice-cream example
5 flavors of ice-cream: banana,chocolate, lemon, strawberry and vanilla
3 scoops
How many combinations will there be?
Let’s use letters for the flavors: {b, c, l, s, v}
{c, c, c} (3 scoops of chocolate)
{b, l, v} (one each of banana, lemon and vanilla)
{b, v, v} (one of banana, two of vanilla)
Combinations with Repetition
Ice-cream example
n=5 things to choose from, choose k=3 of them
Order does not matter, and we can repeat
Think about the ice cream being in boxes
arrow means move, circle means scoop
{c, c, c} (3 scoops of chocolate)
{b, l, v} (banana, lemon, vanilla)
{b, v, v} (banana, two of vanilla)
Combinations with Repetition
We have a simpler problem to solve
How many different ways can you arrange arrows and circles?
3 circles (3 scoops) and 4 arrows (we need to move 4 times to go from the 1st to 5th container)
There are k + (n-1) positions, and we want to choose k of them to have circles
Generate Combinationswith Repetitions
static void Main()
{
Comb(0, 0);
}
static void CombReps(int index, int start)
{
if (index >= k)
PrintVariations();
else
for (int i = start; i < n; i++)
{
arr[index] = i;
CombReps(index + 1, i);
}
}
Combinatorial Formulas
Calculating the number of permutations, variations, combinations
