c++ - 混洗两个列表，第二个列表中没有重复

我有2个 vector 的字符串(一个大约是另一个大小的1/3)。我正在尝试实现一种算法，该算法将两个 vector 随机洗牌在一起。在生成的 vector 中，先前在 vector A中的项目可以彼此跟随，但是在 vector B中的项目则不能。

例如，如果 vector A中的每个元素都是“FOO”， vector B中的每个元素都是“BAR”，那么生成的 vector 可能是{“FOO”，“FOO”，“BAR”，“FOO”，“BAR”， “FOO”，“FOO”，“BAR”}

如您所见，“FOO”可能会重复，但“BAR”一定不能重复

到目前为止，这大致就是我所拥有的:

#include <string>
#include <chrono>
#include <algorithm>
#include <random>
#include <vector>

std::vector<std::string> a(1000, "FOO");
std::vector<std::string> b(300, "BAR");
std::vector<std::string> result;

bool resultIsValid();

void mergeVectors()
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 generator(seed);

    result = a;
    result.insert(result.end(), b.begin(), b.end());
    while (!resultIsValid())
    {
        std::shuffle(a.begin(), a.end(), generator);
    }
}

bool resultIsValid()
{
    for(int i=0; i<result.size()-2; ++i)
        if (result[i] == "BAR" && result[i+1] == "BAR")
            return false;
    return true;
}

这不是实际的代码，但是应该给出一个想法。当我运行此程序时，该程序将进入无限循环，因为实际的字符串数要高得多(在10000范围内)，并且它永远都不会获得有效的 vector 。始终至少有一个“BAR”顺序重复。有谁能提出一个更好的选择，然后继续检查创建的 vector 是否重复“BAR”？我使这个变得比必须的复杂吗？

最佳答案

结果列表由"BAR","FOO"和"FOO"元素组成。例如

{"FOO","FOO","BAR","FOO","BAR","FOO","FOO","BAR","FOO"}

可以拆分为

"FOO" | "FOO" | "BAR","FOO" | "BAR","FOO" | "FOO" | "BAR","FOO"

可以压缩为

{0, 0, 1, 1, 0, 1}

其中0表示单个元素，1表示从"BAR"到"FOO"的过渡。
0和1的数量是不变的，因此可以生成一个包含它们的 vector 并将其洗牌。

唯一的问题是最后一个单个"BAR"也是有效的(如果您将"BAR","FOO"视为原始元素，则在开始时会出现相同的问题)。

如果将包含"FOO"的 vector 增加1个伪元素(前哨)，则可以解决此问题。结果列表始终以"FOO"元素结尾，否则实际上是随机的。但是我们可以安全地删除最后一个元素，因为这是我们的虚拟对象。

实现该算法的简单代码(无需在迭代器和分配器上进行模板化)如下所示:

std::vector<std::string> mergeVectors(std::vector<std::string> const& canvas,
                                      std::vector<std::string> const& sprinkle)
{
  assert (canvas.size() + 1>= sprinkle.size()); // otherwise impossible

  std::vector<int> transitions; // 1 for [sprinkle, canvas]
                                // 0 for single [canvas]

  // sprinkle.size() times [canvas, sprinkle]
  transitions.insert(transitions.end(), sprinkle.size(), 1);
  // rest is [canvas].
  transitions.insert(transitions.end(), canvas.size() - sprinkle.size() + 1, 0);

  // There is a problem with the last element since this always is from canvas
  // as well.  So we set the last canvas to a sentinel element which is always removed.
  // This way, we can ensure that the result is truly randomly distributed.

  std::mt19937 generator(std::chrono::system_clock::now().time_since_epoch().count());
  std::shuffle(transitions.begin(), transitions.end(), generator);

  bool last_is_sprinkle = transitions.back(); transitions.pop_back();

  std::vector<std::string> result;
  auto canvas_it   = canvas.begin();
  auto sprinkle_it = sprinkle.begin();

  for (auto t : transitions) {
    if (t) result.push_back(*sprinkle_it++);
    result.push_back(*canvas_it++);
  }
  if (last_is_sprinkle)
    result.push_back(*sprinkle_it);
  return result;
}

关于c++ - 混洗两个列表，第二个列表中没有重复，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15779537/

foo

c++ - 混洗两个列表，第二个列表中没有重复