Given a list / ordered collection is there a way to produce a guaranteed shuffling / reordering of its members (meaning that no element is in the same position as before), without resorting to trial and error? I am using python here, but this applies to any language with such structures, obviously.
E.g., if I have a list l = [1, 2, 3, 4, 5] and randomly shuffle it:
import random
for _ in range(5):
random.shuffle([1,2,3,4,5]);
print(l)
[1, 2, 3, 5, 4] # 1,2,3
[2, 4, 3, 1, 5] # 3, 5
[2, 1, 4, 5, 3] # OK!
[2, 5, 3, 1, 4] # 3
[5, 3, 4, 2, 1] # OK!
you can see that only the 3rd and 4th output all elements are indeed in different positions in the list, while in the other cases I have written the list elements that remain in the same position.
Somewhat more considerate approaches like leaving out the offending element at each position:
l=[1,2,3,4,5]
shuffled = []
for i in l:
sample_from = [x for x in l if x not in shuffled + [i]]
try:
shuffled.append(random.sample(sample_from, 1)[0])
except:
print("Attempted to sample from", sample_from)
break
print("Shuffled portion:", shuffled)
can lead to errors with no viable solution left, such as:
Shuffled portion: [2]
Shuffled portion: [2, 4]
Shuffled portion: [2, 4, 1]
Shuffled portion: [2, 4, 1, 3]
Attempted to sample from []
Where 5 happened to be left for the end, with no alternative position to the original. I guess when arriving at this position I can swap the remaining 5 with any element in the shuffled list.
Is there however any other simpler, prettier and algorithmic way to achieve this without such manual hacks? Thanks!
To generate a derangement, you can use the Fisher-Yates shuffling algorithm and just exclude the current index from consideration when selecting an index to swap with (i.e., do not allow swapping an element with itself).