python实现洗牌算法_洗牌算法（等概率随机排列数
组，Fisher–Yates shuf。。。
在随机梯度下降(stochastic gradient
descent)中，因为要多次重复再训练集上进⾏，所以每次打乱训练集的顺序可以⽤洗牌算法。当然还有其他。
///
前⼏天看了酷壳上的⼀篇⽂章如何测试洗牌程序，之后仔细看了Wikipedia对Fisher–Yates
shuffle算法的介绍，这⾥简单的总结⼀下，基本是翻译Wikipedia。
Fisher and Yates’ original method
该算法最初是1938年由Ronald A. Fisher和Frank Yates在《Statistical tables for
biological, agricultural and medical
research》⼀书中描述，算法⽣成1-N个数的随机排列的过程如下：
原始数组中有数字1到N
设原始数组未被标记的数字个数为k，⽣成⼀个1到k之间的随机数
取出原始数组未被标记数字中的第k个，将其标记并插⼊到新的排列数组尾端。
重复过程2直到原始数组中没有未被标记的数字
过程3中⽣成的新数组就是⼀个对原始数组的随机排列
该算法可以理解为已知有n个元素，先从n个元素中任选⼀个，放⼊新空间的第⼀个位置，然后再从剩下的n-1个元素中任选⼀个，放⼊第⼆个位置，依此类推。算法在过程3查未被标记的第k个数字有很多重复操作，导致算法效率并不⾼，总的时间复杂度为O(N2
)，空间复杂度为O(N)。算法的python实现如下所⽰：
1
2
3
4
5
6
7
8
9
10
11
12
13
from random import randomdef FisherYateOldShullfe(items):ret = [None] * len(items)for i in reversed(r
ange(0, len(items))):j = int(random() * (i+1))ret[i] = items[j]del items[j]return retif __name__ == '__main__':srclist = [n for n in range(10)]print FisherYateOldShullfe(srclist)
Modern version of the Fisher–Yates shuffle
改进版的Fisher–Yates shuffle算法是1964年Richard Durstenfeld在
Communications of the ACM volume 7, issue 7中⾸次提出，相⽐于原始Fisher-Yates
shuffle最⼤的改进是不需要在步骤3中重复的数未被标记的数字，该算法不再将标记过的数字移动到⼀个新数组的尾端，⽽是将随机数选出的数字与排在最
python 定义数组
后位置的未标记数字进⾏交换。算法在python下的实现如下所⽰：
from random import random
def FisherYatesShuffle(items):
for i in reversed(range(1, len(items))):
j = int(random() * (i+1))
items[i], items[j] = items[j], items[i]
if __name__ == '__main__':
srclist = [n for n in range(10)]
FisherYatesShuffle(srclist)
print srclist
该算法同样可以理解成为这样的过程：从1到n个数字中依次随机抽取⼀个数字，并放到⼀个新序列的尾端(该算法通过互换数字实现)，逐渐形成⼀个新的
序列。计算⼀下概率：如果某个元素被放⼊第i(1≤i≤n)个位置，就必须是在前 i-1 次选取中都没有选到它，并且第 i
次恰好选中它。其概率为：
算法中只有⼀个从1到N-1的循环，循环内操作为常数步，因⽽算法总的时间复杂度为O(N)，空间复杂度为O(1)。
Inside-out algorithm
Fisher-Yates
shuffle是⼀种在原地交换的⽣成过程，即给定⼀个序列，算法在这个序列本⾝的存储空间进⾏操作。与这种in-place的⽅式不同，inside-
out针对给定序列，会⽣成该序列随机排列的⼀个副本。这种⽅法有利于对长度较⼤的序列进⾏随机排列。
Inside-out算法的基本思想是从前向后扫描，依次增加i，每⼀步操作中将新数组位置i的数字更新为原始数组位置i的数字，然后在新数组中将位置i
和随机选出的位置j(0≤j≤i)交换数字。算法亦可以理解为现将原始数组完全复制到新数组，然后新数组位置i(i from 1 to
n-1)依次和随机位置j交换数字。算法的python实现如下：
1
2
3
4
6
7
8
9
10
11
12
13
14
from random import randomdef insideout(source):ret = [None] * len(source)ret[0] = source[0]for i in range(1, len(source)):j = int(random() * (i+1))ret[i] = ret[j]ret[j] = source[i]return retif __name__ == '__main__':srclist = [n for n in range(10)]print insideout(srclist)
对于这个算法，我们分析可以出现多少种不同的排列数，从$i=1$开始，每⼀次交换都可以衍⽣出$(i+1)$倍的排列数，因⽽总的排列⽅案数如下
图。在随机函数完全随机的情况下每⼀种排列都是等概率出现的，因⽽这种算法得到的是⼀个随机排序。它的时间复杂度和空间复杂度都是O(N)。
该算法有⼀个优点就是可以通过不断读取原始数组的下⼀个元素同时使新的排列数组长度加⼀，进⽽⽣成⼀个随机排列，即可以对长度未知的序列进⾏随机排列。实现的伪代码如下：
1
2
3
4
5
6
7
DataAvailablej
另⼀种想法
对n个元素的随机排序对应于这n个元素全排列中的⼀种，所以有这样⼀种⽅法求随机排序：求n个元素的随机排列，给定⼀个随机数
k(1≤k≤n!)，
取出n!个全排列中的第k个即是⼀种随机排序。于是需要解决2个问题：⼀是在⼀个⾜够⼤的范围内求随机数；另外是实现⼀种是在n!个全排列中求第k个全排
列的⽅法。第⼀个问题很古⽼，有⼈说随机数的最⼤范围决定于随即种⼦的⼤⼩，我有⼀种想法是对分段求随机数，⽐如需要求最⼤范围为N的随机数，那么可以对
N进⾏M进制分解，分别求M进制下的每⼀位的随机数，最后合成⼀个⼤的随机数；⽽第⼆个问题就⽐较容易了，有很多全排列⽣成算法，通过“原排
列”->“原中介数”->“新中介数”->“新排列”的过程，可以很⽅便的求出第k个全排列。
1，缘起
最近⼯作上遇到⼀个问题，即将⼀组数据，⽐如[A,B,C,D,E]其中的两个B,E按随机排列，其他的仍在原来的位置：
原始数组：[A,B,C,D,E]
随机字母：[B,D]
可能结果：[A,B,C,D,E],[A,D,C,B,E]
在解决这个问题的过程中，需要解决的⼀个问题是，怎么样让⼀个数组随机排序？上⽹⼀查，这也是计算机科学基础问题，也称之为洗牌算法(Shuffle
Algorithm)。
2，问题及解决
2.1，问题
很简单：给定⼀个数组，将其中的元素随机排列。⽐如给定数组arry=>[1,2,3,4,5]。有A5-5种结果即5!=120种结果
2.2，解决
也很简单，如果⽤⽩话来说就是：
a，选中第1个元素，将其与n个元素中的任意⼀个交换(包括第1个元素⾃⼰)。这时排序后的第1个元素已经确定。
b，选中第2个元素，将其与n-1个元素中作任意⼀个交换(包括第2个元素⾃⼰)。
c，重复上⾯步骤，直到剩1个元素为⽌。
3.3，代码
知道其算法了，实现就简单了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
17
18
///
///
Randomize the list elements using Fisher–Yates shuffle algorithm
///
///
elements type
///
public static
void Shuffle(this
IList list)
{
Random
rng = new Random();
int
n = list.Count;
while
(n > 1)
{
n--;
int
k = rng.Next(n + 1);
T
value = list[k];
list[k]
= list[n];
list[n]
= value;
}
}
3.4，其它
该算法复杂度为O(n)，且⽆偏差，各个元素随机概率相等。确实是⼀个好算法:)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。