Take the 2-minute tour ×

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?

share|improve this question
You mean "can't cut the key in half to get two identical halves"? –  Edwin Jan 18 '12 at 0:24
Maybe it sounds ambiguous but I mean to say that "repetitive" means that you can do such a thing. –  2rs2ts Jan 18 '12 at 0:25
It's not ambiguous, it's contradictory. First you say not repetitive (so AABAAB won't work), then you say you can cut the key in half and get two identical halves (so AABAAB would work). Your example supports the former. Just asking for clarification. –  Edwin Jan 18 '12 at 0:29
I think the OP means that repetitive == can cut into equal halves and that strings should not be repetitive, as the examples suggest. –  katrielalex Jan 18 '12 at 0:35
I'll change it, in that case. –  2rs2ts Jan 18 '12 at 0:35
add comment

2 Answers

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

EDIT: fixed up thanks to @PetrViktorin

share|improve this answer
You can use n instead or len(s). Also, use the // operator for integer division. –  Petr Viktorin Jan 18 '12 at 0:35
@PetrViktorin: oopsie, yes, thanks. –  katrielalex Jan 18 '12 at 0:36
I get a TypeError: 'int' object is not iterable. –  2rs2ts Jan 18 '12 at 1:05
Is alphabet what you think it is? It should be an iterable e.g. a string or a list of characters. –  katrielalex Jan 18 '12 at 8:27
It works for me. One of your names is not defined right: either alphabet is not an iterable or product is not itertools.product. –  katrielalex Jan 25 '12 at 23:06
show 1 more comment

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.


share|improve this answer
+1. Very nice, never needed that although I use itertools frequently. Seems to be exactly what @agarett wants. –  ChristopheD Jan 18 '12 at 0:28
Unfortunately not right, since combinations are sorted. –  katrielalex Jan 18 '12 at 0:30
I see how it creates all the combinations but I don't know how to write such a generator. While iterating through keys I could just check to see if the first half equals the second half, but if that could be magically avoided I would prefer that. –  2rs2ts Jan 18 '12 at 0:38
add comment

Your Answer


