shuffling a list with restrictions in Python

Question

I have a problem with randomizing a list with restrictions in Python (3). I have seen a few other questions relating to this, but none of them really seem to solve my problem. I'm a beginner, so any help is much appreciated!

I'm designing an experiment using two types of stimuli: shapes and colors (four of each). I need to generate permutations of all 16 combinations, which I have done with random.shuffle-function:

import random

# letters are shapes, numbers are colors
x=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"]

random.shuffle(x)

So far so good. However, I want to avoid a shape (letter) or color (number) to appear two times in succession in my result (e.g. "a2" followed by "a4", or "c2" followed by "a2").

Is there a way to make such a restriction?
Thanks in advance!

Cecum

So far so good? random.shuffle(x) returns None because it shuffles x in place. Therefore, result will be None. – Dinnerware

This seems like a graph problem. Every node has an edge pointing to all other nodes except for the ones with the same shape or color (so (n-1)^2 edges per node). And then you want a random traversal that hits every vertex exactly once--a Hamiltonian path I think. – Blouse

@Dinnerware Oh right, thanks for pointing that out. I have corrected the example. – Cecum

Answer 1

Something like this should give a reasonable answer in a reasonable time

import random
while 1:
    choices = ["a1", "a2","a3","b1","b2","b3","c1","c2","c3"]

    shuffle = []

    last = ""

    while choices:
        l = choices
        if last:
            l = [x for x in l if x[0] != last[0] and x[1] != last[1]]
        if not l:
            #no valid solution
            break 
        newEl = random.choice(l)
        last = newEl
        shuffle.append(newEl)
        choices.remove(newEl)
    if not choices:
        print(shuffle)
        break

Rugging

Thanks for the downvote ;-) if you have a better solution you are free to tell you know – Rugging

I'm curious about the downvote too. I tried your solution out and it seems to work. – Blouse

Thanks a lot, Daniele! This is exactly what I was looking for. – Cecum

Answer 2

One way to handle this might be to have two lists one of shapes and one of colors. Shuffle each list individually. Now intermix the two lists. Since each list was built randomly, the mixed list is random as well, but you do not have any two entries together.

Note that using zip, you will actually get sets of pairs which will enable you to handle your test by getting each pair from the result.

In this particular case each shape is a member of the list shapes while each color is a member of the list colors

shapes = ['a', 'b', 'c', 'd']
colors = ['1', '2', '3', '4']
zip(shapes, colors)
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4')]

This gives us each individual shuffle rather than generating all 16 possibilities at once and then shuffling them. This might enable you to generate your test better.

If you want to ensure that two sets of lists do not have the same color or shape in the same position as the previous group of four, then you can test for that after the shuffle against the previous setting.

testing = True
while testing:
    newcolors = colors
    random.shuffle(newcolors)
    # perform the test that you want to make get testresult True or False
    if testresult:
        colors = newcolors
        testing = False

This will keep shuffling until testresult becomes True and discard all invalid results from random.shuffle()

Statolatry

Answer 3

I doubt this is the best way, but it is a way of doing this. If you think about your input as a matrix like this

a1, b1, c1, d1
a2, b2, c2, d2
a3, b3, c3, d3
a4, b4, c4, d4

Then you're goal becomes choosing an random index at each iteration such that the new index is not in the same row nor the same column of the matrix as the previous index and such that the new element has not been chosen before. Putting that into code naively, it becomes

import random
shapes_and_colors=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"]
nRows = 4
nCols = 4
inds = [(x,y) for x in range(nRows) for y in range(nCols)]
def make_random(someArr):
    toRet = []
    n = len(someArr)
    for i in range(n):
        possible = [thing for thing in someArr if thing not in toRet]
        prev = poss = None
        while poss is None:
            next_val = random.choice(possible)
            if next_val == prev:
                #failed so try again
                return make_random(someArr)
            if not toRet or (next_val[0] != toRet[-1][0] and next_val[1] != toRet[-1][1]):
                poss = next_val 
            prev = next_val
        toRet += poss,
    return toRet



ans= [thing for thing in make_random(shapes_and_colors)]
print ans

Outputs After A Couple Runs

['c3', 'd4', 'c1', 'd3', 'b1', 'a4', 'b3', 'c4', 'a3', 'b2', 'a1', 'c2', 'd1', 'a2', 'b4', 'd2']
['d4', 'b3', 'c1', 'a4', 'b2', 'c4', 'd3', 'a1', 'c3', 'a2', 'b4', 'd2', 'a3', 'b1', 'c2', 'd1']

Disclaimer

Since this is a totally naive approach, it sometimes gets stuck! So suppose the last two indices remaining are [(2, 2), (3, 2)]. Then, there is no possible way for the algorithm to proceed without breaking the restrictions. Right now, I'm handling it with a recursive call, which isn't ideal.

Blouse

Answer 4

While you could technically use itertools.permutations (I tried that first), that would take far too long.

Use this to generate random sequences without items that share a property following eachother:

from random import shuffle

x=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"]

def pairwise(some_list):
    one = iter(some_list)
    two = iter(some_list)
    next(two)
    for first, second in zip(one, two):
        yield first, second

while True:
    shuffle(x)
    for first, second in pairwise(x):
        if first[0] == second[0] or first[1] == second[1]:
            break
    else: # nobreak:
        print(x)

Direct

Answer 5

You can build the list piece wise by comparing a random option to the last value.

import random

options = ["a1", "a2", "a3", "a4", "b1", "b2", "b3", "b4",
           "c1", "c2", "c3", "c4", "d1", "d2", "d3", "d4"]

j = random.choice(range(len(options)))
result = [options.pop(j)]
last = result[-1]
while options:
    j = random.choice(range(len(options)))
    candidate = options[j]
    if all([x != y for x, y in zip(last, candidate)]):
        result.append(options.pop(j))
        last = result[-1]

Rurik