1

I have a string 'UUUUUUUUUDDDDDDD' those are 9 Us and 7 Ds.

I want to generate all permutations, like:

'UUUUUUUUUDDDDDDD'
'DUUUUUUUUUDDDDDD'
'DUUUUUDUUUDDDDUD'
'DUUDUUDUUUDDDDUU'

In other words, all possible strings with 9 Us and 7 Ds

I'm trying to use itertools.permutations() but that function considers each U and each D as a different element so I get repeated permutations.

In the example below I will use a smaller string UUD just to demonstrate the problem with itertools.permutations:

for g in itertools.permutations('UUD'):
    print(g)

I get

('U', 'U', 'D')
('U', 'D', 'U')
('U', 'U', 'D')
('U', 'D', 'U')
('D', 'U', 'U')
('D', 'U', 'U')

I would want 

('U', 'U', 'D')
('U', 'D', 'U')
('D', 'U', 'U')

Generating all possibilites and then adding them to a set to make them unique is not a viable solution, as there will be too many permutations to store in memory. I would like to generate them one at a time, work with it and discard it.

nosklo
  • 217,122
  • 57
  • 293
  • 297
  • is your actual data much larger than the 9U 7D example at the top? Is it still binary (e.g. only two letters or etc?) – Adam Smith Jul 18 '18 at 18:32
  • @AdamSmith The data could be larger. It is not binary, could have more letters. – nosklo Jul 18 '18 at 18:33
  • darn, there's a good solution with `itertools.combinations` over `range(MAX_LENGTH, num_ds)` but it doesn't scale well. – Adam Smith Jul 18 '18 at 18:35
  • 1
    Sounds like you're looking for a multiset permutation, in which case this might duplicate [this](https://stackoverflow.com/questions/6284396/permutations-with-unique-values) and a few others (e.g. [this](https://stackoverflow.com/questions/19676109/how-to-generate-all-the-permutations-of-a-multiset)). I've used the one which comes with sympy before-- is that an option? – DSM Jul 18 '18 at 18:35

0 Answers0