Using Python to implement the running steps of the shuffling algorithm

给定一个数组，编写一个程序来生成数组元素的随机排列，这个问题也被称为“洗牌”或“随机化给定的数组”。洗牌算法中数组元素的每种排列的可能性都应该是相同的。

洗牌算法是如何运行的

给定的数组是arr[]，一个简单的解决方法是创建一个辅助数组temp[]，它最初是arr[]的副本。从temp[]中随机选择一个元素，将随机选择的元素复制到arr[0]，然后从temp[]中删除选择的元素。重复相同的过程n次并继续将元素复制到arr[1]、arr[2]、...。该解决方案的时间复杂度为O(n^2)。

Fisher-Yates shuffle算法的工作时间复杂度为O(n)。这里的假设是，我们得到一个函数rand()，它在O(1)时间内生成一个随机数。这个想法是从最后一个元素开始，并将其与整个数组（包括最后一个）中随机选择的元素交换。现在考虑从0到n-2的数组（大小减1），重复这个过程直到我们找到第一个元素。

下面是详细的算法：

对包含n个元素（索引0..n-1）的数组a进行洗牌

for i from n-1 downto 1 do
j=random integer with 0<=j<=i
exchange a[j]and a<i>

Python实现洗牌算法

from random import randint
def randomize(arr,n):
for i in range(n-1,0,-1):
j=randint(0,i+1)
arr<i>,arr[j]=arr[j],arr<i>
return arr
arr=[1,2,3,4,5,6,7,8]
n=len(arr)
print(randomize(arr,n))
输出结果：7 8 4 6 3 1 2 5

The above is the detailed content of Using Python to implement the running steps of the shuffling algorithm. For more information, please follow other related articles on the PHP Chinese website!