天真c ++解决方案的无序映射

Question

我有一个C++任务,我必须用我选择的容器设计一个天真的Knuth问题解决方案并研究生成的性能数据.见下面的问题:

从纽约到加利福尼亚,有三百万名男子名字端到端.每个参与者都得到了一张纸条,上面写下了他自己的名字和他身边的人的姓名.线路最西端的那个人不明白该怎么办,所以他扔掉了他的纸; 剩余的2,999,999张纸被放入一个巨大的篮子里并被带到华盛顿特区的国家档案馆.这里篮子的内容被彻底洗牌并转移到磁带上.

此时,一位信息科学家观察到磁带上有足够的信息来重建原始顺序的人员列表.一位计算机科学家发现了一种通过数据磁带进行重建的方法,只需使用数据磁带和少量随机存取存储器.这怎么可能？

[换句话说,给定1≤i<N的对(xi,xi + 1),以随机顺序,xi是不同的,如何获得序列x1 x2 ... .xN,将所有操作限制为串行技术,适用于磁带.当没有简单的方法来判断两个给定键中的哪一个在另一个之前时,这就是按顺序排序的问题;

根据我的研究,我决定使用unordered_map,而不是列表或法线贴图.我不明白的是提供给我们实现代码的天真解决方案:

考虑将论文作为(名称,名称)元组的集合,可以从这些元组建立继承者(西风邻居)和前任(东方邻居).

 - identify an individual xc

 - append xc to empty list

 - while xc has westerly neighbour

 - xc < westerly neighbour of xc

 - append xc to list

 - xc < head of list

 - while xc has easterly neighbour

 - xc < easterly neighbour of xc

 - prepend xc to list

我的第一个问题 - xc只是一个随机元素,因为容器的性质导致订单无法确定？

我的第二个问题 - 我们给出的名字是这样的文件:

Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg

那么天真的解决方案是说我应该拿第一个名字并把它放在一个列表中,然后是姓氏并将其放入不同的列表中？

道歉,如果我完全关闭,但我真的试图理解这一点!

Answer 1

我相信解决方案是说使用一个列表。选择第一个元组，并将其名字作为列表的头部，将西边的邻居作为下一项。然后，找到以该西风邻居作为其名字的元组（当然，这是困难的部分），并从该元组中获取西风邻居并将其附加到列表中。重复此操作，直到找不到包含最后添加的人员姓名的元组。然后你就知道你已经到达西海岸了。

所以，第一个 xc 本质上是随机的。之后，xc 是确定性的。这条线说

- while xc has westerly neighbour

本质上是在说“找到以当前西边邻居作为自身名称的元组”。

当然，后一部分只是反向应用相同的逻辑，以填补向东的链条。