Python 3: Generate not all permutations, but all non-repetitive combinations of length r?

Question

I'm trying to generate a lazily iterable collection of Vigenere cipher keys of length r. I'm aware of itertools and the permutations() method. However, this generates keys such as ABCD, ABCE, ABCF... but it will never do something like AABC.

So basically, I need tuples or strings of characters that aren't repetitive (that is, a repetitive key can be cut in half to get two identical halves), but can contain duplicate characters. Good example: AABABA, not AABAAB.

How can I create such a collection that won't generate keys like this, and is lazily iterated so I don't blow up my RAM when I want to explore keys longer than 3 characters?

Answer 1

("".join(s) for s in product(alphabet, repeat=n) if s[:n//2]!=s[n//2:])

_{EDIT: fixed up thanks to @PetrViktorin}

Answer 2

It sounds like you want to use itertools.combinations_with_replacement(). On top of that, you can write a generator around that to filter out the ones you don't want.

http://docs.python.org/library/itertools.html#itertools.combinations_with_replacement