python, shuffle until lists are completely different

Question

I want to ask how to shuffle, maybe in a while loop, until all of the lists are completely different(like in sudoku)?

#lists you want to shuffle
s1 = [1, 2, 3, 4]
s2 = [1, 2, 3, 4]
s3 = [1, 2, 3, 3]
s4 = [1, 2, 3, 4]

def mid_generator():

    while True:
        random.shuffle(s1)
        random.shuffle(s2)
        random.shuffle(s3)
        random.shuffle(s4)

        # if ... all lists are different...:
            #break

    return s1, s2, s3, s4

So that the number is only one time in row i and column j:

s1 = [3, 1, 2, 4]
s2 = [4, 2, 1, 3]
s3 = [2, 4, 3, 1]
s4 = [1, 3, 4, 2]

If i try long if-Statements with if s1[0] != s2[0] .... the output is wrong. Maybe you could help me.

Are you trying to generate random [latin squares](https://en.wikipedia.org/wiki/Latin_square)? [That seems to be a hard problem](http://math.stackexchange.com/questions/63131/generate-random-latin-squares) if you want uniformity. — user2357112, Nov 24 '15 at 18:26
not directly. I want to get different lists like in the sudoku game. — FastBatteryCharger, Nov 24 '15 at 18:38
Sudoku grids are even more constrained, in ways your question doesn't even mention. You really need to say stuff like that in your question. — user2357112, Nov 24 '15 at 18:40

Galax · Accepted Answer · 2015-11-24T19:01:51.200

2

This is still an inefficient algorithm as it is based on your original code, but you could put the elements in each position into sets and check their length; len({1, 2, 3, 3}) will be 3, as there are only 3 unique elements:

import random

#lists you want to shuffle
s1 = [1, 2, 3, 4]
s2 = [1, 2, 3, 4]
s3 = [1, 2, 3, 4]
s4 = [1, 2, 3, 4]

def mid_generator():

    while True:
        random.shuffle(s1)
        random.shuffle(s2)
        random.shuffle(s3)
        random.shuffle(s4)

        test0 = {s1[0], s2[0], s3[0], s4[0]}
        test1 = {s1[1], s2[1], s3[1], s4[1]}
        test2 = {s1[2], s2[2], s3[2], s4[2]}
        test3 = {s1[3], s2[3], s3[3], s4[3]}

        if len(test0) == len(test1) == len(test2) == len(test3) == 4:
            break

    return s1, s2, s3, s4

Example interactive output:

>>> mid_generator()
([3, 4, 2, 1], [1, 2, 4, 3], [4, 3, 1, 2], [2, 1, 3, 4])

edited Nov 24 '15 at 19:01

answered Nov 24 '15 at 18:39

Galax

1,441
7
6

First of all, i thank you for your help! but i still have a problem, sometimes i generate a code with same numbers in a columns. – FastBatteryCharger Nov 24 '15 at 18:57
@MartinM what do you mean? The code above should work. – Galax Nov 24 '15 at 19:01
i replaced the code with the new code and now it works! You helped me alot!! – FastBatteryCharger Nov 24 '15 at 19:05
Glad to be able to help, it would be pretty easy to generalise this too for arbitrary length lists. – Galax Nov 24 '15 at 19:18

score 1 · Answer 2 · answered Nov 24 '15 at 19:14

It's pretty ugly, but if you are careful to correctly compare every column in each with every other for each list, the long list of and statements works fine too:

def mid_generator():

    while True:
        random.shuffle(s1)
        random.shuffle(s2)
        random.shuffle(s3)
        random.shuffle(s4)

        if (    s1[0] != s2[0] and s1[0] != s3[0] and s1[0] != s4[0]
            and s2[0] != s3[0] and s2[0] != s4[0] and s3[0] != s4[0]
            and s1[1] != s2[1] and s1[1] != s3[1] and s1[1] != s4[1]
            and s2[1] != s3[1] and s2[1] != s4[1] and s3[1] != s4[1]                
            and s1[2] != s2[2] and s1[2] != s3[2] and s1[2] != s4[2]
            and s2[2] != s3[2] and s2[2] != s4[2] and s3[2] != s4[2]                
            and s1[3] != s2[3] and s1[3] != s3[3] and s1[3] != s4[3]
            and s2[3] != s3[3] and s2[3] != s4[3] and s3[3] != s4[3]):
            break
    return s1, s2, s3, s4

Ah thank you again! I tried a long if statement too, but as you say, you have to be very careful and for me it is very confusing to work with long if statements. — FastBatteryCharger, Nov 24 '15 at 19:18
Yes even the version with the sets is a bit fragile, as it's easy to mistype one of the numbers. If you see how short the generalised version is you might think that that was the best approach all along ;) — Galax, Nov 24 '15 at 19:30

score 1 · Answer 3 · answered Nov 24 '15 at 19:28

Just for completeness, here's a generalised version for arbitrary list length:

def mid_generator(n):
    s = [list(range(1, n+1)) for x in range(n)]
    while True:
        for x in s:
            random.shuffle(x) 
        for i in range(n):
            test = {s[j][i] for j in range(n)}
            if len(test) != n:
                break
        else:
            return s
    return None # never hit

Interactive:

>>> mid_generator(1)
[[1]]
>>> mid_generator(2)
[[1, 2], [2, 1]]
>>> mid_generator(3)
[[1, 3, 2], [3, 2, 1], [2, 1, 3]]
>>> mid_generator(4)
[[2, 4, 1, 3], [4, 2, 3, 1], [1, 3, 2, 4], [3, 1, 4, 2]]
>>> mid_generator(5)
[[4, 5, 2, 1, 3], [1, 2, 3, 5, 4], [3, 4, 5, 2, 1], [5, 1, 4, 3, 2], [2, 3, 1, 4, 5]]
>>> mid_generator(6)

(still waiting...)

YScharf · Answer 4 · 2022-02-13T12:54:06.703

1

Using the Fisher-Yates shuffle based on code from geegksforgeeks. the following code is modified to ensure that the value is never placed at the original index.

def fisher_yates_shuffle_diff(orig_list):
    result_list = orig_list.copy()
    list_len = len(orig_list)
    indc_list = list(range(0, list_len))
    for i in range(list_len-1, 0, -1):
     
        # Pick a random index from 0 to i 
        indc = indc_list.copy()
        # Remove current index
        indc.remove(i)
        j = indc[random.randint(0, i)]

        # Swap arr[i] with the element at random index
        result_list[i], result_list[j] = result_list[j], result_list[i]
    return result_list

edited Feb 13 '22 at 12:54

answered Sep 29 '21 at 09:17

YScharf

1,638
15
20

1

great answer, was exactly what i was looking for. a couple things - random.randint includes both endpoints, so you'll need something like `j = indc[random.randint(0, i-1)` to make it so that it never picks a number that's out of range. also, the `return result_list` makes the for-loop exit prematurely. the comments could be a bit more clear as well. otherwise, it's a great, elegant answer that avoids a potentially infinite loop. – lapraswastaken Feb 11 '22 at 05:15

score -1 · Answer 5 · answered Nov 24 '15 at 18:40

-1

this will work - but its not optimal - however the if check will work

def mid_generator():

    while True:
        random.shuffle(s1)
        random.shuffle(s2)
        random.shuffle(s3)
        random.shuffle(s4)

        if not (s1 == s2 or s1 == s3 or s1 == s4 or s2 == s3 or s2 == s4 or s3 == s4):
            break

    return s1, s2, s3, s4

answered Nov 24 '15 at 18:40

gkusner

1,244
1
11
14

why the down vote - it works fine? and he did not say anything about latin square - so this solution is a proper answer, don't make assumtions that are not founded in proof – gkusner Nov 24 '15 at 19:00
Not looking for the 4 lists to simply be different permutations, he is looking for each number to be in a different position in each list- a [Latin Square](https://en.wikipedia.org/wiki/Latin_square) – Galax Nov 24 '15 at 19:03
that wasn't in the original question – gkusner Nov 24 '15 at 19:04
actually it wasn't - the question was modified and i answered the original, check the edits – gkusner Nov 24 '15 at 19:13
The question was modified, to correct the indentation and to add a final line. but the sentence "So that the number is only one time in row i and column j" was there from the beginning, with the example. [See for yourself here](http://stackoverflow.com/posts/33901023/revisions) – Galax Nov 24 '15 at 19:15

python, shuffle until lists are completely different

5 Answers5