Как мне создать все возможные комбинации карт <char, char> из карты <char, vector <char>>?

Question

Я хочу взять map<char, vector<char> > и сгенерировать из него каждое возможное map<char, char>.

Я понимаю, что это может занять значительный объем памяти и занять немного времени.

Каждая map<char, char> должна содержать каждую букву a-z и сопоставляться с уникальным символом a-z. то есть. Аляска Ь ср ду эв ФХ Джорджия ро инфракрасный JQ кп литий тх Северная Каролина оо пз Достаточное количество гх SD тэ ию В.Ф. Рабочая группа хт юй ZT

Вот что я уже сделал для себя:

Чтобы сократить смешное количество возможных комбинаций до меньшего количества, если vector<char> содержит более 5 элементов, я просто заменю его на vector<char>, содержащий один символ из моего оригинала 'master' / ' 'map<char, char>.

Не все символы будут присутствовать над всеми vector<char>s на карте. Эти символы должны быть найдены и помещены в некоторый вектор «других».

Это также должно содержать символы, где один символ является единственным возможным символом для более чем одной символьной клавиши (т. Е. Mw в примере, из которого я работаю - я не уверен, как это сделать).

Этот «чужой» вектор следует использовать для случаев, когда невозможно иметь уникальный символ a-z или если несколько символов имеют один и тот же возможный символ.

Вот пример того, что у меня есть.

Я буду принимать map<char, vector<char> >, например:

a: gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
д: мвт
e: gjkpqvxz
f: nr
г: в
ч: ср
я: его
j: gjkpqvxz
k: r
л: ч
m: gjkpqvxz
n: gjkpquvxyz
o: is
p: gjkpqvxz
q: is
r: dl
с: л
т: е
u: dgkpuvy
v: cf
w: bcf
x: dguy
y: f
z: на

Это моя стартовая карта. После вырезания больших векторов символов более 5 и замены их на лучшее предположение. Если значение vector<char> размера 1, то это сопоставление символов имеет только одну комбинацию, и этот символ нельзя использовать ни в каком другом сопоставлении, поскольку это сделает его не уникальным. Я урезал его до:

a: k
b: j
с: р
д: мвт
e: v
f: n
г: на
ч: с
я: это
j: q
к: г
л: ч
м: х
n: guy
o: is
p: z
q: is
р: д
с: л
т: е
u: dguy
V: C
w: bc
x: dguy
y: f
z: на

Вектор 'others' содержит 'o' (я думаю, важно отметить, что я думаю, что он должен содержать такие случаи, как mw из приведенного выше примера. Поскольку d - это единственное место, где можно использовать mw, но, очевидно, с нужно, чтобы каждая буква использовалась только один раз, можно использовать только одну, оставляя другую где-то потерянной. Я не уверен, как программировать общий случай, чтобы добавить их в вектор других.)

Я ищу помощь и указатели для генерации всех возможных map<char, char> из map<char, vector<char> >s, как это и в этом формате. Они будут использоваться в качестве аргумента в вызове функции. Я не совсем уверен, с чего начать писать что-то, что будет работать в общем смысле. Я, вероятно, подхожу к этому с большим количеством циклов for, просматривающих каждый элемент против каждого другого элемента против любого другого элемента ... и т. Д. И т. Д., Что, я полагаю, будет крайне неэффективным, и, вероятно, есть гораздо более элегантные способы решения такой проблемы .

Извините, если это слишком много текста или кажется слишком конкретным или плохо написано / спросили.

Я ценю любую помощь.

Answer 1

Полагаю, я надеюсь, что мне не нужно, чтобы они все существовали одновременно. Тогда я мог бы:

1) Создайте первую карту, назначив первый возможный элемент каждой букве:

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

2) Создайте оставшиеся карты по очереди, неоднократно изменяя существующую карту:

++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 может воссоздавать «чужой» вектор каждый раз с карты, или вы можете обновлять его каждый раз, когда вы меняете персонажа. Заменить:

    new_map['a'] = something;

с:

    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;

В вашем урезанном примере есть только около 6000 возможностей, которые должны пролететь мимо. На самом деле, если вам все они нужны одновременно, вы можете копировать предыдущую карту на каждом шаге, и это точно не займет до следующего ледникового периода.

Кстати, считали ли вы, что карта немного излишня только для 26 возможных ключей, каждый из которых должен присутствовать на каждой карте? Вектор или массив будет значительно дешевле использовать и копировать.

Answer 2

Я понимаю, что это может занять значительный объем памяти и занять немного времени.

Да, количество комбинаций составляет около 403 291 461 000 000 000 000 000 000: -)