Attribution de nombres aléatoires dans une grille sans doublons en Python

Question

J'ai 16 variables disposées dans une grille de 4 par 4. Mon objectif est de créer une fonction capable d'attribuer un nombre aléatoire entre 0 et 4 à chaque variable, sans doublon dans chaque colonne et chaque ligne - comme un sudoku.

Chaque méthode que j'ai essayée donne des doublons. Par exemple :

column_A = [A1, A2, A3, A4]
column_B = [B1, B2, B3, B4]
column_C = [C1, C2, C3, C4]
column_D = [D1, D2, D3, D4]
row_1 = [A1, B1, C1, D1]
row_2 = [A2, B2, C2, D2]
row_3 = [A3, B3, C3, D3]
row_4 = [A4, B4, C4, D4]
all_rows = [row_1, row_2, row_3, row_4]
all_columns = [column_A, column_B, column_C, column_D]

def random_grid():
    for i in range(len(all_rows)):
      all_columns[i] = sample([0, 1, 2, 3, 4], 4)
      all_rows[i] = sample([0, 1, 2, 3, 4], 4)

ne fonctionne pas Comment puis-je faire ?

Answer 1

Il suffit de créer une grille "de base", où deux lignes ou colonnes ne sont pas identiques. Par exemple, pour une grille de taille 4x4, la ligne de base serait :

[[1, 2, 3, 4],
 [4, 1, 2, 3],
 [3, 4, 1, 2],
 [2, 3, 4, 1]]

Puis mélangez les lignes, puis mélangez les colonnes.

Du pur python :

random.shuffle ne mélange que les éléments de la liste que vous avez transmise. Pour mélanger les colonnes, vous devrez transposer la liste des listes de sorte que le premier axe regroupe les éléments suivants colonnes au lieu de rangs.

import random

def random_grid(size=4):
    r = list(range(1, size+1))
    baseline = [r[-n:] + r[:-n] for n in range(size)]
    random.shuffle(baseline)
    transpose = [list(col) for col in zip(*baseline)]
    random.shuffle(transpose)
    return transpose

Utilisation de numpy :

np.random.shuffle ne mélange que le premier axe, nous transposons donc le tableau avant de le mélanger à nouveau.

import numpy as np

def random_grid(size=4):
    r = list(range(1, size+1))
    baseline = np.array([r[-n:] + r[:-n] for n in range(size)])
    np.random.shuffle(baseline)
    np.random.shuffle(baseline.T)
    return baseline

---

Maintenant, puisque vous voulez des nombres aléatoires entre 0 y size Si vous avez besoin d'une grille plus grande d'une ligne et d'une colonne que ce que vous voulez, vous pouvez simplement obtenir une grille plus grande d'une ligne et d'une colonne que ce que vous voulez, soustraire un à chaque élément et rejeter la ligne et la colonne supplémentaires.

Du pur python :

def random_grid_2(size=4):
    rgrid = random_grid(size+1)
    return [[i - 1 for i in row[:-1]] for row in grid[:-1]]

Numpy :

def random_grid_2(size=4):
    rgrid = random_grid(size+1) - 1
    return rgrid[:-1, :-1]

Bien entendu, cette approche est moins efficace que de le faire en random_grid en premier lieu, lorsque vous créez la grille, mais j'ai gardé les deux étapes séparées pour vous aider à comprendre ce qui se passe.

Answer 2

Ok, voici un peu de code qui implémente ma méthode ; plus pour la démonstration que pour une utilisation pratique car, comme il a été dit dans un commentaire, elle peut échouer (s'il n'y a plus de choix, ce qui peut arriver pour les 3 nombres dans le coin inférieur droit de la matrice) ; cela pourrait être résolu en attrapant l'erreur et en recommençant le processus, mais ce n'est pas très élégant.

from random import choice

numbers = {0,1,2,3,4}

a=[[],[],[],[]]

for i in range(4):
    for j in range(4):
        available = list(numbers - set(a[i][:j]) - {a[x][j] for x in range(i)})
        a[i].append(choice(available))

print(a)

Voici le code modifié (avec la capture des erreurs) ; il fonctionnera toujours, mais au prix de la création potentielle de plusieurs matrices ratées avant une matrice qui fonctionne.

from random import choice

numbers = {0,1,2,3,4}

failed = True
while failed:
    a=[[],[],[],[]]
    failed = False
    try:
        for i in range(4):
            for j in range(4):
                available = list(numbers - set(a[i][:j]) - {a[x][j] for x in range(i)})
                a[i].append(choice(available))
    except:
        failed = True

print(a)

Answer 3

Pranav a montré une excellente solution. Une solution naïve (qui devrait fonctionner dans ce cas) pourrait être de générer n'importe quelle matrice et de vérifier si elle est correcte.

Mise en œuvre simple :

from random import sample

def check(matrix, size=4):
    return check_rows(matrix, size) and check_cols(matrix, size)

def check_rows(matrix, size=4):
    return all(len(set(matrix[i])) == size for i in range(size))

def check_cols(matrix, size=4):
    transposed = [[matrix[j][i] for j in range(size)] for i in range(size)]
    return check_rows(transposed, size)

def generate(size=4):
    return [sample(range(5), size) for _ in range(size)]

while True:
    matrix = generate()
    if check(matrix):
        break

print(matrix)