c++ - 我应该如何从 map> 生成所有可能的 map 组合？

Question

我正在寻找 map<char, vector<char> >并生成每个可能的 map<char, char>从它。

我知道这可能会占用大量内存并需要一些时间。

每个map<char, char>需要包含每个字母 a-z，并映射到唯一的 a-z 字符。 IE。啊bjcp迪EVfh嘎血红蛋白红外线jq千克李MX数控哦pzqsrl标准差特uwvf工作组xm于zt

到目前为止，这是我为自己得出的结论:

要将可能组合的荒谬数量减少到较低数量，如果 vector<char>包含超过 5 个元素，我将简单地用 vector<char> 替换它包含来 self 的“主人”/“原始”map<char, char> 的单个字符.

并非所有字符都会出现在所有 vector<char>s 中在 map 上。需要找到这些字符并将其放入一些“其他” vector 中。

这还应该包含字符，其中一个字符是多个字符键的唯一可能字符(即我正在使用的示例中的 mw - 我不确定如何去做)。

这个“其他” vector 应该用于不可能有唯一的 a-z 字符的情况，或者多个字符具有相同的单一可能字符的情况。

这是我目前所拥有的示例。

我将参加 map<char, vector<char> > ，例如:

一个:gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
d: 重磅
e: gjkpqvxz
f: 编号
g: 在
h: 比照
我:他的
j: gjkpqvxz
k: r
我:你
米:gjkpqvxz
名词:gjkpquvxyz
o:是
p: gjkpqvxz
问:是
r: DL
小号:大号
吨:电子
你:dgkpuvy
五:比照
w: bcf
x: dguy
是:f
z: 在

这是我的起始 map 。将超过 5 的大字符 vector 剪掉并替换为最佳猜测后。其中是 vector<char>大小为 1，该字符映射只有一种组合，并且该字符不能用于任何其他映射，因为这会使它不唯一。我已将其缩减为:

一个:k
乙:乙
c: p
d: 重磅
e: v
f: n
g: 在
h: c
我:是
j: q
k: r
我:你
米:x
名词:家伙
o:是
p: z
问:是
r: d
小号:大号
吨:电子
u: dguy
五:c
w: 公元前
x: dguy
是:f
z: 在

'others' vector 包含'o'(我认为重要的是要注意我认为这应该包含上面示例中的 mw 等情况。因为 d 是唯一可以使用 mw 的地方，但显然与需要每个字母只使用一次，只能使用其中一个，而另一个丢失在某个地方。我不确定如何编写一个通用案例以将这些添加到其他 vector 中。)

我正在寻求帮助和指导，以生成所有可能的 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)通过修改现有 map 依次创建剩余 map ，重复:

++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 每次都可以从 map 中重新构建“others” vector ，或者您可以在每次更改字符时更新它。替换:

    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 种可能性，应该会飞逝而过。事实上，如果您确实同时需要它们，您可以在每一步都复制以前的 map ，并且不会正好需要到下一个冰河时代。

顺便说一句，您是否认为一张 map 对于只有 26 个可能的键有点矫枉过正，每个键都需要出现在每个 map 中？ vector 或数组的使用和复制成本要低得多。