随机排列 [英] Random Permutations

问题描述

我遇到麻烦，找出一个不错的方式随机洗牌元素在 std :: vector ，并在一些操作后，恢复原始顺序。我知道这应该是一个相当琐碎的算法，但我想我太累了...

I am having trouble figuring out a decent way of randomly shuffling the elements in an std::vector and, after some operations, restoring the original order. I know that this should be a rather trivial algorithm, but I guess I'm too tired...

由于我被限制使用自定义随机数生成器类，我想我不能使用 std :: random_shuffle ，这不帮助反正，因为我还需要保留原来的顺序。所以，我的方法是创建一个 std :: map ，作为原始位置和随机的位置之间的映射，如下：

Since I am constrained to use a custom random number generator class, I guess I can't use std::random_shuffle, which doesn't help anyway, because I also need to preserve the original order. So, my approach was to create an std::map which serves as a mapping between the original positions and the random ones, like this:

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;
}

我不确定上述算法是一个随机置换的正确实现，所以欢迎任何改进。

I am not sure that the above algorithm is a proper implementation for a random permutation, so any improvements are welcome.

现在，这里是我已经设法使用这个排列映射：

Now, here is how I've managed to make use of this permutation map:

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> ，但是，现在，我只是无法找出最优解。老实说，我真的不在乎输入中的数据，所以我甚至可以使它非常量，覆盖它，并跳过创建它的副本，但问题是如何实现算法？

Something tells me that I should be able to use only one std::vector<BigInteger> for this algorithm, but, right now, I just can't figure out the optimal solution. Honestly, I don't really care about the data in input, so I could even make it non-const, overwrite it, and skip creating a copy of it, but the question is how to implement the algorithm?

如果我这样做，我最终在脚下拍摄自己，对吧？ ：）

If I do something like this, I end up shooting myself in the foot, right? :)

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;
}

---

按照Steve关于使用Fisher-Yates的说法，我改变了 getRandomPermutation 函数：

---

Following Steve's remark about using "Fisher-Yates" shuffle, I changed my getRandomPermutation function accordingly:

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;
}

推荐答案

您的代码中的具体错误：

If you're looking for specific errors in your code:

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

错误。请注意，一旦完成，每个值不一定在地图的值中显示一次。所以这不是一个排列，更不用说一个均匀分布的随机排列。

is wrong. Observe that once you're finished, each value does not necessarily appear exactly once among the values of the map. So it's not a permutation, let alone a uniformly-distributed random one.

正确的生成随机排列的方法是Tony说的，使用 std :: random_shuffle 在最初表示身份置换的向量上。或者如果你想知道如何正确执行shuffle，查找Fisher-Yates。一般来说，任何使 0 ... N-1 统一的 N 随机选择的方法注定会失败，因为这意味着它可以运行的 N ^ N 可能的方式。但是有 N！个可能的排列 N 项和 N ^ N 一般不能被 N！整除。因此，每个排列不可能是等量的随机选择的结果，即分布是不均匀的。

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?

所以，你有你的排列，你想重新排序<$ c $

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

要知道的关键是每个排列是一个循环的组合， 。也就是说，如果你从一个给定的起点重复地跟随排列，你回到你开始的地方（这条路径是起点所属的周期）。在给定排列中可以存在多于一个这样的循环，并且如果 permutation [i] == i 对于某些 i ，那么 i 的周期长度为1。

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.

周期都是不相交的，也就是说元素正好出现一个周期。因为循环不会彼此干扰，我们可以通过应用每个循环来应用置换，并且我们可以以任何顺序执行循环。因此，对于每个索引 i ，我们需要：

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:

• 检查我们是否已经完成 i 。


• 设置 current = i


• 交换 index [current] 与 index [permutation [current]] 。因此， index [current] 被设置为其正确的值（循环中的下一个元素），并且其旧值沿着循环向前推。
  
• 当前为已完成


• code>是 i ，我们已经完成了这个周期。因此，循环的第一个值结束于以前被循环的最后一个元素占据的位置，这是正确的。移至下一个索引。


• 设置 current = permutation [current] ，然后返回到交换步骤。
  

• 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.

根据所涉及的类型，你可以优化swap周围 - 最好复制/移动到临时变量和每个周期的开始，然后在循环的每个步骤执行复制/移动而不是交换，最后将临时复制/移动到循环结束。

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.

反转过程是相同的，但使用排列的逆。置换 perm 的反 inv 是排列，使得 inv [perm [i ]] == i 每个 i 。您可以计算逆，并使用上面的确切代码，或者您可以使用类似于上面的代码，除非沿着每个周期在相反方向移动元素。

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，对于每个交换你执行记录在向量< pair< size_t，size_t> > 。然后你不必担心周期。可以通过应用相同的交换序列将置换应用于向量。您可以通过应用互换序列来逆转排列。

An alternative to all that, since you implemented Fisher-Yates yourself -- as you're running Fisher-Yates, for each swap you perform record the two indices swapped in a vector<pair<size_t,size_t>>. Then you don't have to worry about cycles. You can apply the permutation to the vector by applying the same sequence of swaps. You can reverse the permutation by applying the reversed sequence of swaps.

这篇关于随机排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！