随机置换 [英] Random Permutations
问题描述
我有麻烦找出随机洗牌的的std ::向量元素的体面的方式和一些操作，恢复原来的订单。我知道，这应该是一个相当琐碎的算法，但我想我太累了......
由于我不得不使用定制的随机数生成器类，我想我不能使用的std :: random_shuffle ，这不利于无论如何，因为我还需要preserve原来的顺序。所以，我的方法是创建一个的std ::地图用作原来的位置和随机的人之间的映射，是这样的：
的std ::地图＆LT;为unsigned int，unsigned int类型＆GT; getRandomPermutation（const的无符号整型和放大器; numberOfElements）
{
的std ::地图＆LT;为unsigned int，unsigned int类型＆GT;排列;
//填充地图
为（unsigned int类型I = 0; I＆LT; numberOfElements;我++）
{
排列[我] =我;
}
//随机它
为（unsigned int类型I = 0; I＆LT; numberOfElements;我++）
{
//生成在区间的随机数[0，numberOfElements）
无符号长randomValue = GetRandomInteger（numberOfElements - 1U）;
//破碎掉期执行
//排列[I] = randomValue;
//排列[randomValue] =我;
//用这个来代替：
的std ::交换（排列[I]，排列[randomValue]）;
}
返回置换;
}
我不知道，上面的算法是正确执行的随机排列，所以任何改善是值得欢迎的。
现在，这里是如何我已经成功地利用这个排列图：
的std ::矢量＆lt; BigInteger的＆GT; doStuff（常量的std ::矢量＆lt; BigInteger的＆GT;＆安培;输入）
{
///置换随机顺序的值
的std ::地图＆LT;为unsigned int，unsigned int类型＆GT;置换= getRandomPermutation（的static_cast＆LT; unsigned int类型＆GT;（input.size（）））;
的std ::矢量＆lt; BigInteger的＆GT;温度;
//置换值
为（unsigned int类型I = 0; I＆LT;的static_cast＆LT; unsigned int类型＆GT;（input.size（））; ++ I）
{
temp.push_back（输入[排列[I]）;
}
//做的东西，各种与温度
///反向排列
的std ::矢量＆lt; BigInteger的＆GT;输出;
为（unsigned int类型I = 0; I＆LT;的static_cast＆LT; unsigned int类型＆GT;（input.size（））; ++ I）
{
output.push_back（TEMP [排列[I]）;
}
返回输出;
}
有个声音告诉我，我应该可以只使用一个的std ::矢量＆lt; BigInteger的＆GT; 这个算法，但是，现在，我实在不明白出的最优解。老实说，我真的不关心数据的输入，所以我甚至可以让它非常量，覆盖它，并跳过创建它的一个副本，但问题是如何实现的算法？
如果我这样做，我结束了拍摄自己的脚，对吧？ ：）
的（unsigned int类型I = 0; I＆LT;的static_cast＆LT; unsigned int类型＆GT;（input.size（））; ++ I）
{
BigInteger的AUX输入= [I]
输入[I] =输入[排列[I]];
输入[排列[I] =辅助;
}
编辑：继史蒂夫的言论有关使用费舍尔 - 耶茨的洗牌，我改变了我的 getRandomPermutation 相应的功能：
的std ::地图＆LT;为unsigned int，unsigned int类型＆GT; getRandomPermutation（const的无符号整型和放大器; numberOfElements）
{
的std ::地图＆LT;为unsigned int，unsigned int类型＆GT;排列;
//填充地图
为（unsigned int类型I = 0; I＆LT; numberOfElements;我++）
{
排列[我] =我;
}
//随机它
为（unsigned int类型I = numberOfElements - 1; I＆GT; 0; --i）
{
//生成在区间的随机数[0，numberOfElements）
无符号长randomValue = GetRandomInteger（我）;
的std ::交换（排列[I]，排列[randomValue]）;
}
返回置换;
}
如果你正在寻找在你的code的具体错误：
排列[I] = randomValue;
排列[randomValue] =我;
是错误的。注意，一旦你完成后，每个值并不一定出现一次地图的价值之一。因此，这不是一个排列，更别说是均匀分布的随机之一。
正确的方法来生成一个随机的排列是托尼说的话，可以使用的std :: random_shuffle 在载体上，最初重新presents身份置换。或者，如果你想知道一个洗牌的正确执行，查找费雪耶茨。一般情况下，任何方法，使 N 随机选择从均匀 0 ... N-1 是注定要失败的，因为这意味着它具有ñ^ N 可能的话，可以运行的方式。但也有 N！的 N个可能的排列项和ñ^ N 一般不整除 N！。因此，它是不可能的每个排列成为同等数量的随机选择的结果，即分布不均匀。
问题是如何实现的算法？
所以，你有你的排列，并且要重新排序就地输入的元素，根据该置换。
要知道，关键的一点是，每一个置换是循环的成分。这就是说，如果反复遵循一个给定的起点置换，你回来，你开始（而这条道路是它的出发点所属的周期）。可能有不止一个这样的周期在给定的置换，而如果排列[I] ==我一些我，然后循环我长度为1。
的周期是所有不相交的，也就是说每个元素出现在一个循环。因为周期不妨碍对方，我们可以通过将每个周期应用排列，我们可以做的周期以任何顺序。因此，对于每个指数我我们需要：
- 检查我们是否已经做
我。如果是这样，就移动到下一个索引。 - 设置
电流= I - 交换
指数[现行]与指数[排列[现行]]。因此，指数[现行]设置为正确的值（在周期的下一个元素），而其原来的值是推着沿着循环。 - 标记
电流为完成 - 如果
permutuation [现行]是我，我们已经完成了循环。如此循环的第一值结束了在以前由循环的最后一个元素，这是对所占据的位置。移动到下一个指标。 - 设置
电流=排列[现行]并返回到交换一步。
根据所涉及，就可以在掉期优化类型 - 这可能是更好的复制/移动到一个临时变量，每个周期的开始，然后做一个复制/移动交换，而不是在每一步循环，最后复制/移动临时到循环结束
逆转过程是相同的，但是使用置换的逆。置换烫发的逆 INV ，是置换，使得 INV [烫发[我]] ==我每个我。你可以计算出逆及使用上面的确切code，也可以使用code与上述类似，但移动元素沿着每个周期相反的方向。
这是替换了这一切，因为你执行费雪耶茨自己 - 因为你正在运行费雪耶茨，为每个交换执行记录这两个指数交换了矢量＆lt;对＆LT;为size_t ，为size_t＆GT;＆GT; 。然后，你不必担心周期。您可以通过将互换的相同序列应用置换来的载体。您可以通过应用交换的相反的顺序颠倒排列。
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...
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;
}
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;
}
EDIT: 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.
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]withindex[permutation[current]]. Soindex[current]is set to its correct value (the next element in the cycle), and its old value is "pushed" forward along the cycle. - mark
currentas "done" - if
permutuation[current]isi, 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.
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屋！
