How To Lightly Shuffle A List In Python

August 21, 2024 Post a Comment

I have this issue where I would like to shuffle a list, but only do so slightly. Say, I want only a small number of elements to be moved. Is there a simple way to get this done? Ri

Solution 1:

to show what some of these solutions are doing I find it helps to run a monte-carlo algorithm many times and look at the distribution

first a tidied up version of @meta4's solution as it was the most fleshed out:

from random import randrange

defpartial_shuffle(l, factor=5):
    n = len(l)
    for _ inrange(factor):
        a, b = randrange(n), randrange(n)
        l[b], l[a] = l[a], l[b]

which we can run many times by doing:

import numpy as np

n = 8
orig = list(range(n))
occur = np.zeros((n, n), int)

for _ inrange(100000):
    x = orig[:]
    partial_shuffle(x,1)
    occur[orig,x] += 1

if we print out the occurrences table as percentages we get:

[[33.5  9.6  9.5  9.4  9.4  9.6  9.5  9.5]
 [ 9.6 33.2  9.7  9.5  9.6  9.6  9.4  9.4]
 [ 9.5  9.6 33.2  9.5  9.6  9.5  9.6  9.5]
 [ 9.5  9.3  9.6 33.4  9.5  9.5  9.5  9.6]
 [ 9.4  9.6  9.4  9.6 33.3  9.5  9.7  9.5]
 [ 9.6  9.5  9.6  9.6  9.4 33.3  9.5  9.6]
 [ 9.4  9.7  9.5  9.5  9.5  9.6 33.2  9.7]
 [ 9.5  9.5  9.6  9.5  9.7  9.5  9.6 33.2]]

each row represents the probability of the item moving to the column. in this case (when n=8) the algorithm will tend to leave elements where they were ~33% of the time, and then pick the remainder uniformly

I can then run (a tidied up) version of pjs's code with:

from random import gauss

orderliness = 2

occur = np.zeros((n, n), int)

for _ inrange(100000):
    x = sorted(orig, key=lambda i: gauss(i * orderliness, 1))
    occur[orig,x] += 1

which gives very different output:

[[91.9  7.9  0.1  0.   0.   0.   0.   0. ]
 [ 7.9 84.1  7.8  0.1  0.   0.   0.   0. ]
 [ 0.1  7.8 84.1  7.9  0.1  0.   0.   0. ]
 [ 0.   0.1  7.9 84.1  7.7  0.1  0.   0. ]
 [ 0.   0.   0.1  7.7 84.2  7.8  0.1  0. ]
 [ 0.   0.   0.   0.1  7.9 84.2  7.7  0.1]
 [ 0.   0.   0.   0.   0.1  7.7 84.2  7.9]
 [ 0.   0.   0.   0.   0.   0.1  7.9 91.9]]

i.e. items tend to remain close to where they started

this sort of table is great at detecting bias in the distribution, which there doesn't seem to be evidence of above. but, for example, with Artyom's solution (shuffle(x, lambda: random() / 5)) gives the following:

[[  0.   37.4   0.    0.    0.   16.7  23.8  22.1]
 [  0.    0.  100.    0.    0.    0.    0.    0. ]
 [  0.    0.    0.  100.    0.    0.    0.    0. ]
 [  0.    0.    0.    0.  100.    0.    0.    0. ]
 [  1.7   0.    0.    0.    0.   83.3  11.9   3. ]
 [  9.    7.4   0.    0.    0.    0.   64.2  19.4]
 [ 26.7  17.9   0.    0.    0.    0.    0.   55.5]
 [ 62.6  37.4   0.    0.    0.    0.    0.    0. ]]

which probably isn't what the OP wanted. the high probability off diagonal represents rotating the array by one element

Solution 2:

One interpretation is to strongly or weakly retain the initial ordering. The weakest retention would be a completely random shuffle, the strongest would be to not deviate from the initial ordering.

This can be accomplished by creating a tuple consisting of the original index scaled by a constant, plus some randomness, followed by the value. Sort the tuples, then iterate through to recover the original values in their new order. If the scale factor for the index is near zero, the new order will be random. If it's near 1, things will tend to strongly but not perfectly retain their original ordering. If it's larger, the result becomes unlikely to be shuffled.

import random

orderliness = 0.75

def tuplify(x, y):
    return (orderliness * y + random.gauss(0,1), x)

values = [i+1for i in range(20)]
print(values)
pairs = list(map(tuplify, values, range(len(values))))
pairs.sort()
partially_ordered_values = [p[1] for p inpairs]
print(partially_ordered_values)

This produces, for example:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]  # initial ordering
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 11, 14, 17, 16, 15, 18, 19, 20]  # weakly shuffled

Tendency to shuffle would be determined by the relative magnitudes of orderliness and the standard deviation in random.gauss().

Solution 3:

from random import randint

defpartial_shuffle(l, factor=5):
    for _ inrange(factor):
        a, b = randint(0, len(l)), randint(0, len(l)) # pick two random indexes
        l[b], l[a] = l[a], l[b] # swap the values at those indexesreturn l

This is the partial Fisher-Yates Shuffle @rossum recomended.

''.join(partial_shuffle(list('abcdefghijklmnopqrstuvwxyz'), 2))

This example yields "abcdefnhijklmgopqrsyuvwxtz", from one run, but will yield something else for a different run.

Solution 4:

One could also interpret slightly shuffled in the sense that there is a probability for shuffling elements at every step of the Fisher-Yates algorithm @rossum and @meta4 mentioned (instead of having a fixed number of elements shuffled).

defconditional_fy(l, p):
    """Shuffle elements of a list with a given probability

    Args:
        l: list
        p: shuffle probability
            (0: elements are never shuffled,
             1: elements are always shuffled)

    """assert0 <= p <= 1for i inrange(len(l) - 1, 0, -1):
        shuffle = random.random()
        if shuffle < p:
            j = random.randint(0, i - 1)
            l[i], l[j] = l[j], l[i]

Solution 5:

there is shuffle in the random module which takes 1 required argument list object and second random argument random takes a function object which returns float number from 0.0 to 1.0 you can write only new function which will return generally less than 0.5

import random

def rand():
    returnrandom.random() / 5

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(arr, random=rand)

OUTPUT

[9, 3, 4, 5, 6, 7, 8, 1, 2]

Python Developer