2

文字列のベクトルが 2 つあります (一方は他方のサイズの約 1/3 です)。2 つのベクトルをランダムにシャッフルするアルゴリズムを実装しようとしています。結果として得られるベクトル項目では、以前にベクトル A にあったものは互いに追跡できますが、ベクトル B にあったものは追跡できません。

たとえば、ベクトル A のすべての要素が「FOO」で、ベクトル B のすべての要素が「BAR」の場合、結果のベクトルは {"FOO","FOO","BAR","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" の少なくとも 1 つが常に存在します。「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 に答える
0

アイデアは、次のようにすることです。

  • シャッフル A.
  • 結果のベクトル C をシャッフルされた B として初期化します。この時点で、C の要素は|B|であり、それらの間に少なくとも|B|-1A の要素を配置する必要があることがわかります。
  • シャッフルされた A ベクトルから要素をポップし、それらを C 内の適切な位置に挿入して、C 内で B 要素が繰り返されないようにします。
  • |A|-(|B|-1)A 内の残りの要素を使用して、ランダムな位置で 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 に答える
0

2 番目のベクトルv2が短い場合は、 の各要素を出力ベクトルv1にコピーし、毎回 の1 つ以上の要素を追加する必要があります。1 つの解決策は、 のすべての可能なインデックスを列挙し、要素が にあるのと同じ数のインデックスだけが残るまでそれらをランダムに消去することです。したがって、隣接する 2 つのインデックスの違いは、 の要素の後に挿入するの要素の数です。例えば：v2voutv1v1v2v1voutv2

    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 に答える