随机排列

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,所以我甚至可以使它成为非const,覆盖它,并跳过创建它的副本,但问题是如何实现该算法？

如果我做这样的事情,我最终会用脚射击自己,对吧？:)

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"shuffle的评论之后,我相应地改变了我的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

如果您正在查找代码中的特定错误：

permutation[i] = randomValue;
permutation[randomValue] = i;

是错的。请注意，完成后，每个值不一定在地图的值中恰好出现一次。所以它不是一种排列，更不是均匀分布的随机排列。

The proper means to generate a random permutation is what Tony says, use std::random_shuffle on a vector that initially represents the identity permutation. Or if you want to know how a shuffle is properly performed, look up "Fisher-Yates". In general, any approach that makes N random selections uniformly from 0 .. N-1 is doomed to failure, because that means it has N^N possible ways it can run. But there are N! possible permutations of N items, and N^N is generally not divisible by N!. Hence it's impossible for each permutation to be the result of an equal number of random selections, i.e. the distribution is not uniform.

the question is how to implement the algorithm?

So, you have your permutation, and you want to re-order the elements of input in-place, according to that permutation.

The key thing to know is that every permutation is a composition of "cycles". That is to say, if you repeatedly follow the permutation from a given starting point, you come back to where you started (and this path is the cycle to which that starting point belongs). There may be more than one such cycle in a given permutation, and if permutation[i] == i for some i, then the cycle of i has length 1.

The cycles are all disjoint, that is to say each element appears in exactly one cycle. Because cycles don't "interfere" with each other, we can apply a permutation by applying each cycle, and we can do the cycles in any order. So, for each index i we need to:

• check whether we've already done i. If so, move on to the next index.
• set current = i
• swap index[current] with index[permutation[current]]. So index[current] is set to its correct value (the next element in the cycle), and its old value is "pushed" forward along the cycle.
• mark current as "done"
• if permutuation[current] is i, we've finished the cycle. So the first value of the cycle ends up in the spot formerly occupied by the last element of the cycle, which is right. Move on to the next index.
• set current = permutation[current] and go back to the swap step.

Depending on the types involved, you can optimize around the swaps - it may be better to copy/move to a temporary variable and the start of each cycle, then do a copy/move instead of a swap at each step of the cycle, and finally copy/move the temporary to the end of the cycle.

Reversing the process is the same, but using the "inverse" of the permutation. The inverse inv of a permutation perm, is the permutation such that inv[perm[i]] == i for each i. You can either compute the inverse and use the exact code above, or you can use code similar to the above, except move the elements in the opposite direction along each cycle.

所有这一切的替代方案是，由于您自己实现了 Fisher-Yates - 当您运行 Fisher-Yates 时，对于您执行的每次交换，都会记录在vector<pair<size_t,size_t>>. 那么你就不用担心周期的问题了。您可以通过应用相同的交换序列将排列应用于向量。您可以通过应用相反的交换顺序来反转排列。