5

我很难找到一种体面的方法来随机改组中的元素，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;
}
4

4 回答 4

4

如果您要“随机化”一个包含 n 个元素的向量，您可以创建另一个std::vector<size_t> index(n)， set index[x] = xfor 0 <= x < n，然后 shuffle 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

于 2012-06-22T01:42:28.690 回答
2

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

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

是错的。请注意，完成后，每个值不一定会在地图的值中出现一次。所以这不是一个排列，更不用说一个均匀分布的随机排列了。

生成随机排列的正确方法是托尼所说的，std::random_shuffle在最初表示恒等排列的向量上使用。或者，如果您想知道如何正确执行随机播放，请查看“Fisher-Yates”。一般来说，任何N从随机选择统一的方法0 .. N-1都注定要失败，因为这意味着它有N^N可能运行的方式。但是有可能的项目N!排列，并且通常不能被 整除。因此，每个排列不可能是相同数量的随机选择的结果，即分布不均匀。NN^NN!

问题是如何实现算法？

因此，您有您的排列，并且您想根据该排列重新排序input原位的元素。

要知道的关键是每个排列都是“循环”的组合。也就是说，如果你从一个给定的起点重复地遵循排列，你就会回到你开始的地方（这条路径就是那个起点所属的循环）。在给定的排列中可能有多个这样的循环，如果permutation[i] == i对于某些i，则循环的i长度为 1。

循环都是不相交的，也就是说每个元素恰好出现在一个循环中。因为循环不会相互“干扰”，所以我们可以通过应用每个循环来应用排列，并且我们可以按任何顺序执行循环。因此，对于每个索引，i我们需要：

  • 检查我们是否已经完成i。如果是这样，请转到下一个索引。
  • 放current = i
  • index[current]与交换index[permutation[current]]。Soindex[current]被设置为它的正确值（循环中的下一个元素），并且它的旧值沿着循环向前“推”。
  • 标记current为“完成”
  • 如果permutuation[current]是i，我们已经完成了循环。所以循环的第一个值最终出现在循环的最后一个元素之前占据的位置，这是正确的。继续下一个索引。
  • 设置current = permutation[current]并返回交换步骤。

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

反转过程是相同的，但使用排列的“逆”。inv排列的逆perm，是排列使得inv[perm[i]] == i对于 each i。您可以计算逆并使用上面的确切代码，也可以使用类似于上面的代码，除了沿每个循环沿相反方向移动元素。

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

于 2012-06-22T02:00:32.883 回答
1

请注意，根据您的应用程序，如果您有一个真正均匀分布的排列很重要，那么您不能使用任何算法多次调用典型的伪随机数生成器。

原因是大多数伪随机数生成器，例如 clib 中的那个，都是线性同余的。那些有一个弱点，他们会生成在平面上聚集的数字 - 所以你的排列不会完全均匀分布。使用更高质量的生成器应该可以解决这个问题。

见http://en.wikipedia.org/wiki/Linear_congruential_generator

或者，您可以在 0..(n!-1) 范围内生成一个随机数，并将其传递给 unrank 函数进行排列。对于足够小的 n，您可以存储它们并获得恒定时间算法，但如果 n 太大，则最好的 unrank 函数是 O(n)。无论如何，应用得到的排列将是 O(n)。

于 2013-02-27T16:03:08.207 回答
0

给定一个有序的元素序列，a,b,c,d,e您首先创建一个新的索引序列：X=(0,a),(1,b),(2,c),(3,d),(4,e). 然后，您随机打乱该序列并获取每对的第二个元素以获得随机序列。要恢复原始序列，您可以X使用每对的第一个元素对集合进行递增排序。

于 2012-06-22T01:15:55.303 回答