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.
--------------
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
Mathématique Optimisation algorithme
Répondre avec citation
Envoyé par tbc92
Partager