c++ - 随机排列

Question

我无法找到一种合适的方式来随机排列 std::vector 中的元素。并经过一些操作，恢复原来的顺序。我知道这应该是一个相当简单的算法，但我想我太累了......

由于我不得不使用自定义随机数生成器类，我想我不能使用 std::random_shuffle ，这无论如何都无济于事，因为我还需要保留原始订单。所以，我的方法是创建一个 std::map它用作原始位置和随机位置之间的映射，如下所示:

std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
    std::map<unsigned int, unsigned int> permutation;

    //populate the map
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        permutation[i] = i;
    }

    //randomize it
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        //generate a random number in the interval [0, numberOfElements)
        unsigned long randomValue = GetRandomInteger(numberOfElements - 1U);

        //broken swap implementation
        //permutation[i] = randomValue;
        //permutation[randomValue] = i;

        //use this instead:
        std::swap(permutation[i], permutation[randomValue]);
    }

    return permutation;
}

我不确定上述算法是否是随机排列的正确实现，因此欢迎任何改进。

现在，这是我如何设法利用这个排列图:

std::vector<BigInteger> doStuff (const std::vector<BigInteger> &input)
{
    /// Permute the values in a random order
    std::map<unsigned int, unsigned int> permutation = getRandomPermutation(static_cast<unsigned int>(input.size()));

    std::vector<BigInteger> temp;

    //permute values
    for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
    {
        temp.push_back(input[permutation[i]]);
    }

    //do all sorts of stuff with temp

    /// Reverse the permutation
    std::vector<BigInteger> output;
    for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
    {
        output.push_back(temp[permutation[i]]);
    }

    return output;
}

有些东西告诉我，我应该只能使用一个 std::vector<BigInteger>对于这个算法，但是，现在，我只是想不出最优解。老实说，我不太关心 input 中的数据，所以我什至可以将其设为非常量，覆盖它，然后跳过创建它的拷贝，但问题是如何实现该算法？

如果我这样做，我最终会搬起石头砸自己的脚，对吧？ :)

for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
{
    BigInteger aux = input[i];
    input[i] = input[permutation[i]];
    input[permutation[i]] = aux;
}

---

编辑:根据史蒂夫关于使用“Fisher-Yates”洗牌的评论，我更改了我的 getRandomPermutation相应地发挥作用:

std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
    std::map<unsigned int, unsigned int> permutation;

    //populate the map
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        permutation[i] = i;
    }

    //randomize it
    for (unsigned int i = numberOfElements - 1; i > 0; --i)
    {
        //generate a random number in the interval [0, numberOfElements)
        unsigned long randomValue = GetRandomInteger(i);

        std::swap(permutation[i], permutation[randomValue]);
    }

    return permutation;
}

Answer 1

如果您要“随机化”一个包含 n 个元素的 vector ，您可以创建另一个 std::vector<size_t> index(n) , 设置 index[x] = x对于 0 <= x < n , 然后洗牌 index .然后您的查找采用以下形式:original_vector[index[i]] .原始 vector 的顺序从未改变，因此无需恢复顺序。

...constrained to use a custom random number generator class, I guess I can't use std::random_shuffle...

你注意到这个重载了吗？

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rand );

有关如何使用兼容对象包装随机数生成器的详细信息，请参阅 http://www.sgi.com/tech/stl/RandomNumberGenerator.html