0

I'm trying to generate lists of possible permutations of two values, which only contain equal numbers of each value.

The closest I've come is product permutation and then a Counter afterwards, but this is obviously the wrong way around and consumes vast amounts of memory for values over 20.

lst = ['d', 'r']
correct = 0
for x in product(lst, repeat=20):
    y = Counter(x)
    if y['d'] == y['r']:
        correct += 1
print(correct)

I've also tried just a set of permutations but that's even less efficient than the product algorithm for some reason:

lst = ['d', 'r'] * 10
print(len(set(permutations(lst)))

Can anyone suggest a different tool, or a way of restricting product's generation to only the iterations with equal numbers of each element?

cccczzz
  • 53
  • 4
  • You'd probably need to write your own algorithm. – cs95 Sep 06 '17 at 01:30
  • What do you mean by "vast amounts of memory", and how do you measure that? In general the first approach seems good; it requires 2^20 ~ 10^6 iterations. In each iteration you generate a `Counter` object; it is possible that those collectively use up memory if they are not garbage collected in time. You could try to count the `d`s and `r`s without building intermediate objects. The `permutations` approach is much slower because it requires iteration over 20! ~ 10^18 permutations. – user8153 Sep 06 '17 at 05:02
  • Permutations of a [multiset](https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets) is answered in [How to generate all the permutations of a multiset?](https://stackoverflow.com/questions/19676109/how-to-generate-all-the-permutations-of-a-multiset/) with [An O (1) Time Algorithm for Generating Multiset Permutations](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.77.6275&rep=rep1&type=pdf). "Vast amounts of memory" should not be needed as in the case of a 20 element list of 2 values, the number of permutations would be 20! / (10! * 10!) = 184756 – jq170727 Sep 16 '17 at 15:55

0 Answers0