Algorithme de recherche dans tableaux comme au sudoku

Version imprimable

Bonjour,
Je suis a la recherche d’algorithme qui me permettra de générer 10 nombre a partir d’un tableau à 2 dimensions 10X10 avec

Code:

1
2
3
4
5
6
7
8
9
10
11
 
5 nombre des 10 soit existant dans la 1er ligne du tableau
4 nombre des 10 soit existant dans la 2e ligne du tableau
3 nombre des 10 soit existant dans la 3e ligne du tableau
2 nombre des 10 soit existant dans la 4e ligne du tableau
3 nombre des 10 soit existant dans la 5e ligne du tableau
2 nombre des 10 soit existant dans la 6e ligne du tableau
5 nombre des 10 soit existant dans la 7e ligne du tableau
4 nombre des 10 soit existant dans la 8e ligne du tableau
2 nombre des 10 soit existant dans la 9e ligne du tableau
3 nombre des 10 soit existant dans la 10e ligne du tableau

je ne sais pas comment on peut appeler cette algorithme

Svp j’ai cherché par tous avant de venir ici
Cordialement

07/07/2013, 02h01
prgasp77

Il n'y a pas de solution générale : en effet, selon ton tableau 10x10, il pourrait ne pas y avoir de solution. Donc il va falloir nous en dire plus.

Citation:

Envoyé par prgasp77

Il n'y a pas de solution générale : en effet, selon ton tableau 10x10, il pourrait ne pas y avoir de solution. Donc il va falloir nous en dire plus.

Merci pour t'as réponse.

il y'as toujours au moins une solution car chaque ligne de ce tableau contient 10 nombre de 1 a 35

voici le tableau
Code:

1 2 3 4 5 6 7 8 9 10 1 3 4 10 12 26 27 28 30 31 1 2 11 12 13 14 20 22 29 30 2 3 7 9 11 14 17 23 26 28 2 7 12 14 17 18 23 26 28 32 6 10 13 22 23 30 32 33 34 35 1 2 6 7 14 17 18 21 22 24 3 17 18 20 25 29 30 32 33 35 1 8 13 14 21 23 24 26 28 31 4 5 6 7 8 10 13 23 24 33 1 4 5 12 13 28 29 31 33 35
j'ai des 100n de tableau donc impossible de le faire manuellement

cordialement

07/07/2013, 17h18
lolzx

Tu peux résoudre facilement ton problème en fessant un peu de backtraking
07/07/2013, 18h29
prgasp77

Citation:

Envoyé par DATA MINER

il y'as toujours au moins une solution car chaque ligne de ce tableau contient 10 nombre de 1 a 35

Non.

Citation:

Envoyé par lolzx

Tu peux résoudre facilement ton problème en fessant un peu de backtraking

C'est une méthode, qui trouvera une réponse si il en existe. Je conseille de backtracker en sélectionnant en priorité des nombres très présent dans le tableau. Un premier crible peut aussi permettre d'ignorer les nombres qui ne peuvent pas faire partie de la solution (comme dans ton exemple le 34, qui n'apparaît que dans la cinquième ligne.

Cdlt,

Voici la solution que j’ai trouve
Je génère des tableaux qui contiennent toutes les combinaisons possibles de N nombre voulue de 10
Code:

1 2 3 4 5 6 7 8 9 10 T1 contient 5^10 possibilité T2 contient 4^10 possibilité T3 contient 3^10 possibilité T4 contient 2^10 possibilité T5 contient 3^10 possibilité T6 contient 2^10 possibilité T7 contient 5^10 possibilité T8 contient 4^10 possibilité T9 contient 2^10 possibilité T10 contient 3^10 possibilité
Apres je mets tous dans un seul tableux T
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 N=0 For X1 = 0 To UBound(t1) For X2 = 0 To UBound(t2) For X3 = 0 To UBound(t3) For X4 = 0 To UBound(t4) For X5 = 0 To UBound(t5) For X6 = 0 To UBound(t6) For X7 = 0 To UBound(t7) For X8 = 0 To UBound(t8) For X9 = 0 To UBound(t9) For X10 = 0 To UBound(t10) T[N] = t1(X1) & t2(X2) & t3(X3) & t4(X4) & t5(X5) & t6(X6) & t7(X7) & t8(X8) & t9(X9) & t10(X10) N++
Je surprimes les doublons dans la même ligne du tableau T élément séparé par ;
Code:

1 2 3 4 5 6 7 8 9 TT = Split(T[N], ";") For m1 = 0 To UBound(TT) For m2 = m1 + 1 To UBound(TT) If TT(m1) = TT(m2) Then TT(m2) = NULL Next m2 Next m1 If UBound(TT) <10 Then accepter(TT)
Si le nombre d’élément dans le tableau TT est inferieur de 10 on accepte TT

Vous en penser quoi a part que c’est trop lent

est ce que il y'as une optimisation possible

merci

08/07/2013, 18h01
pseudocode

Citation:

Envoyé par DATA MINER

Vous en penser quoi a part que c’est trop lent

est ce que il y'as une optimisation possible

J'en pense qu'il n'y a pas 5^10 possibilités de prendre 5 éléments parmi 10.

Et qu'une fois qu'on a choisi 5 éléments parmi 10 dans le premier tableau, ca réduit très probablement le nombre d'éléments à choisir dans les 9 tableaux suivants. Et ainsi de suite.

Donc oui, il y a matière à optimiser. :D
12/07/2013, 01h58
DATA MINER

Citation:

Envoyé par pseudocode

J'en pense qu'il n'y a pas 5^10 possibilités de prendre 5 éléments parmi 10.

oui effectivement il y'as

10!/(10!(10-5)!)

Citation:

Envoyé par pseudocode

Et qu'une fois qu'on a choisi 5 éléments parmi 10 dans le premier tableau, ca réduit très probablement le nombre d'éléments à choisir dans les 9 tableaux suivants. Et ainsi de suite.

Donc oui, il y a matière à optimiser. :D

est ce que il y'as une formule mathématique pour décrire cette situation
12/07/2013, 11h50
prgasp77

Citation:

Envoyé par DATA MINER

oui effectivement il y'as
10!/(10!(10-5)!)

Perdu :mrgreen: ! C_10^5 = 10! / (5!)^2 = 252. Ça divise donc ton problème de trois ordres de grandeur :ccool:.
Petit rappel C_n^k = n! / (k!(n-k)!).

Mais encore une fois, tester toutes les combinaisons n'est pas forcément utile. À moins de commencer par les plus probable et s'arrêter dès que tu as une solution viable.
12/07/2013, 13h27
pseudocode
Citation:

Envoyé par DATA MINER

oui effectivement il y'as

10!/(5!(10-5)!)

Citation:

formule mathématique pour décrire cette situation

Ce type de problème s'appelle CSP (Constraint Satisfaction Problem). Il n'y a pas d'algo générique pour les CSP.

Le plus simple est d'énumérer une à une toutes les solutions candidates et de vérifier si les contraintes sont respectées. Mais c'est potentiellement très long.

Le plus rapide c'est de construire des solutions qui respectent les contraintes. C'est ce que fait l'algo backtracking en construisant progressivement une solution, avec retour arrière si c'est impossible.

Dans ton cas, comme ton tableau initial contient beaucoup de doublons, tu peux choisir la première solution:
```
Construire la liste "ALL" = T1+T2+T3+...+T10
Supprimer les doublons de la liste ALL
Pour chaque sous-liste "S" à 10 élements de la liste ALL
  si S respecte les 10 contraintes
    afficher S
    sortir du programme
  fin si
fin pour
```
17/07/2013, 23h57
DATA MINER
Citation:
Envoyé par pseudocode

Ce type de problème s'appelle CSP (Constraint Satisfaction Problem). Il n'y a pas d'algo générique pour les CSP.

Le plus simple est d'énumérer une à une toutes les solutions candidates et de vérifier si les contraintes sont respectées. Mais c'est potentiellement très long.

Le plus rapide c'est de construire des solutions qui respectent les contraintes. C'est ce que fait l'algo backtracking en construisant progressivement une solution, avec retour arrière si c'est impossible.

Dans ton cas, comme ton tableau initial contient beaucoup de doublons, tu peux choisir la première solution:

Construire la liste "ALL" = T1+T2+T3+...+T10 Supprimer les doublons de la liste ALL Pour chaque sous-liste "S" à 10 élements de la liste ALL si S respecte les 10 contraintes afficher S sortir du programme fin si fin pour
merci ca marche