2

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?

2rs2ts
  • 10,662
  • 10
  • 51
  • 95
  • You mean "*can't* cut the key in half to get two identical halves"? – Edwin Jan 18 '12 at 00: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 00: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 00:29
  • I think the OP means that `repetitive == can cut into equal halves` and that strings should not be repetitive, as the examples suggest. – Katriel Jan 18 '12 at 00:35
  • I'll change it, in that case. – 2rs2ts Jan 18 '12 at 00:35
  • This is straightforwardly a two-step process: generate the possible sequences of values chosen from `{A, B, C, D}` (with repetitions, and distinguishing based on order), and then filtering out those which meet the "repetitive" condition. I assume it's clear how to implement the condition check, so the only remaining question here is about `itertools.product` - so I've closed this as a duplicate. – Karl Knechtel Feb 28 '23 at 21:16

2 Answers2

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

EDIT: fixed up thanks to @PetrViktorin

Katriel
  • 120,462
  • 19
  • 136
  • 170
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

krousey
  • 1,728
  • 15
  • 22
  • +1. Very nice, never needed that although I use `itertools` frequently. Seems to be exactly what @agarett wants. – ChristopheD Jan 18 '12 at 00:28
  • 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 00:38