Bonjour
 
C'est juste pour vous demander un peu d'algorithmique, du moins si vous avez des idées d'optimisation
 
J'ai codé une classe nommée Arrangement, qui me renvoie tous les arrangement possibles de x entiers parmi un tableau de y entiers.
 
par exemple :
 
tablo : 1|5|6|8|9|4|3|2|7
 
j'apelle le constructeur comme ca :
 
arr = new Arrangement ( tablo,3);
 
et j'aurai via des next() et des courant() tous les arrangement possibles de 3 entiers la dedans, sous forme de tableau d'entier, par exemple , dans l'ordre :
 
1|5|6
1|5|8
1|5|9
...
1|6|8
 
etc.
 
Bref, celle la est optimale je le sais (bien que codée recursivement par souci de simplicité mais la recursivité se poursuit au pire n fois si je demande n entiers parmi un tableau de m donc c pas un drame).
 
Maintenant, il me faut une classe qui me bouffe un meme tableau d'entiers, mais qui me renvoie tous les couples possibles de 3 entiers dedans.
 
Par exemple :
 
tablo : 1|5|6|8|9|4|3|2|7
 
Appel du constructeur :
 
cpl = new Couple(tablo,3);
 
et je veux qu'il me renvoie les couples (ordre on s'en fout) comme ceci :
 
1|5|6 + 8|9|4
1|5|6 + 8|9|3
1|5|6 + 8|9|2
...
1|5|6 + 3|2|7
1|5|8 + 6|9|4
etc...
 
Maintenant, dans mon algo qui l'utilise (plutot couteux, d'ou ma recherche d'optimalité, demandée d'ailleurs dans le projet), si j'ai déja fait un couple, pas la peine de faire l'inverse.
 
Par exemple, si j'ai fait 1|2|3 + 4|5|6 pas la peine de refaire 4|5|6 + 1|2|3.
 
Niveau codage de la classe au dessus, c'est deja fait.
 
J'utilise deux Arrangement (cf au dessus). J'initialise le premier au debut, puis je lance le second en lui filant un tableau contenant tous les entiers sauf ceux du premier arrangement, etc.
 
Ca, aucun probleme.
 
Ce que je me demande, c'est au niveau du cas d'arret.
 
J'ai codé pour l'instant un cas d'arret simple, qui dit que des que le premier chiffre du premier couple est au dela de la moitié du tableau, on considère que c'est fini...
 
A votre avis :
 
-je les fait tous si je fais ca ? J'en fais trop ? pas assez ?
 
-Y a moyen de trouver mieux ?
 
Merci de vos réponses ^^
 
PS : mon doute porte en fait sur la longueur paire ou impaire du tableau de départ...

Merci justeleblanc, ca me fé cho au coeur
 
C'est pas urgent, je peux continuer l'algo en ayant un cas d'arret bof, et attendre une réponse (ou réussir a la trouver par moi meme, ce qui est pas impossible bien que moi et la combinatoire hum )
 
Mais ca serai bieng quand meme ^^

je commence a caler la

Ben tu récupéres tous d'abord une liste des 6-tuples possible avec Arrangement(tablo, 6).
Puis pour chaque 6-tuples tu récupères les paires de triplets possible avec Arrangement(tablo2, 3) mais t'en gardes que la moitie

Verdoux a écrit a écrit : Ben tu récupéres tous d'abord une liste des 6-tuples possible avec Arrangement(tablo, 6). Puis pour chaque 6-tuples tu récupères les paires de triplets possible avec Arrangement(tablo2, 3) mais t'en gardes que la moitie

 
Heu putain attention a toi tu me fais douter la, surtout que mon algo version zarbi est terminé...
 
Mais niveau programmation c'est l'horreur ca non ?
 
je vois pas trop ce que tu me conseille de faire... Disons que je vois en gros ce que tu veux faire, mais absolument pas comment tu veux coder ca sans perdre une patate de mémoire

EDIT : zut, en fait, j'avais mal compris...
 
Ton algorithme reviens au meme que le mien, a ceci pret que tu n'as pas a marquer ceux qui ont déjà été pris...
 
mais en contrepartie tu dois utiliser 2 arrangements chiants a utiliser pour ne garder que la moitié des couples possibles... et vérifier que tu n'as pas deja fait ce tuple avant surtout...moi non
 
En fait, je crois que j'ai trouvé une solution
 
Je prends la moitié des 3-tuples possibles du tablo de départ.
 
Jusqu'a la moitié quoi  
 
Ensuite, je marque ceux pris, et je prends tous les 3-tuples restats
 
et je continue
 
Et ceux étant deja passé dans le premier tuple ont déjà été itérés entièrement donc ne nécéssitent plus d'etre sélectionné (enfin quand ils ont été pris en première place du premier tuple en fait )

[jfdsdjhfuetppo]--Message édité par Tetedeiench le 16-05-2002 à 23:35:21--[/jfdsdjhfuetppo]

Verdoux, en fait, j'ai un algo qui amrche plutot bien, mais j'aimerai vérifier que c'est bien ca...
 
Ce qui m'aiderai réellement maintenant, c'est le calcul de combien de couples de 3 sommet je peux faire dans mon tableau de départ...
 
Pour un tableau de 7 j'en dénombre via mon algo actuel 70... c'est ca ?

Oui ce doit être ça.
Et 280 pour un tableau de 8.

[jfdsdjhfuetppo]--Message édité par Verdoux le 16-05-2002 à 23:44:15--[/jfdsdjhfuetppo]

Verdoux, je t'aime, c bon
 

 

 

 
Magnifique, mon algo est PARFAIT, pas UNE ITERATION en trop
 
Magnifique
 
je t'aime

C'est beau l'informatique

Mieux : pour un tableau de 22 ca met 6 secondes... sur un PII 350 ...
 
Y a 746130 possibilités ^^
 
C'est y pas optimal ca ^^

[jfdsdjhfuetppo]--Message édité par Tetedeiench le 16-05-2002 à 23:58:16--[/jfdsdjhfuetppo]

Tetedeiench,  
il suffit que tu ne prennes pas les paires de triplet
a|b|c d|e|f ou a>d, non?
Donc pour Couple(tablo, n) tu dois juste modifier ton algo qui fait Arrangement (tablo,2*n)  
Afin que lorsque tu construit a|b|c|d|e|f, tu ne construises pas les cas ou a>d, puis tu separes le resultat a|b|c|d|e|f en couple a|b|c d|e|f.
A+,

Tetedeiench a écrit a écrit : Mieux : pour un tableau de 22 ca met 6 secondes... sur un PII 350 ...   Y a 746130 possibilités ^^   C'est y pas optimal ca ^^

 
'tain, c'est long!! Y'a une machine IBM qui compile le dernier noyau Linux, en 6 secondes! D

 
huuuuuuum, oui, en effet, ca pourrait le faire...
 
Ca utilise moins la prog objet, mais bon, je fais bidouiller ca et garder la + rapide des deux (si grosse différence il y a
 
Merci gilou ^^

A la réflexion gilou, c'est aussi problematique ton truc...
 
Car quand je donne un arrangement, j'ai pas programmé ca avec 6 pointeurs...
 
Enfin c'est récursif via des avancement ...
 
Donc en gros, pour mes arrangements, j'aurai ca :
 
1 2 3 4 5 6
 
Et effectivement ca fait le couple 1 2 3 + 4 5 6
 
Maintenant admettons que je veuille avoir le couple 1 5 6 + 2 3 4 (que je dois absolument faire tant que le premier couple pointe sur 1 d'ailleurs, ca se tiens)
 
Avec mon algo d'arrangement actuel, je pourrai que sortir 1 2 3 + 4 5 6 ...
 
Bilan : spacool
 
Je vais garder ma version actuelle car elle est diablement efficace finalement ^^

Tetedeiench a écrit a écrit : A la réflexion gilou, c'est aussi problematique ton truc...   Car quand je donne un arrangement, j'ai pas programmé ca avec 6 pointeurs...   Enfin c'est récursif via des avancement ...   Donc en gros, pour mes arrangements, j'aurai ca :   1 2 3 4 5 6   Et effectivement ca fait le couple 1 2 3 + 4 5 6   Maintenant admettons que je veuille avoir le couple 1 5 6 + 2 3 4 (que je dois absolument faire tant que le premier couple pointe sur 1 d'ailleurs, ca se tiens)   Avec mon algo d'arrangement actuel, je pourrai que sortir 1 2 3 + 4 5 6 ...   Bilan : spacool   Je vais garder ma version actuelle car elle est diablement efficace finalement ^^

Ben moi je connais pas ton implem, donc...
A+,

Vi bien sur tu pouyvais pas savoir, et je te remercie grandement de ton intervention