朴素 C++ 解决方案的无序列图

Question

我有一个C++任务，我必须用我选择的容器为高德纳问题设计一个朴素的解决方案，并研究生成的性能数据。请参阅下面的问题：

三百万名别具一格的男人首尾相连，从纽约到加利福尼亚。每个参与者都得到了一张纸条，上面写下了自己的名字和紧靠他西边的人的名字。队伍最西端的那个人不明白该怎么办，所以他把纸扔掉了;剩下的2,999,999张纸条被放在一个巨大的篮子里，带到华盛顿特区的国家档案馆。在这里，篮子里的东西被完全洗牌并转移到磁带上。

在这一点上，一位信息科学家观察到磁带上有足够的信息来重建按原始顺序排列的人员列表。一位计算机科学家发现了一种方法，只需使用磁带的顺序访问和少量随机存取存储器，就可以通过不到1000次数据磁带进行重建。这怎么可能？

[换句话说，给定 1 ≤ i

根据我的研究，我决定使用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

本质上是说"找到以当前西风邻居为自名的元组"。

当然，后半部分只是反过来应用相同的逻辑，以填充向东的链条。

Answer 2

第一次尝试

我这样做是为了回答，因为不可能将其作为评论来问。 还澄清这一点是恕我直言至少一半的答案

这是指以下吗？

identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
    if( xc < westerly neighbour of xc )
    {
        append xc to list
    }
    // Do not understand this:
    // - xc < head of list
}
while( while xc has easterly neighbour )
{
    if( xc < easterly neighbour of xc )
    {
        prepend xc to list
    }
}

（这只是尝试更接近解决方案-我什至还没有考虑算法...

第二次尝试

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
    }
}

这有点道理：所以你浏览列表，尽可能收集所有西风邻居，然后对所有东风进行此操作。 因此，对于原始列表的每次运行，排序列表会变得越来越长。

第三次尝试

恕我直言，缺少一些东西：如果我解释所有可用的信息，我会得出以下解决方案。 但这需要对原始磁带进行更多的扫描：而不是给定的 10.000 次，而是扫描大约 750.000 次。有什么想法吗？

#include <vector>
#include <algorithm>
#include <iostream>
#include <list>
size_t constexpr max_men { 3000000 };
typedef std::tuple< int, int > neighbors_t;
typedef std::vector< neighbors_t > pool_t;
int main() {
  // Need a vector here for random_shuffle - but using it further down
  // just with sequencial methods.
  pool_t pool_list;
  for( size_t i { 0 }; i < max_men - 1; ++i ) {
    pool_list.push_back( std::make_tuple( i, i + 1) );
  }
  std::random_shuffle( pool_list.begin(), pool_list.end() );

  // Use the algorithm to get it sorted again
  // identify an individual xc:
  // Pick first from first tuple
  // append xc to empty list
  std::list<int> sorted_list;
  sorted_list.push_back( std::get<0>( pool_list.front() ) );
  // Count the number of tape scans
  size_t tape_scans { 0 };
  do {
    // Scan through the pool_list
    for( neighbors_t n : pool_list ) {
#if 0
      std::cout << "n [" << std::get<0>( n ) 
        << "] sorted_list [";
      for( int i : sorted_list ) {
        std::cout << i << " ";
      }
      std::cout << "]" << std::endl;
#endif
      // while( xc has westerly neighbour )
      // Found westerly neighbour
      if( std::get< 1 >( n ) == sorted_list.front() ) {
        // append xc to list
        sorted_list.push_front( std::get< 0 >( n ) );
      }
      if( std::get< 0 >( n ) == sorted_list.back() ) {
        // append xc to list
        sorted_list.push_back( std::get< 1 >( n ) );
      }
    } 
    ++tape_scans;
    std::cout << "Tape Scans needed [" << tape_scans 
          << "] sorted list size [" << sorted_list.size() << "]"
          << std::endl;
  } while( sorted_list.size() < max_men );
  std::cout << "Tape Scans needed [" << tape_scans << "]" << std::endl;
  return 0;
}