Permutations - Page 1

Je veux faire une boucle generale.
A chaque iteration de boucles, je veux calculer une nouvelle permutation de l'ensemble {1,...,n}
C pour tester l'ensemble des ca spossibles (apres je fais un autre algo)
Des idees ? Sacahnt que n est une indterminee ?

indéterminée ?
ca me fairait mal!
tu veux dire paramètre ?

Oui un parametre.

euh, si tes permutations ne repondent a aucune condition, il te faudra un algo exponentiel de toute façon !?

Oui, je sais, je veux avoir toutes les permut.
Mais comment les cacluler de maniere efficase ?

http://www.afapl.asso.fr/nvapl33/kerf.pdf

c'est un algo tout simple. il calcule les permutations en se basant sur la recursivité.

ses programmes sont illisibles, mais l'algo est a peu pres bien expliqué.

Ben, j'avais pas envie de reflechir...
Merde alors

désolé.

sinon, je viens de voir un algo sur le net...
écris en lisp.
(meme pas du scheme)

C'est quoi une permutation ?

Hum.
soit n=3.
Les permutations sont :
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

c'est a dire que pour n, il faut une matrice n*n! pour stocker toutes les permutations ...

Mais pkoi je réponds, moi !?

Zut, c'etait a moi.
Finalement je me demande si je vais pas plutot tout stocker dans un tableau pour n <= 7.

J'ai dit que je voulais aps reflechir #bouhou#

le pb du sac a dos est un classique des pb NP complets, voire NP durs.
On le résoud donc a l'aide d'une heuristique, en en faisant un probleme de decision (pb de decision = on definit une entree, et en sortie, on a vrai ou faux, par exemple : entree : le nombre 100, sortie : vrai si et seuelement si il n'existe pas de solution donnant un meilleur resultat que 100)

pour les permutations, dans la mesure ou on les veux absolument toutes, le probleme est aussi NP complet, mais n'a pas d'heuristique

(ben oui !, si on choisit de TOUTES les énumérer...)

C'est le meme algo que celui que j'ai donné en URL.
c vrai que la, il est presque programmé.

désolé, chick-jonh, j'avais pas tt lu.

Bah... De toute facon, au dela de 9...
Ca couille trop

Donc PpHd veut un programme qui écrive les permutations d'une liste donnée dans un tableau.

c'est pour faire quoi ?
parce que, sur TI, je vois pas

NaN
Sans doute pour ses reseaux.
peut etre pour trouver tous les chemins possibles dans un reseau K-complet ?

De quels genres ?

C'est marrant comme problème

On peut inventer notre algo et te le filer, PpHd ?
En ASM ou en pseudo-code ?

Que penses-tu des fonctions suivantes?

;short *first_permut(short *buffer,short number)
;(C) 2001 Kevin Kofler
;Please give me credit in the documentation of your program if you use my routine!
;DISCLAIMER OF WARRANTIES: I HAVE DONE MY BEST NOT TO INSERT BUGS IN MY ROUTINES, BUT I CANNOT BE HELD RESPONSIBLE IF THERE ARE SOME, EVEN IF ANY DAMAGES TO YOUR CALCULATOR OR THE DATA ON IT RESULT OF THOSE BUGS!
;JE NE PEUX ÊTRE TENU RESPONSABLE POUR D'ÉVENTUELS DÉGATS CAUSÉS À VOTRE CALCULATRICE OU AUX DONNÉES ENREGISTRÉES DESSUS PAR D'ÉVENTUELS BOGUES DE CETTE ROUTINE!

first_permut:
 movea.l 4(a7),a0
 move.w 8(a7),d0
 movea.l a0,a1
 subq.w #1,d0
next:
 move.w d0,(a1)
 addq.w #1,(a1)+
 dbra.w d0,next
 rts

;short *next_permut(short *permut,short number)
;(C) 2001 Kevin Kofler
;Please give me credit in the documentation of your program if you use my routine!
;DISCLAIMER OF WARRANTIES: I HAVE DONE MY BEST NOT TO INSERT BUGS IN MY ROUTINES, BUT I CANNOT BE HELD RESPONSIBLE IF THERE ARE SOME, EVEN IF ANY DAMAGES TO YOUR CALCULATOR OR THE DATA ON IT RESULT OF THOSE BUGS!
;JE NE PEUX ÊTRE TENU RESPONSABLE POUR D'ÉVENTUELS DÉGATS CAUSÉS À VOTRE CALCULATRICE OU AUX DONNÉES ENREGISTRÉES DESSUS PAR D'ÉVENTUELS BOGUES DE CETTE ROUTINE!

next_permut:
 movea.l 4(a7),a0
invalid_permut:
 move.w 8(a7),d0
 movea.l a0,a1
 move.l d0,d1
check_again:
 cmp.w (a1),d0
 bne.s no_clear
 move.w #1,(a1)+
 subq.w #1,d1
 tst.w d1
 beq.s error
 bra.s check_again
no_clear:
 addq.w #1,(a1)
 subq.w #2,d0
next_cmp_1:
 lea.l 2(a0,d0.w),a1
 move.w 0(a1,d0.w),d2
 movea.l a0,a1
 move.w d0,d1
next_cmp_2:
 cmp.w (a1)+,d2
 beq.s invalid_permut
 dbra.w d1,next_cmp_2
 dbra.w d0,next_cmp_1
 rts
error:
 suba.l a0,a0
 rts

[edit]Edité par Kevin Kofler le 03-08-2001 à 03:14:55[/edit]

>chickensaver_john: c'est pas un peu lent?

C'est possible (surtout à cause de la boucle de type O(n(n-1)) pour les comparaisons qui éliminent les listes de type 1;1;2 qui ne sont pas des permutations, boucle qui est exécutée m+1 fois où m est le nombre de listes à rejeter). Mais c'est l'algorithme le plus simple qui m'est venu à l'esprit.

Juste une précision: le vrai problème de vitesse de ma routine n'est pas la boucle O(n(n-1)) qui est quand-même polynomiale, mais le nombre de listes à rejeter m, qui n'est pas polynomial (mais approximativement exponentiel) et qui fait répéter toute la fonction. Ceci, dit, le fait de multiplier encore par n(n-1) n'améliore sûrement pas les caractéristiques de vitesse de la routine.

Mais elle a le mérite de fonctionner (au moins j'espère ) et de ne pas être trop complexe (donc pas trop grosse).
[edit]Edité par Kevin Kofler le 02-08-2001 à 21:18:30[/edit]

Mise à jour: j'ai corrigé certains bogues en déboguant avec VTI. Maintenant le programme marche correctement (du moins avec les 3-permutations).

Avec ce programme en C:

#include <tigcclib.h>

short _ti89;
short _ti92plus;

extern short *first_permut(short *buffer,short number);
extern short *next_permut(short *permut,short number);

void _main()
{
short buffer[3];
first_permut(buffer,3);
while (next_permut(buffer,3));
};

et mes fonctions en assembleur A68k, auxquelles on a préalablement ajouté:

 xdef first_permut
 xdef next_permut

 bra skip

au début et skip: à la fin (pour que l'exécution commence bien par le programme en C),

on obtient, dans l'ordre (en lisant la mémoire dans le débogueur de VTI, puisque je n'ai pas mis de printf):

0003 0002 0001
0002 0003 0001
0003 0001 0002
0001 0003 0002
0002 0001 0003
0001 0002 0003

Le prochain appel de next_permut renvoie NULL.
[edit]Edité par Kevin Kofler le 03-08-2001 à 03:27:32[/edit]

Oui ca peut marcher. Mais je vais essayer de trouver une autre methode, base sur une inondation de toutes les permutations possibles des le debut, pour ne retenir apres que la meilleure.
Mais c'est chaud (Au leiu de tester toutes ler perms et de trouver la meilleure), j'inonde et apres filtrage, il ne reste plus que la meilleure.

PpHd ==> si tu cherches une permutation qui doit vérifier un minimax, ce n'est aps la peine de TOUTES les calculer ! c'est vbraiment trop bourrin.

A quoi vont - elles te servir ??


chikensaver-john >> en pratique, on utilise jamais d'algo aussi bourrin pour les pb d'optimisations. Les solutions de ces pb etant generalement NP-dures a enumerer ... Le pb du sac a dos se resoud par une strategie gourmande en temps polynomial. Alors s'il fallait passer en temps exponentiel, pour trouver une solution a peine meilleure ... ben tu mettrais des siecles a faire ton sac ...

Enfin, oui c un minimax.
Mais c'est assez chaud a expliquer.
bref tu cherches le debit max entre plusieurs point ssources et plusieurs points cibles.
L'information entre les points est concurentielle.
Et ca me pose des pbs.
Deja pour formuler correctement le sujet

ben alors commence par formuler le sujet.
avec une entree et une sortie.
quelles sont tes parametres d'entree ?

un nombre de point,liste de points de depart, une liste de points d'arrivee ?

sortie = ??
un couple point de depart/arrivee, qui ait un flot max ?

pour pouvoir resoudre ce pb avec des heuristiques, il faut une sortie booleenne, genre :
- entree : un nb de pt de depart, un nb d epoint d'arrivee, une liste de pt de depart, une liste de pt d'arrivee, un couple pt depart/arrivee (S,P), un flot F

- sortie :
-vrai ssi le flot entre s et p est superieur a F ET tous les flots entre les pts de depart et les pts d'arrivee est superieur a F.
- faux, sinon.

effectivement.
c'est ce "tous les flots" qui pose pb ...


je continue d'y reflechir..

Perso, j'ai trouve une methode.
Elle ne fait pas le flot max, et c un algo glouton.
Mais je pense qu'elle est plus proche de la realite :0

en gros, ca marche comment ?
quel est la formulation du probleme, surtout .