How to randomize a list to meet conditions

Question

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?

Answer 1

Only your second condition is necessary: if all the elements are not in their original position, the order will be different. Rather than looking through all possible permutations and choosing one randomly, (which is even more inefficient than shuffling until your condition is met), you can generate a list to your spec.

Your list has 8 elements, which means that each position can have one of 7 options (all but the element currently there). This is equivalent to placing ones in a matrix of zeros such that no one occupies the same row or column as another (normal shuffling), but with the restriction that elements can not be on the main diagonal, which complicates things.

You can implement a Fisher-Yates-like shuffle which includes the restrictions. This will randomize your list without having to sift through vast numbers of permutations.

It's probably easier to work with indices to avoid placement collisions, rather than looking up the position of each element as it's swapped.

n = len(lst)
ind = list(range(n))
for i in range(n - 1):
    # Case 1: Swap out necessary, conflictonly with self
    if ind[i] == i:
        swap_ind = random.randrange(i + 1, n)
    else:
        try:
            # Case 2: swap might cause conflict
            ind_of_i = ind.index(i, i + 1)
            swap_ind = random.randrange(i, n - 1)
            if swap_ind >= ind_of_i:
                swap_ind += 1
        except ValueError:
            # Case 3: no conflict, full range available
            swap_ind = random.randrange(i, n)
    ind[i], ind[swap_ind] = ind[swap_ind], ind[i]

You now have a list of shuffled indices, none of which has ended up in the same spot it started in. You can arrange the input list with

result = [lst[i] for i in ind]

Keep in mind that the implementation of the check ind[swap_ind] is very inefficient in time, and effectively negates the benefit of sorting indices instead of the actual values. You can replace it with a second list that maintains an inverse lookup table of index to position, and swap that along with ind. The result will be O(1) lookup and twice as much memory utilization.

I am not sure how uniform the result will be over the space of all available permutations, but I suspect that (a) it is probably good enough for what you are looking for, and (b) can be easily modified to be more uniform if necessary/possible.

Answer 2

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

Answer 3

You can use this list comprehension:

result = [i for i in permutations if any(a != b for a, b in zip(i, lst))]

We are any(a == b for a, b in zip(i, lst) testing if any matching item on same index in lst and permutaion in this line.