2

Possible Duplicate:
is there any best way to generate all possible three letters keywords

how can I enumerate all strings of length K from an alphabet L, where L is simply a list of characters? E.g. if L = ['A', 'B', 'C'] and K = 2, I'd like to enumerate all possible strings of length 2 that can be made up with the letters 'A', 'B', 'C'. They can be reused, so 'AA' is valid.

This is essentially permutations with replacement, as far as I understand. if theres a more correct technical term for this, please let me know.... its essentially all strings of length K that you can make by choosing ANY letter from the alphabet L, and possibly reusing letters, in a way that is sensitive to order (so AB is NOT identical to BA according to this.) is there a clearer way to state this?

in any case i believe the solution is: 

[ ''.join(x) for x in product(L, repeat=K) ]

but i am interested in other answers to this, esp. naive approaches versus fast Pythonic ones, and discussions of speed considerations.

Community
  • 1
  • 1
  • Please write some code and / or tell us specifically what problem you're facing trying to do that. – agf Sep 27 '11 at 07:39
  • You can do it by using recursion. – tgmath Sep 27 '11 at 07:40
  • I agree it's a duplicate, apologies for missing it. would still like to know about recursive way to do this since that is not mentioned in other thread in detail –  Sep 27 '11 at 08:03
  • Your edit has made this a discussion / polling question -- it no longer has a specific correct answer, or even a specific question ("I am interested in..."). That's not on-topic for this site. – agf Sep 27 '11 at 08:07

2 Answers2

1

this is part of the Python Documentation

EDIT2: of course the right answer is the product, thanks for the comment

print  [''.join(x) for x in product('ABC', repeat=3)]

prints 27 elements

['AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC', 'BAA', 'BAB', 
'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC', 'CBA', 
'CBB', 'CBC', 'CCA', 'CCB', 'CCC']

@agf gave the right answer before

Community
  • 1
  • 1
knitti
  • 6,817
  • 31
  • 42
  • Doesn't look right - if the alphabet size (iterable) is length 3, and r = 3, you'd expect 3^3 sequences, but len([x for x in combinations_with_replacement(['A', 'B', 'C'], 3)]) returns 10. –  Sep 27 '11 at 07:48
  • see my edit, which element would be wrong? :-) – knitti Sep 27 '11 at 07:53
  • 1
    none are wrong, but it misses some. there should be 3^3, or 27 elements: [ ''.join(x) for x in product('ABC', repeat=3) ] ['AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC', 'BAA', 'BAB', 'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC', 'CBA', 'CBB', 'CBC', 'CCA', 'CCB', 'CCC'] –  Sep 27 '11 at 07:58
  • Where is `'ABA'`, `'ACA'` etc? Please read your link "Combinations are emitted in lexicographic sort order." The right answer is given (by me) in http://stackoverflow.com/questions/7074051/is-there-any-best-way-to-generate-all-possible-three-letters-keywords/7074066#7074066 – agf Sep 27 '11 at 07:59
  • thanks, your right. linked to you answer – knitti Sep 27 '11 at 08:06
0

You can use itertools:

n = 3
itertools.product(*['abc']*n)

This gives you 27 elements as you expected.

Olivier Verdier
  • 46,998
  • 29
  • 98
  • 90
  • Read the `product` docs more carefully and see my answer in the linked duplicate http://stackoverflow.com/questions/7074051/is-there-any-best-way-to-generate-all-possible-three-letters-keywords/7074066#7074066 – agf Sep 27 '11 at 08:01