随机置换(Random Permutations)

2019-07-30 02:20发布

站内文章 / 前沿技术

818 0

老娘就宠你

女 | 书童

私信

我无法找出随机洗牌在元素的体面的方式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;
}

编辑：继史蒂夫的有关使用“费舍尔-耶茨的”洗牌的话，我改变了我的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;

是错的。注意，一旦你完成后，每个值不一定恰好出现一次地图的价值观之一。因此，这不是一个排列，更别说是均匀分布的随机一个。

正确的方式产生的随机排列是托尼说什么，使用std::random_shuffle在最初代表身份置换的载体。或者，如果你想知道如何洗牌正确执行，查找“费雪耶茨”。一般情况下，使任何方法N随机选择均匀地从0 .. N-1是注定要失败，因为这意味着它有N^N它可以运行可能的方式。但也有N! 可能的排列N项目， N^N一般不整除N! 。因此，它是不可能的每个置换为相等数目的随机选择的结果，即，分布是不均匀的。

问题是如何实现的算法？

所以，你有你的置换，并要重新排序的元素input原地的，根据该置换。

要知道关键的一点是，每个排列是“循环”的成分。也就是说，如果你反复遵循从给定起点置换，你回来你开始的地方（这个路径是到该起点所属的周期）。可以存在多于一个这样的周期在给定的排列，并且如果permutation[i] == i一些i ，然后循环i具有长度1。

该周期是所有不相交的，也就是说每个元素出现在正好一个周期。由于周期不“干扰”对方，我们可以通过将每个周期应用排列，我们可以以任何顺序做循环。因此，对于每个索引i ，我们需要：

检查我们是否已经做了i 。如果是这样，移动到下一个索引。
设定current = i
交换index[current]与index[permutation[current]] 所以index[current]被设定为正确的值（在循环中的下一个元素），和它的旧值“推”向前沿着循环。
马克current为“完成”
如果permutuation[current]是i ，我们已经完成了循环。如此循环的第一个值在原来由循环的最后一个元素，这是对占领的点结束。移动到下一个索引。
设定current = permutation[current] ，并返回到交换步骤。

根据所涉及的类型，可以优化周围的掉期 - 这可能是更好的移动复制/到一个临时变量和每个周期的开始，然后进行复制/移动，而不是交换的在循环的每一步，并终于复制/移动临时的周期结束。

倒车过程是相同的，但是使用置换的“逆”。逆inv的置换的perm ，是置换使得inv[perm[i]] == i每个i 。你可以计算逆和使用上面的确切的代码，也可以使用与上述类似的代码，除在沿着每个循环中相反的方向移动的元素。

对所有的选择，因为你实现费希尔-耶茨自己-因为你正在运行费雪耶茨，每个交换执行记录这两个指数在交换vector<pair<size_t,size_t>> 。然后，你不必担心周期。您可以通过应用互换的相同序列应用置换的载体。您可以通过应用交换的相反的顺序颠倒排列。

Answer 2:

如果您是“随机化” n个元素的向量，可以创建另一个std::vector<size_t> index(n)设定index[x] = x为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