Let's say I have a three character string "ABC". I want to generate all permutations of that string where a single letter can be replaced with his lower-case equivalent. For example, "aBC", "abC", "abc", "AbC", "Abc", etc. In other words, given a regexp like [Aa][Bb][Cc] generate every string that can be matched by it.
Asked
Active
Viewed 75 times
1 Answers
2
The problem can be trivially reduced to generating all binary sequences of length n. This has been previously addressed, for example in Fastest way to generate all binary strings of size n into a boolean array? and all permutations of a binary sequence x bits long.
-
Not exactly, you can use either "A" or "a" - not both (in the same permutation item) – Nir Alfasi Aug 09 '13 at 18:48
-
@alfasin: Not sure I follow. Each binary digit corresponds to a letter. `0` is lowercase, `1` is uppercase. `000` stands for `abc`, `001` for `abC`, `010` for `aBc` and so on. – NPE Aug 09 '13 at 18:49
-
if you use lowercase "a" you MUST use the capitals: "B" and "C" in this same permutation. At least according to his definition: "where a single letter can be replaced..." – Nir Alfasi Aug 09 '13 at 18:51
-
@alfasin: That's what he says, but I doubt he means it. Look at the examples: they repeatedly violate the constraint. – NPE Aug 09 '13 at 18:52
-
I am using upper-/lower-case only as an example: the transformation on the character is table-driven. – TreeRex Aug 09 '13 at 18:53
-
@NPE I guess you're right - the problem is not defined very well. +1 – Nir Alfasi Aug 09 '13 at 18:54
-
@NPE is correct, the issue is that each character in the string can have multiple variants, and I want to generate the set of all combinations of strings with the variants in the same position. – TreeRex Aug 09 '13 at 18:54
-
Think of it this way: I have a set of strings that can be described the regexp [Aa][Bb][Cc] and I want to generate all strings that can be generated with that regexp. – TreeRex Aug 09 '13 at 18:56