2

我有 2 个字符串向量（一个大约是另一个的 1/3）。我正在尝试实现一种算法，将两个向量随机混洗在一起。在结果向量中，先前在向量 A 中的项目可以相互跟随，但在向量 B 中的项目不能。

例如，如果向量 A 中的每个元素都是“FOO”，向量 B 中的每个元素都是“BAR”，那么结果向量可能是 {"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 范围内）并且它永远不会获得有效的向量。总是有至少一个“BAR”按顺序重复。任何人都可以提出更好的替代方案，然后继续重新检查创建的向量中是否存在“BAR”的重复项？我是否让这变得比它必须的更复杂？

4

5 回答 5

6

结果列表由"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 和s的数量1是不变的，因此可以生成一个包含这些的向量并将其打乱。

唯一的问题是在结尾处，其中单个"BAR"也是有效的（如果您将"BAR","FOO"其视为原始元素，则会在开头出现同样的问题）。

"FOO"如果包含的向量增加 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;
}
于 2013-04-03T08:28:53.537 回答
2

我们可以根据从 A 和 B 中分配的剩余元素数量计算结果向量中的下一个元素应该来自 A 或 B 的概率，并根据该概率从 A 或 B 中随机选择下一个元素.

如果选择的最后一个元素来自列表 B，则从列表 A 中选择下一个元素的概率始终为 100%（这会阻止 B 中的连续元素）。

如果 A 中剩余的元素数等于 B 中剩余的元素数，如果添加到结果列表中的最后一个元素来自 A，那么从 B 中获取下一个元素的概率是 100%。

(A.length() - B.length())/A.length()否则，从 A 中选择元素的概率应该等于 我们可以通过根据这个概率测试一个介于 0 和 1 之间的随机生成的值来确定元素应该来自列表 A 还是列表 B。

这应该保证 As 和 B 被均匀地洗牌，可以通过多次运行程序并比较结果向量的每一半中的 B 数量来测试这一点。

（编辑）

我认为在 Python 中测试这个算法会更快，所以这是我的 Python 实现：

from random import random

def intersperse(a,b):
    la = len(a)
    lb = len(b)
    ia = 0
    ib = 0
    bWasLast = False
    res = []
    while (ia < la) or (ib < lb):
        if bWasLast:
            res.append(a[ia])
            ia += 1
            bWasLast = False
        elif ((lb - ib) > (la - ia)) and not bWasLast:
            res.append(b[ib])
            ib += 1
            bWasLast = True
        else:
            laRemaining = la - ia
            lbRemaining = lb - ib
            probA = (laRemaining - lbRemaining)/laRemaining
            if random() < probA:
                res.append(a[ia])
                ia += 1
                bWasLast = False
            else:
                res.append(b[ib])
                ib += 1
                bWasLast = True
    return res

测试代码如下：

A = 'a'*10000
B = 'b'*3000

sumBLeft = 0
sumBRight = 0

for n in range(100):
    r = intersperse(A,B)
    sumBLeft += sum([1 for x in r[:len(r)//2] if x == 'b'])
    sumBRight += sum([1 for x in r[len(r)//2:] if x == 'b'])

print (sumBLeft/sumBRight)

该程序的输出显示，在我的测试运行中，结果左侧的“b”数量仅比结果右侧的“b”数量多 0.08%，证实了“b”的分布通过结果向量是偶数。

于 2013-04-03T05:58:56.370 回答
0

据我从你的代码中可以看出，你正在为好运而洗牌，直到你得到的组合是有效的。我的方法如下：

是foo带有“FOO”项目bar的向量和带有“BAR”项目的向量，并且是F和B它们各自的大小。
任何条形项之前都必须有一个“FOO”项，除非“BAR”项是结果序列中的第一项。因此，如果我们将“BAR”和它们前面的“FOO”画在一起，我们会得到B“FOOBAR”序列（或者B-1，如果我们以“BAR”开头）和F-B（或F-(B-1)）介于两者之间的“FOO”。结果序列以“BAR”项开头的概率是B/(F+1)。

我首先为“BAR”和“FOO”项目的混合制作一个模式向量，然后将真实结果向量混合在一起。该模式将由“FOOBAR”和“FOO”项组成，因为“BAR”项必须以“FOO”开头，除非结果序列以“BAR”开头

伪代码：

bool startsWithBar = B < (random * (F+1));
//if the sequence starts with a BAR, there are B-1 FOOBAR items
int nFOOBAR = B - (startsWithBar ? 1 : 0); 
int nFOO = F - nFOOBAR;

vector<char> pattern(nFOOBAR, 'm'); //m for mix - FOOBAR = FOO followed by a BAR
pattern.insert(pattern.end(), nFOO, 'f');

shuffle(pattern);
shuffle(foo);
shuffle(bar);

vector<string> result;
result.reserve(F+B);

auto itBar = begin(bar);
auto itFoo = begin(foo);

//fill the result according to the pattern
if (startsWithBar)
  result.push_back(*itBar++);

for (char patt : pattern)
{
  switch (patt)
  {
    case 'f': //"FOO"
      result.push_back(*itFoo++);
      break;
    case 'm': //"FOOBAR"
      result.push_back(*itFoo++);
      result.push_back(*itBar++);
      break;
  }
}

例如{"FOO","FOO","BAR","FOO","BAR","FOO","FOO","BAR"}，模式将是{'f', 'm', 'm', 'f', 'm'}

于 2013-04-03T06:19:13.310 回答
0

如果您的第二个向量v2短于v1您必须将每个元素复制v2到输出向量vout中并每次附加一个或多个元素v1。一种解决方案是，枚举所有可能的索引v1并随机擦除它们，直到只剩下与 中的元素一样多的索引v2。因此，两个相邻索引之间的差异是您在 的元素之后v1插入的元素数量。例如：voutv2

    using size_type = std::vector<std::string>::size_type;

    std::vector<size_type> vid(v1.size());
    std::iota(begin(vid), end(vid), 0);
    std::random_shuffle(begin(vid), end(vid));
    vid.erase(std::next(begin(vid), v2.size()), end(vid));
    std::sort(begin(vid), end(vid));

    size_type id_last = 0;
    for(size_type i = 0; i < vid.size(); ++i) {
        vout.insert(end(vout), std::next(begin(v1), id_last),
                                                 std::next(begin(v1), vid[i]));
        vout.push_back(v2[i]);
        id_last = vid[i];
    }
    vout.insert(end(vout), std::next(begin(v1), vid.back()), end(v1));

这可能不是最快的方法，但它应该概述其背后的想法。我相信整个索引管理也可以使用一些迭代器适配器来重写，比如boost。另外，如果合并后不需要原始字符串向量，可以移动字符串而不是复制它们。

于 2013-04-03T08:08:11.867 回答
0

一个想法是这样做：

  • 洗牌A。
  • 将生成的向量 C 初始化为混洗后的 B。此时 C 中的元素是|B|，并且您知道您必须至少将|B|-1A 中的元素放在它们之间。
  • 从打乱后的 A 向量中弹出元素，将它们插入到 C 内的适当位置，以避免在 C 内重复 B 元素。
  • 使用 A 中的剩余元素在随机位置完成|A|-(|B|-1)对 C 向量的插入。

假设你有：

A = {FOO1, FOO2, FOO3, FOO4, FOO5}
B = {BAR1, BAR2, BAR3}

第 1 步和第 2 步：

A = {FOO4, FOO3, FOO1, FOO5, FOO2}
C = {BAR3, BAR1, BAR2}

第 3 步：

A = {FOO1, FOO5, FOO2}
C = {BAR3, FOO4, BAR1, FOO3, BAR2}

第4步：

C = {FOO1, FOO5, BAR3, FOO4, BAR1, FOO3, FOO2, BAR2}
于 2013-04-03T08:26:45.957 回答