python - 如何随机化列表以满足条件

Question

我想生成一个列表的 n 个随机版本，这样每次随机化的顺序都与之前的不同，并且每个元素的位置也必须与之前列表中的位置不同。我已经生成了列表的所有可能排列的列表，但我一直困惑于如何选择符合我的条件的子列表。我想也许列表理解可以工作，但不确定如何完成它。

# constraints: n <= 12

lst = ['John', 'William', 'Michael', 'Victor', 'Tom', 'Charley', 'Patrick', 'David']

permutations = list(itertools.permutations(lst))

randomized_lists = [i for i in permutations if <conditions>]

有什么想法可以做到这一点吗？另外，是否有更好(更有效)的方法来解决该问题？

Answer 1

这可以通过修改 Fisher–Yates shuffle 来完成避免与自身交换一项的算法。也就是说，对于 k 处的每个项目(其中 k 从 0 开始)，而不是在 [0, k] 中选择随机项目或[k, n - 1](包括k)，在[0, k)或(k, n - 1](不包括k)，并将k处的项目与随机项目交换。

<小时/>

下面的方法实现了这个想法:

import random

def shuffle_diff_pos(list):
  """ Returns a shuffled list in which 
      each item moves to a different position. """
  list=[x for x in list]
  if len(list)>=2:
    i=len(list)-1
    while i>0:
      k=random.randint(0, i-1)
      tmp=list[i];list[i]=list[k];list[k]=tmp
      i-=1
  return list

lst = ['John', 'William', 'Michael', 'Victor', 'Tom', 'Charley', 'Patrick', 'David']
randomized_lists = [shuffle_diff_pos(lst) for _ in range(12)]