Menu
Let's say there's n amount of entries, each of whom can take the value of 0 or 1. That means there's 2^n possible combinations of those entries. The number of entries can vary from 1 to 6.
How can you create each possible combination as a sequence of numbers (i.e. for n = 2: 00, 01, 10, 11), without resorting to a thousand IFs?
391
The formula for combinations is generally n! / (r! (n -- r)!), where n is the total number of possibilities to start and r is the number of selections made. In our example, we have 52 cards; therefore, n = 52. We want to select 13 cards, so r = 13.
The algorithm assumes that we have a set containing elements: {0, 1, … , }. Then, we generate the subsets containing elements in the form , starting from the smallest lexicographic order: The algorithm visits all -combinations. It recursively represents multiple nested for loops.
We set a constant value 2 to r, i.e., the number of items being chosen at a time. After that, we use the combination formula, i.e., fact(n) / (fact(r) * fact(n-r)) and store the result into the result variable.
Heap. This algorithm is based on swapping elements to generate the permutations. It produces every possible permutation of these elements exactly once. This method is a systematic algorithm, which at each step chooses a pair of elements to switch in order to generate new permutations.
You can achieve that just by printing the numbers 0..2^n-1 in binary form.
171
Might as well just use ints:
n = 5
for x in range(2**n):
print ''.join(str((x>>i)&1) for i in xrange(n-1,-1,-1))
Crazy decimal to binary conversion lifted from this answer.
Output:
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
