1

I have a number of letters say three a's and two b's and I want to find all possible words with them. I have tried itertools.permutations and itertools.product but they didn't help because:

1) The results permutations contains repetitions (i.e. the same word appears multiple times). For example:

> print [''.join(i) for i in itertools.permutations('aab', 3)]
['aab', 'aba', 'aab', 'aba', 'baa', 'baa']

2) The results of product can contain words with only one of the letters:

> print [''.join(i) for i in itertools.product('ab', repeat=3)]
['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

With two a's and one b I want to get `['aab', 'aba', 'baa']. Also I need the approach to use iterators and not lists (or any other way the stores everything in memory) because the results can be very large.

Elektito
  • 3,863
  • 8
  • 42
  • 72
  • As I said I don't want to store the entire results in memory as it can get quite big. Something like itertools would be nice. – Elektito Oct 18 '14 at 14:06
  • You can use generator from here http://stackoverflow.com/questions/6284396/permutations-with-unique-values/6285203#6285203 or http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695#12837695 – Luka Rahne Oct 18 '14 at 22:18
  • @LukaRahne The first one exhausts the stack relatively quickly, but the second seems to be perfect. Thank you. – Elektito Oct 19 '14 at 06:48

2 Answers2

2
def _permute(xs):
    if not xs:
        yield ()
    for x in xs:
        xs[x] -= 1
        if not xs[x]:
            xs.pop(x)
        for ys in _permute(xs):
            yield (x,) + ys
        xs[x] += 1

from collections import Counter
def permute(xs):
    return _permute(Counter(xs))

Usage:

>>> list(permute('aab'))
[('a', 'a', 'b'), ('a', 'b', 'a'), ('b', 'a', 'a')]
>>> [''.join(xs) for xs in permute('aab')]
['aab', 'aba', 'baa']
>>> map(''.join, permute('aab'))  # list(map(...)) in Python 3.x
['aab', 'aba', 'baa']
falsetru
  • 357,413
  • 63
  • 732
  • 636
  • Thanks but `next(permute('ab'*1000))` gives me a "maximum recursion depth exceeded" error which means this won't be a suitable solution for my situation. – Elektito Oct 18 '14 at 16:18
  • @Elektito, You can increase the recursion limit using `sys.setrecursionlimit`. For example, `import sys; sys.setrecursionlimit(3000)` – falsetru Oct 18 '14 at 16:19
  • A bit larger and now I get a segfault. Besides, this doesn't essentially change the space complexity of the solution, and relying on the stack for storing this much data can usually lead to trouble. – Elektito Oct 18 '14 at 16:28
  • 1
    Clever. I see what you did there! :) Still it seems to have a space complexity larger than O(n). It brought down my computer for `next(permute('ab'*100000))` which should not be a problem with an O(n) algorithm. I found this though (suggested by Luka Rahne above) and it seems to work perfectly: http://stackoverflow.com/a/12837695/363949. Thank you very much for your time. – Elektito Oct 19 '14 at 06:45
  • @Elektito, Thank you for the feedback. I will check the answer there. – falsetru Oct 19 '14 at 06:46
-1

I like this problem!

  1. Split the list of characters into those that aren't duplicated and those that are.
  2. You can generate the unique permutations of the non-duplicated characters one at a time using itertools.
  3. For each of the characters that are duplicated, you can generate the ways to insert those characters one at a time. (This needs to be done separately so we don't treat different orders of these duplicates as distinct.)
Scott Hunter
  • 48,888
  • 12
  • 60
  • 101