在第二个列表中混合两个列表而不重复

Question

我有2个字符串向量(一个大约是另一个的1/3).我试图实现一个算法,将两个向量随机混合在一起.在结果矢量中,先前在矢量A中的项目可以相互跟随,但是矢量B中的项目不能.

例如,如果向量A中的每个元素都是"FOO"并且向量B中的每个元素都是"BAR",那么得到的向量可能是{"FOO","FOO","BAR","FOO","BAR", "富", "富", "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范围内),它永远不会得到有效的向量.总是存在至少一个"BAR"顺序重复.有人能够建议一个更好的选择,然后只是继续重新检查创建的矢量为重复的"BAR"？我是否比这更复杂？

Answer 1

结果列表由"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".

0s和1s 的数量是不变的,因此可以生成包含这些的矢量并将其随机化.

唯一的问题是在最后,单个"BAR"也是有效的(如果你"BAR","FOO"看作原始元素,在开始时会出现同样的问题).

如果包含的向量"FOO"增加1个虚拟元素(sentinel),则可以解决这个问题.结果列表总是以元素结尾,"FOO"但在其他方面是真正随机的.但我们可以安全地删除最后一个元素,因为这是我们的假人.

实现算法的简单代码(没有在Iterators和Allocators上进行模板化)可能如下所示:

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