How should I go about generating every possible map<char, char> combination from map<char, vector<char> >?

Question

I am looking to take a map<char, vector<char> > and generate each possible map<char, char> from it.

I understand this may use a sizeable amount of memory and take a bit of time.

Each map<char, char> needs to contain every letter a-z, and be mapped to a unique a-z character. ie. ak bj cp dy ev fh ga hb ir jq kn li mx nc oo pz qs rl sd te uw vf wg xm yu zt

Here is what I have concluded for myself so far:

To cut down the ridiculous number of possible combinations to a lower amount, if a vector<char> contains more than 5 elements, I will simply replace it with a vector<char> containing a single char from my 'master'/'original' map<char, char>.

Not all characters will be present over all of the vector<char>s in the map. These characters need to be found and put into some 'others' vector.

This should also contain characters where one character is the only possible character for more than one character key(ie. mw in the example I am working from - I'm unsure how to go about this).

This 'others' vector should be used for the cases where it is not possible to have a unique a-z character, or where more than one character has the same, single possible character.

Here’s an example of what I have so far.

I will be taking a map<char, vector<char> >, such as:

a: gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
d: mw
e: gjkpqvxz
f: nr
g: at
h: cf
i: his
j: gjkpqvxz
k: r
l: h
m: gjkpqvxz
n: gjkpquvxyz
o: is
p: gjkpqvxz
q: is
r: dl
s: l
t: e
u: dgkpuvy
v: cf
w: bcf
x: dguy
y: f
z: at

This is my starting map. After cutting out the large character vectors of over 5 and replacing them with the best guess. Where the is a vector<char> of size 1, that character mapping only has one combination, and that character cannot be used in any other mapping as it would make it not unique. I have trimmed it down to:

a: k
b: j
c: p
d: mw
e: v
f: n
g: at
h: c
i: is
j: q
k: r
l: h
m: x
n: guy
o: is
p: z
q: is
r: d
s: l
t: e
u: dguy
v: c
w: bc
x: dguy
y: f
z: at

The 'others' vector contains 'o' (I think it is important to note that I think this should contain cases such as mw from the above example. As d is the only place mw can be used, but obviously with the need for each letter to only be used once, only one of them can be used, leaving the other to be lost somewhere. I'm not sure how to go about programming a general case to add these to the others vector.)

I am looking for help and pointers with generating every possible map<char, char> from map<char, vector<char> >s like this and in this format. They will be used as an argument in a function call. I'm not really sure where to start writing something that would work in a general sense. I would probably approach it with a large amount of for loops looking through every element against every other element against every other element ... etc etc, which I assume would be extremely inefficient and there are probably much more elegant ways of solving such a problem.

Sorry if this is too wall of text-ish or seems overly specific or poorly written/asked.

I appreciate any and all assistance.

Answer 1

I guess I'd hope that I don't need them all to exist simultaneously. Then I could:

1) Create the first map by assigning the first possible element to each letter:

for (char c = 'a'; c <= 'z'; ++c) {  // yes, I assume ASCII
   new_map[c] = old_map[c][0];
}
int indexes[26] = {0};

2) Create the remaining maps in turn by modifying the existing map, repeatedly:

++indexes[0];
if (indexes[0] < old_map['a'].size()) {
    new_map['a'] = old_map['a'][indexes[0]];
} else {
    indexes[0] = 0;
    new_map['a'] = old_map['a'][0];
    // "carry the 1" by applying the same increment process to indexes[1]
}
do_something_with(new_map);

do_something_with can re-construct the "others" vector each time from the map, or else you can update it each time you change a character. Replace:

    new_map['a'] = something;

with:

    char removed = new_map['a'];
    --counts[removed];
    if (counts[removed] == 0) others.add(removed);
    ++counts[something];
    if (counts[something] == 1) others.remove(something);
    new_map['a'] = something;

In your trimmed-down example there are only about 6000 possibilities, which should fly by. In fact, if you did need them all simultaneously you could copy the previous map at every step, and it wouldn't exactly take until the next ice age.

Btw, have you considered that a map is a bit overkill for only 26 possible keys, each of which is required to be present in every map? A vector or array would be considerably cheaper to use and to copy.

Answer 2

I understand this may use a sizeable amount of memory and take a bit of time.

Yes, the number of combinations is about 403,291,461,000,000,000,000,000,000 :-)