14

シーケンス[0からn]をランダムな順序で繰り返し、すべての要素に1回だけアクセスするとします。O （1）メモリでこれを行う方法はありますか？つまり、[1..n]シーケンスを作成しstd::iotaて実行することなく、これを実行する方法はありstd::random_shuffleますか？

ランダムな順序でシーケンスを吐き出すある種のイテレータが最適です。

要件は、別のシードを選択することで別のランダムな順序を取得できるようにすることです。

4

6 に答える 6

8

シーケンスをインプレースで変更できる場合は、0からNまでの乱数を繰り返し描画してから、アクセスした要素を消去するか、最後にスワップするか、またはそのようなスキームを使用できます。

于 2012-09-17T13:54:53.893 に答える
6

理論的には、周期が正確にnであり、0..nのすべての値をカバーする乱数ジェネレーターを作成した場合、これを1回実行すると、好みの結果が得られます。

もちろん、これは一般的な解決策ではない場合があります。少なくとも動的なものを探している場合は、PRNGを事前に作成する必要があり、これを行う方法はnに依存するためです。

于 2012-09-17T13:46:37.003 に答える
1

さて...ちょっと考えてみてください。どの要素が以前に訪問されたかをどのように「知る」ことができますか？

簡単な答え：できません。（ステートレスな疑似乱数ジェネレーターを数えない限り、よく編集してください。ただし、コマンドで自分自身を述べたように、一般的なケースでは実行可能ではないようです）

ただし、実際のシーケンスによっては、要素を「その場で」訪問したものとして「マーク」することが可能であるため、技術的にはO（n）ストレージが必要ですが、アルゴリズムに追加のストレージは必要ありません。

例：

const int VISITED_BIT = 0x8000; // arbitrary example

bool extract(int i) { return (i & ~VISITED_BIT); }    
bool visited(int i) { return (i & VISITED_BIT); }    
bool markvisited(int& i) { i |= VISITED_BIT); }

int main()
{
    std::vector<int> v = {2,3,4,5,6};

    int remain = v.size();
    while (remain>0)
    {
        size_t idx = rand(); // or something
        if (visited(v[idx]))
            continue;

        std::cout << "processing item #" << idx << ": " << extract(v[idx]) << "\n";
        markvisited(v[idx]);
        remain--;
    }
}
于 2012-09-17T13:47:42.510 に答える
1

ほとんどのアルゴリズムの問​​題と同様に、時空間のトレードオフがあります。これは、O（n ^ 2）時間を使用してすべての順列を生成することに満足している場合は、O（1）空間で解決できます。いくつかの一時変数を除いて、これが必要とする唯一のストレージは、乱数シード自体（またはこの場合はPRNGオブジェクト）です。これは、疑似乱数のシーケンスを再生成するのに十分だからです。

この関数には、すべての呼び出しで同じPRNGを指定する必要があり、他の目的に使用することはできないことに注意してください。

#include <random>

template<typename PRNG, typename INT>
INT random_permutation_element(INT k, INT n, PRNG prng) {
  typedef std::uniform_int_distribution<INT> dis;
  INT i = 0;
  for (; i < k; ++i) dis(0, i)(prng);
  INT result = dis(0, i)(prng);
  for (++i; i < n; ++i) if (dis(0, i)(prng) <= result) ++result;
  return result;
}

これが素早く汚れたハーネスです。./test 1000 3長さ3の1000の完全な順列を生成します。./test 10 1000000 0 5長さ100万の10の順列のそれぞれの最初の5つの要素を生成します。

#include <iostream>

int main(int argc, char** argv) {
  std::random_device rd;
  std::mt19937 seed_gen(rd());
  int count = std::stoi(argv[1]);
  int size = std::stoi(argv[2]);
  int seglow = 0;
  int seglim = size;
  if (argc > 3) seglow = std::stoi(argv[3]);
  if (argc > 4) seglim = std::stoi(argv[4]);
  while (count-- > 0) {
    std::mt19937 prng(seed_gen());
    for (int i = seglow; i < seglim; ++i)
      std::cout << random_permutation_element(i, size, prng)
                << (i < seglim - 1 ? ' ' : '\n');
  }
  return 0;
}

特定の順列を終了する可能性が低い場合は、これを行うためのより高速な方法がありますが、この書き方は見栄えがよく、おそらく理解しやすいでしょう。（もう1つの方法は、逆の順序で数値を生成することです。つまり、k個の数値を生成した後で停止できますが、最初に結果を取得してから調整するために、2回実行する必要があります。）

于 2012-09-17T20:07:36.860 に答える
0

いいえ、考えてみてください。プログラムが訪れた場所をどこかで覚えておく必要があります。それらすべてにランダムにアクセスできるイテレータがある場合、イテレータの内部はこれを何らかの方法で追跡する必要があり、メモリを使用し続けます。

于 2012-09-17T13:46:25.550 に答える
0

この種の構造を構築したばかりです。ヒープ構造を生成します（最小または最大、関係ありません）。ただし、比較のために、キー値を使用する代わりに、乱数を使用します。したがって、ヒープに挿入されたアイテムはランダムな順序で配置されます。次に、ヒープの基本構造を形成する配列（ランダムに順序付けられます）を返すか、要素を1つずつポップして、ランダムな順序で戻すことができます。このタイプのコンテナが（ヒープとは別の配列を持つのではなく）プライマリストレージとして使用される場合、それはとにかく単なる配列であるため、追加のメモリの複雑さはありません。時間計算量は、挿入の場合はO（log N）、最上位要素をポップする場合はO（log N）です。シャッフルは、各要素O（N log N）をポップして再挿入するのと同じくらい簡単です。

私は、最後まで繰り返した後に自動シャッフルする豪華な列挙子（C＃ですが、C ++イテレーターでも同じことができます）を作成しました。つまり、リストを（ポップせずに）複数回反復し、毎回異なる順序を取得できるたびに、完全な反復ごとにO（N log N）シャッフルが発生します。（カードの山札のように考えてください。すべてのカードが捨て札の山に置かれた後、次回同じ順序にならないように、山札を再シャッフルします。）

于 2013-07-27T22:23:12.490 に答える