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

问题描述

我想生成一个列表的n个随机版本，以使每次随机化的顺序都不同于之前的顺序，而且每个元素的位置都必须与之前列表中的位置不同.我已经生成了列表的所有可能排列的列表，但是我在如何选择符合我的条件的子列表上遇到了麻烦.我在想也许列表理解可以奏效，但不确定如何完成.

I would like to generate n randomized versions of a list such that with each randomization the ordering is different from the one before and also each element must have a different position than in the list before. I have generated a list of all possible permutations of the list but I am stuck on how to select the sub-lists that match my conditions. I am thinking maybe a list comprehension could work but not sure how to complete it.

# 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>]

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

Any ideas how this could be done? Also, is there a better (more efficient) approach to the problem?

推荐答案

这可以通过修改 Fisher– Yates随机播放算法可避免与自己交换一项.也就是说，对于 k 中的每个项目(其中 k 从0开始)，而不是选择[0, k]或[k, n - 1](包括k)中的随机项目，在[0, k)或(k, n - 1]中选择一个随机项目(不包括k)，然后将 k 中的项目与该随机项目交换.

This can be done by modifying the Fisher–Yates shuffle algorithm to avoid swapping one item with itself. That is, for each item at k (where k starts at 0), instead of choosing a random item in [0, k] or [k, n - 1] (including k), choose a random item in [0, k) or (k, n - 1] (excluding k), and swap the item at k with the random item.

以下方法实现了这个想法:

The following method implements this idea:

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)]

这篇关于如何将列表随机化以满足条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！