当前位置：文江博客话题详情

我应该如何生成每个可能的映射来自 map 的组合>？

发布于 2024-08-24 16:51:44 字数 1944 浏览 2 评论 0 原文

我正在寻找一个 map; > 并从中生成每个可能的 map。

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

每个 map 需要包含每个字母 az，并映射到唯一的 az 字符。 IE。 AK 北京 CP 迪电动车频率嘎血红蛋白红外杰克千李 MX 数控哦普兹质量 RL 标准差特华盛顿大学室颤工作组 xm 于 zt

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

为了将可能的组合数量减少到更低的数量，如果 vector 包含超过 5 个元素，我将简单地替换它带有一个 vector ，其中包含我的“master”/“original”map 中的单个字符。

并非所有字符都会出现在地图中的所有 vector 上。需要找到这些字符并将其放入一些“其他”向量中。

这还应该包含其中一个字符是多个字符键的唯一可能字符的字符（即我正在使用的示例中的 mw - 我不确定如何解决这一问题）。

这一“其他”向量应用于不可能具有唯一 az 字符的情况，或者多个字符具有相同的单个可能字符的情况。

这是我到目前为止所拥有的一个例子。

我将采用 map; >，如：

a:gjkpqvxz
b：gjkpqvxz
c: gjkpqvxyz
d: 分子量
e: gjkpqvxz
f：编号
g：在
小时：比照
我：他的
j：gjkpqvxz
k: r
l：h
米：gjkpqvxz
n: gjkpquvxyz
o：是
p：gjkpqvxz
问：是
r: dl
s: l
t: e
你：dgkpuvy
v：比照
w：BCF
x：dguy
y：f
z：

这是我的起始地图。剪掉超过 5 个的大字符向量并用最佳猜测替换它们之后。如果是大小为 1 的向量，则该字符映射仅具有一种组合，并且该字符不能在任何其他映射中使用，因为这会使其不唯一。我已将其精简为：

a: k
b：j
c：p
d: 分子量
e: v
f：n
g：在
小时：c
我：是
j：q
k: r
l：h
米：x
n：家伙
o：是
p：z
问：是
r: d
s: l
t: e
你：dguy
v：c
w：公元前
x：dguy
y：f
z: at

'others' 向量包含 'o' （我认为重要的是要注意，我认为这应该包含上面示例中的 mw 等情况。由于 d 是唯一可以使用 mw 的地方，但显然与每个字母只需要使用一次，只能使用其中一个，而另一个则丢失在某处，我不知道如何编写一般情况以将它们添加到其他向量中。）

我是。寻找帮助和指针，从 map 生成每个可能的 map >s 像这样并且采用这种格式。它们将用作函数调用中的参数。我不太确定从哪里开始写一些在一般意义上可行的东西。我可能会用大量的 for 循环来遍历每个元素，对照每个其他元素，对照每个其他元素……等等，我认为这效率极低，并且可能有更优雅的方法来解决这样的问题。

抱歉，如果这面文字太多，或者看起来过于具体或写得/问得不好。

我感谢任何和所有的帮助。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

唔猫 2024-08-31 16:51:44

我想我希望我不需要它们同时存在。然后我可以：

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 个可能的键（每个键都必须出现在每个地图中）来说有点大材小用？向量或数组的使用和复制成本要低得多。

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.

回复收藏 0 原文