2

ベクトル内の特定の割合の要素をシャッフルする最良の方法は何ですか?

ベクトルの 10% または 90% をシャッフルしたいとします。必ずしも最初の 10% とは限りませんが、全面的には 10% にすぎません。

ティア

4

7 に答える 7

4

配列内のインデックスの 10% に対して何もしないように、Fisher-Yates シャッフルを変更します。

これは私が (ウィキペディアから) 投稿して修正した Java コードですが、これは言語の問題というよりもアルゴリズムの問​​題であるため、C++ に変換できると思います。

public static void shuffleNinetyPercent(int[] array) 
{
    Random rng = new Random();       // java.util.Random.
    int n = array.length;            // The number of items left to shuffle (loop invariant).
    while (n > 1) 
    {
        n--;                         // n is now the last pertinent index
        if (rng.nextDouble() < 0.1) continue; //<-- ADD THIS LINE
        int k = rng.nextInt(n + 1);  // 0 <= k <= n.
        // Simple swap of variables
        int tmp = array[k];
        array[k] = array[n];
        array[n] = tmp;
    }
}
于 2009-11-03T14:39:31.357 に答える
2

独自のランダムイテレータを作成し、random_shuffleを使用して、次のようにするにはどうでしょうか:(アイデアを得るために完全にテストされていません）

template<class T>
class myRandomIterator : public std::iterator<std::random_access_iterator_tag, T>
{
public:
    myRandomIterator(std::vector<T>& vec, size_t pos = 0): myVec(vec), myIndex(0), myPos(pos)
    {
        srand(time(NULL));
    }

    bool operator==(const myRandomIterator& rhs) const
    {
        return myPos == rhs.myPos;
    }

    bool operator!=(const myRandomIterator& rhs) const
    {
        return ! (myPos == rhs.myPos);
    }

    bool operator<(const myRandomIterator& rhs) const
    {
        return myPos < rhs.myPos;
    }

    myRandomIterator& operator++() 
    {
        ++myPos;
        return fill();
    }

    myRandomIterator& operator++(int) 
    {
        ++myPos;
        return fill();
    }

    myRandomIterator& operator--() 
    {
        --myPos;
        return fill();
    }

    myRandomIterator& operator--(int)
    {
        --myPos;
        return fill();
    }



    myRandomIterator& operator+(size_t n) 
    {
        ++myPos;
        return fill();
    }

    myRandomIterator& operator-(size_t n) 
    {
        --myPos;
        return fill();
    }


    const T& operator*() const
    {
        return myVec[myIndex];
    }

    T& operator*()
    {
        return myVec[myIndex];
    }



private:
    myRandomIterator& fill()
    {
        myIndex = rand() % myVec.size();
        return *this;
    }

private:
    size_t myIndex;
    std::vector<T>& myVec;
    size_t myPos;

};

int main()
{
    std::vector<int> a;
    for(int i = 0; i < 100; ++i)
    {
        a.push_back(i);
    }

    myRandomIterator<int> begin(a);
    myRandomIterator<int> end(a, a.size() * 0.4);

    std::random_shuffle(begin, end);

    return 0;
}
于 2009-11-03T15:11:22.190 に答える
2

これを試すことができます：

ベクトルの各要素に乱数を割り当てます。割り当てた乱数の最小 10% に乱数が含まれる要素をシャッフルします。ベクター内のその 10% をプレースホルダーに置き換え、乱数に従って 10% を並べ替え、それらをプレースホルダーがあるベクトル。

于 2009-11-03T15:33:57.673 に答える
1

1 つの方法は、 std::random_shuffle() を使用して、入力範囲を制御することで % を制御できます ....

于 2009-11-03T14:31:25.530 に答える
1

ランダムに選択されたポジションの N 回のスワップを実行しないのはなぜですか。N はパーセンテージによって決定されます。

したがって、100 個の要素がある場合、10% のシャッフルで 10 回のスワップが実行されます。各スワップは、配列内の 2 つの要素をランダムに選択し、それらを切り替えます。

于 2009-11-03T14:32:26.440 に答える
1

SGI のstd::random_sample拡張機能があれば、これを行うことができます。random_sampleそうでない場合は、指定された範囲内で均一に分散されたランダムな整数を返す関数の上に簡単に実装できます (Knuth、第 2 巻、「アルゴリズム R」)。

#include <algorithm>
#include <vector>
using std::vector;

void shuffle_fraction(vector<int> &data, double fraction) {
    assert(fraction >= 0.0 && fraction <= 1.0);

    // randomly choose the indices to be shuffled
    vector<int> bag(data.size());
    for(int i = 0; i < bag.size(); ++i) bag[i] = i;

    vector<int> selected(static_cast<int>(data.size() * fraction));
    std::random_sample(bag.begin(), bag.end(), selected.begin(), selected.end());

    // take a copy of the values being shuffled
    vector<int> old_value(selected.size());
    for (int i = 0; i < selected.size(); ++i) {
        old_value[i] = data[selected[i]];
    }

    // choose a new order for the selected indices
    vector<int> shuffled(selected);
    std::random_shuffle(shuffled.begin(), shuffled.end());

    // apply the shuffle to the data: each of the selected indices
    // is replaced by the value for the corresponding shuffled indices
    for (int i = 0; i < selected.size(); ++i) {
        data[selected[i]] = old_value[shuffled[i]];
    }
}

3 つの「小さな」ベクトルを使用するため、最も効率的ではありませんが、ベクトルのサブセットで動作するようにフィッシャー イェーツ アルゴリズムを適応させる必要がなくなります。実際には、ベクトルではなく、ランダム アクセス反復子のペアで動作する関数テンプレートにする必要があります。コードが少し難読化されると思うので、私はそれをしていませんが、あなたはそれを求めていませんでした。また、比率の代わりにサイズを使用し、分数を丸める方法を決定するのは呼び出し元に任せます。

于 2009-11-03T18:58:15.810 に答える
0

シャッフル バッグ アルゴリズムを使用して、配列の 10% を選択できます。次に、その選択に対して通常のシャッフルを使用します。

于 2009-11-03T14:50:43.033 に答える