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.
1 Answer
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.
8 Comments
Nir Alfasi
Not exactly, you can use either "A" or "a" - not both (in the same permutation item)
NPE
@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.Nir Alfasi
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..."
NPE
@alfasin: That's what he says, but I doubt he means it. Look at the examples: they repeatedly violate the constraint.
TreeRex
I am using upper-/lower-case only as an example: the transformation on the character is table-driven.
|