Bonjour

Je cherche à résoudre le problème suivant :

Objectif :

Générer une matrice M de dimensions 29×8 où :
Chaque ligne de la matrice est un sous-ensemble de 8 entiers distincts choisis parmi les entiers de 1 à 29.
Chaque paire de lignes de la matrice doit partager exactement deux éléments en commun.

Contraintes :

Chaque ligne doit contenir 8 valeurs distinctes.
Chaque paire de lignes doit avoir exactement deux éléments en commun.
La solution doit utiliser uniquement les valeurs de 1 à 29.

Sortie attendue :

Une matrice 29×8 respectant les contraintes ou un message indiquant qu'aucune solution n'existe.

Ce que je demande :
Je souhaite obtenir :

- Un code Python ou dans tout autre langage qui peut générer une solution rapidement.
- Si vous connaissez une solution algorithmique ou théorique à ce problème, je serais heureux que vous la partagiez.

Pour info j'ai trouvé la solution pour une matrice de dimensions 16×6 mais le code il se bloque au niveau de 29*8


Voici le code python qui génère une matrice de dimensions 16×6 avec les contraintes suivantes :

1-Chaque ligne contient 6 valeurs distinctes.
2-Chaque paire de lignes partage exactement 2 éléments.
3-Les valeurs utilisées sont comprises entre 1 et 16.

Cependant, lorsqu'on essaie d'étendre ce code pour générer une matrice de 29×8 en utilisant les valeurs de 1 à 29, le code n'arrive pas à trouver une solution valide.
--------------
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import random
import pandas as pd
 
# Définition des paramètres
C = list(range(1, 17))
NUM_ROWS = 16
NUM_COLS = 6
 
# Initialisation de la matrice vide
matrix = []
 
# Fonction pour vérifier les contraintes de chevauchement
def has_valid_overlap(new_row, matrix):
    for row in matrix:
        # Calculer le nombre d'éléments communs avec chaque ligne existante
        common_elements = set(new_row) & set(row)
        # Vérifie qu'il y a exactement 2 éléments en commun
        if len(common_elements) != 2:
            return False
    return True
 
# Génération de la matrice ligne par ligne
while len(matrix) < NUM_ROWS:
    # Générer une ligne aléatoire avec 6 valeurs uniques de C
    new_row = random.sample(C, NUM_COLS)
    # Vérifier les contraintes de chevauchement avec les lignes existantes
    if has_valid_overlap(new_row, matrix):
        matrix.append(new_row)
 
# Conversion de la matrice en DataFrame
df = pd.DataFrame(matrix, columns=[f'Col_{i+1}' for i in range(NUM_COLS)])
 
# Afficher la matrice sous forme de DataFrame
df


Merci