Discussion :

[DATA MINER]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[DATA MINER]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[lolzx]

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

[prgasp77]

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

Non.

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,

[DATA MINER]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pseudocode]

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.

[DATA MINER]

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)!)

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.

est ce que il y'as une formule mathématique pour décrire cette situation

[prgasp77]

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

Perdu ! C_10^5 = 10! / (5!)^2 = 252. Ça divise donc ton problème de trois ordres de grandeur .
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.

[pseudocode]

oui effectivement il y'as

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

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

[DATA MINER]

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