随机排列

我无法找到一种随机洗牌元素的好方法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;
}

EDIT:继史蒂夫关于使用“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;
}

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

...受限于使用自定义随机数生成器类，我想我不能使用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 http://www.sgi.com/tech/stl/RandomNumberGenerator.html