[java] Un peu d'algorithmique niveau combinatoire...

Un peu d'algorithmique niveau combinatoire... [java] - Java - Programmation

Marsh Posté le 16-05-2002 à 20:16:43    

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


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 20:16:43   

Reply

Marsh Posté le 16-05-2002 à 20:30:21    

Merci justeleblanc, ca me fé cho au coeur :love:
 
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 ^^


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 22:56:04    

:hot: je commence a caler la ;)


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 23:04:25    

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 :D

Reply

Marsh Posté le 16-05-2002 à 23:30:08    

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 :D  




 
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 :??:


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 23:34:04    

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]


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 23:37:51    

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 ?


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 23:44:00    

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]

Reply

Marsh Posté le 16-05-2002 à 23:45:13    

Verdoux a écrit a écrit :

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




Verdoux, je t'aime, c bon :love:
 
:love:
 
:love:
 
:love:
 
Magnifique, mon algo est PARFAIT, pas UNE ITERATION en trop :love:
 
Magnifique :love:
 
je t'aime :love:


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 16-05-2002 à 23:48:48    

C'est beau l'informatique :D

Reply

Marsh Posté le 16-05-2002 à 23:48:48   

Reply

Marsh Posté le 16-05-2002 à 23:57:19    

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 ^^ :D :love:

 

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


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 17-05-2002 à 00:39:55    

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+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 17-05-2002 à 08:20:07    

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 ^^ :D :love:  
 
 




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

Reply

Marsh Posté le 17-05-2002 à 08:40:48    

gilou a écrit a écrit :

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+,  




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


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 17-05-2002 à 09:23:14    

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


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Marsh Posté le 17-05-2002 à 10:33:09    

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+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 17-05-2002 à 16:21:48    

gilou a écrit a écrit :

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




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


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed