How do you find all the combinations of a 40 letter string?
I have to find how many combinations 20 D and 20 R can make.
as in one combination could be...
DDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRR
thats 1 combination, now how do I figure out the rest?
To count every combination of 20 D and 20 R, we can think of there being 40 "slots", 20 of these slots will be filled by D, and the rest will be filled by R. So, we can calculate the total number of combinations using C(40, 20), or 40 choose 20, which can be represented with the following formula:
40!/(20!*(40-20)!)
Or in Python:
>>> import math
>>> math.factorial(40) / (math.factorial(20) * math.factorial(40-20))
137846528820L
Note that this is the same thing as the number of unique permutations of a string with 20 D and 20 R, but if you just calculate the number of permutations of that string you will be counting a lot of duplicates, and if you tried to calculate this by creating each permutation it will take a very long time.
If you wanted to actually generate the unique permutations (which I don't suggest), one way to do it would be to use itertools.combinations(range(40), 20). Each element returned here would be a tuple of 20 integers, which would be the indices of each D in that particular permutation.
There are a lot of permutations. It usually isn't a good idea to generate them all just to count them. You should look for a mathematical formula to solve this, or perhaps use dynamic programming to compute the result.
Here's a nice function built into itertools:
This taken directly from this link: 9.7. itertools — Functions creating iterators for efficient looping
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
Edit
I've included a link I found on SO which gives a fine example of doing this using JavaScript: Is there any pre-built method for finding all permutations of a given string in JavaScript?
If you don't mind PHP, here's an example taken directly from this link: 4.26. Finding All Permutations of an Array
Note: To use the pc_permute function, you would need to separate your string into a character array.
function pc_permute($items, $perms = array( )) {
if (empty($items)) {
print join(' ', $perms) . "\n";
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
pc_permute($newitems, $newperms);
}
}
}
Depending on what you want to do with the combinations, there are a lot of ways to figure this out. If you just want to know the number of combinations/permutations that exist, math can tell you that.
If you want to do something like build a brute force algorithm that checks every possible arrangement of a given set of characters, itertools.product() can help.
http://docs.python.org/library/itertools.html#module-itertools
Here's a generator which generates all distinct permutations.
def distinct_pem(A,D):
if A==0: yield 'D'*D
elif D==0: yield 'A'*A
elif A==1 and D==1:
yield 'AD'
yield 'DA'
else:
if A>=2:
for string in distinct_pem(A-2,D):
yield 'AA'+string
if A>1 and D>1:
for string in distinct_pem(A-1,D-1):
yield 'AD'+string
yield 'DA'+string
if D>=2:
for string in distinct_pem(A,D-2):
yield 'DD'+string
For 10 this is very fast, but it struggles with 20 (perhaps it can be made more efficient?).
