salut

je ne vois pas comment ou pourquoi ton code marche pour 13 * 6 et pas pour  29 * 8 ... sauf à peut-être te bouffer trop de mémoire( genre programme récursif)

peux-tu donner ton code ?

une idée d'algo  ... mais je ne sais pas s'il est très efficace :

construction d'une matrice à p lignes et q colonnes en choisissant parmi les entiers de 1 à n avec les contraintes :

a : q nombres distincts par ligne
b : toute paire de deux lignes a exactement deux nombres en commun

1/ construction de la ligne 1 : choix de q nombres (distincts) par n

2/ construction de la ligne k : choix de q - 2 nombres parmi les n - q restants (en retirant ceux de la ligne précédente k - 1) + choix de deux nombres parmi les q de la ligne précédente k - 1

## les lignes k - 1 et k vérifient donc la contrainte b

3/ vérification de la contrainte b avec la ligne k et toutes les lignes précédentes sauf l'avant dernière (de 1 à k - 2)

4/ si ça marche on retourne en 2/ et on construit la ligne suivante : k + 1
4/ si ça ne marche pas on retourne en 2/ et on recommence avec la ligne k

Bonsoir,
quelques idées.
Il vaut sans doute mieux ordonner les lignes et partir de la ligne (1,2,3,4,5,6,7,8).
Ensuite on place au début de chacune des autres lignes une des 28 paires de nombres possibles à partir de la ligne 1.

La matrice se présente alors sous la forme

1 2 3 4 5 6 7 8
1 2
1 3
⋅⋅⋅
⋅⋅⋅
6 7
6 8
7 8

Bonjour  carpediem

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.
                                                                                            --------------
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

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.
--------------
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

*** message déplacé ***

Juste une remarque : il y a plus de quatre millions de lignes possibles.
Exactement
Si tu cherches au hasard dans cet ensemble une ligne précise tu a peu de chance de la trouver en un temps raisonnable.

Dans le module python "itertools" il y a une fonction "combinations" qui donne la liste de toutes les possibilités ce qui permet de les parcourir dans l'ordre.

Merci pour votre réponse verdurin.
Je l'ai déjà testé, mais après une longue exécution, le code n'aboutit toujours pas à une solution.

--------
from itertools import combinations

def share_two_elements(comb1, comb2):
    """Vérifie si comb1 et comb2 partagent exactement 2 éléments."""
    common_elements = set(comb1) & set(comb2)
    return len(common_elements) == 2

def generate_combinations():
    """Génère 29 combinaisons de 8 éléments parmi [1, 29] avec la contrainte de partage exact de 2 éléments."""
    # Générer toutes les combinaisons possibles de 8 éléments parmi 1 à 29
    all_combinations = list(combinations(range(1, 30), 8))  # [1, 29] avec 8 éléments
    print(f"Total de combinaisons générées: {len(all_combinations)}")
    
    selected_combinations = []
    max_combinations = 29  # Le nombre cible de combinaisons
    start_idx = 0  # Index de départ pour la première combinaison
    
    # Boucle principale pour sélectionner les combinaisons valides
    while len(selected_combinations) < max_combinations:
        selected_combinations = []  # Réinitialisation des combinaisons sélectionnées
        # On commence à partir de la combinaison `start_idx`
        for idx in range(start_idx, len(all_combinations)):
            comb = all_combinations[idx]
            for comb in all_combinations:
                # Vérifier si cette combinaison peut être ajoutée
                if all(share_two_elements(comb, existing_comb) for existing_comb in selected_combinations):
                    print(comb)
                    selected_combinations.append(comb)

                # Si on a atteint 29 combinaisons valides, on arrête
                if len(selected_combinations) == max_combinations:
                    break
        
        # Si on n'a pas réussi à obtenir 29 combinaisons valides, on passe à l'élément suivant de all_combinations
        if len(selected_combinations) < max_combinations:
            start_idx += 1
            print(f"Réinitialisation avec la combinaison {start_idx} de all_combinations.")
    
    return selected_combinations

# Générer les 29 combinaisons valides
valid_combinations = generate_combinations()

# Afficher les résultats
for idx, comb in enumerate(valid_combinations, 1):
    print(f"Combinaison {idx}: {comb}")

Voilà quelqu'un qui ne lit pas le règlement ...c'est pourtant écrit en assez gros...

extrait de la FAQ du forum :

Q03 - Pourquoi ne faut-il pas faire du ''multi-post'' ?

Pour de nombreuses raisons.

Pour mémoire, le multi-post consiste à reposer une même question dans un sujet différent , ou à poser des questions successives d'un même problème dans des sujets différents.

De même, une demande identique sur plusieurs sites sera considérée comme un multipost et la discussion pourra être fermée par un modérateur.

Etant donné tous les désagréments créés par le multi-post, le non-respect de cette règle entraînera votre exclusion temporaire ou définitive du forum !

Voici maintenant quelques raisons qui font que nous combattons avec autant d'ardeur le multi-post (et ses adeptes ) :

• La perte de temps pour les modérateurs qui consacrent leur temps bénévolement pour garantir la qualité des sujets et des échanges sur le forum.
• Le respect du travail des correcteurs qui consacrent leur temps bénévolement pour aider ceux qui sollicitent de l'aide.
• La lisibilité du forum de manière à ce qu'un sujet ayant déjà reçu de l'aide soit facilement identifié et qu'un sujet n'en ayant pas encore reçu puisse à son tour en recevoir.

Rappelez-vous une nouvelle fois la règle d'or du forum :
1 sujet créé = 1 problème

On ne peut pas exclure qu'il n'y ai pas de solutions.
Comment est-ce que ton script détecte ce cas ?