Heim >Backend-Entwicklung >Python-Tutorial >Verwendung von Python zur Implementierung der laufenden Schritte des Mischalgorithmus

Verwendung von Python zur Implementierung der laufenden Schritte des Mischalgorithmus

王林
王林nach vorne
2024-01-23 23:24:101338Durchsuche

洗牌算法运行规则 Python实现洗牌算法

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

洗牌算法是如何运行的

给定的数组是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

Das obige ist der detaillierte Inhalt vonVerwendung von Python zur Implementierung der laufenden Schritte des Mischalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Dieser Artikel ist reproduziert unter:163.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen

In Verbindung stehende Artikel

Mehr sehen