Salut les gens,
 
 
on donne "n", et je dois sortir toutes les permutations de 0 -> n-1.
 
ex : n = 3
 
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
 
Je dois faire ca avec une fonction récursive, mais j'suis bloqué. Ca à l'air tout con, mais j'y arrive pas  
 
Quelqu'un peut me donner une piste ?  
 
 
ps : faut pas m'expliquer ce qu'est une fct recursive, ...

comme tu ne dis pas le langage , voici l'algo  
 
 
permutation(Ensemble E)
{
 pour chaque e de E
  afficher e
  permutation (E-{e})
  sauter une ligne
}

ouais, mais bon, avec une codition d'arret c'est quand même nettement mieux

gizmo a écrit a écrit : ouais, mais bon, avec une codition d'arret c'est quand même nettement mieux

Je suppose que "pour chaque e de E"
implique que on s'arrete quand E est vide...

a condition de ne pas considérer l'élément vide, oui.

c'est quoi l'element vide ? Je ne connais rien de tel...
Je considere l'ensemble vide, mais pas l'element, or un element ne peut etre confondu avec un ensemble...
 
cf "l'ensemble de tous les ensembles"
 
De plus meme en admettant qu'il existe un tel element
si E ne contient que l'element vide, il n'est pas vide et donc l'execution continue, E / { element vide} = E/E = ensemble vide
d'ou au passage suivant l'ensemble est vide...

[edtdd]--Message édité par BENB--[/edtdd]

ben ca dépend des objets avec lesquels tu travailles, si tu travailles avec une liste chainnée terminée par l'élément null (en  c++), et bien si ta condition d'arret est mal concue, ton algo va boucler a l'infini.

1- C'est de l'algo donc independant du langage
 
2- Tes listes chainee doivent etre mal concue si tu peut confondre un element de gestion de la chaine avec ce que cette chaine est sensee contenir... Utilise la list de la STL et ton probleme disparait...
 
2- "pour chaque" est generalement traduit par un for(), et donc la condition de fin est implicite surtout en C/C++ puisque dans le dernier For la condition de fin du for se trouverait verifiee des le debut, et donc aucune iterations.
 
3- Ce qui m'intrigue beaucoup plus c'est le E-{e}, qui est, a mon avis nettement plus complexe de mise en oeuvre, a priori. Mais encore une fois il s'agit ici d'un Algo et une ecriture de haut niveau se justifie parfaitement, et ce d'autant plus que c'est bien ce qu'appelle la question puisqu'elle n'indique absolument pas comment le premier E est fourni (tableau - liste chainee ) ?

1° c'est de l'algo, donc il doit prévoir les cas de figure les plus complexes, et d'autre langage que le C++ acceptent un élément vide (les langages fonctionnels entre autre), donc la condition d'arret est a prévoir ou au moins a documenter.
 
2° c'était un exemple...
 
2° généralement c'est traduit plutot par foreach, qui a une autre signification que le for dans certains langages.
 
3° entièrement d'accord.

J'ai du mal a conceptualiser un "element vide"
car un ensemble qui contiendrait un tel element ne serait pas vide...
de plus mathematiquement le contenant est l'ensemble, et l'element le contenu, et qualifier de vide qqchose suppose que ce soit un contenant...
 
Par contre que dans certains langages il y ait un indicateur d'ensemble vide, certes, mais ce n'est pas un element.
 
Par exemple en C/C++ le NULL ou 0 joue ce role... Un pointeur qui pointe sur NULL est cense pointer sur rien et donc representer un "ensemble vide"
mais il n'est en rien un element de cet ensemble...

en effet, c'est juste un concept, mais tout est-il que certains langages permettent de travailler sur le vide (donc même pas le Null ou le 0).

Oui mais c'est en contradition avec les concepts mathematiques des ensembles....
C'est pour cela que je refute le droit de cette chose a s'appeller "element"

[edtdd]--Message édité par BENB--[/edtdd]

oui, mais ce n'est pas en contradition avec la logique informatique de création de variable. Ces langages considèrent que tu vas pouvoir transformaer le vide en qqch, et donc acceptent de travailler aveuglément dessus.

[edtdd]--Message édité par gizmo--[/edtdd]

Mais cette chose est elle toujours presente quand l'ensemble n'est plus vide ?
Quels sont les langages qui usent de ce concept...

les langages fonctionnels utilisent ce concept. Un objet est défini par ce qu'il contient et ce qu'il contient peut ête le vide ou des éléments et le vide.

C'est donc plus un descripteur de l'ensemble formellement represente comme un element, ou un pre-element...
 
Quels sont ces langages ?

c'est ca.
 
Exemples de langages fonctionnels : ML, CaML, Eiffel (cas particulier car la compilation le transforme en C), Modula,...

En Caml tu peux
definir  
type monType= Rien | Quelquechose;;
 
mais "Rien" n'est pas une construction
du langage  
ca n'a le sens de Rien
que parce que je l'utilise ainsi dans mon programme.
C'est purement binaire c'est 0 ou 1.
(comme le type NULL en C, qui est different
de void qui signifie une 'absence' de parametre)
Quand tu as un objet de type monType qui vaut
"Rien" ca reste un objet et il vaut quelque chose:
il vaut "Rien", et il n'est pas vide
(comment un objet ou un element peut-il etre vide
si ce n'est pas un conteneur ou un ensemble?)
Si MonType represente une liste ou un ensemble
alors Rien peut signifier une liste vide mais
ce n'est que parce que MOI j'ai decide de representer
mes donnees ainsi.
 
Bon c'est peut-etre embrouille comme explication
mais j'espere que ca vous aura un peu eclaire.
 
[HS] Quelqu'un se rappelle le passage d'Alice
au pays des merveilles ou elle rencontre
Humpty Dumpty? [/HS]
 
A+
LEGREG

LeGreg > NULL est une valeur en C/C++, 0 en general, et c'est nous qui semantiquement lui donnons le sens de "rien"
 
Je suis bien d'accord avec toi, "element vide" est une expression absurde, et c'est avant tout cette expression que j'ai attaque, d'abord parceque un element n'est, a priori, pas un contenaire et de plus le vide ne s'appliquait pas a lui...
Il aurrait donc ete "l'element 'vide'" ou encore "l'element du vide" mais alors l'ensemble qui le contient n'est plus vide.
 
Il n'est donc pas "vide"
Il n'est donc pas un element.
 
Pour revenir au debut de la discution avec Gizmo, "Pour chaque element de E" implique en lui meme une terminaison si E est un ensemble fini (ayant un nombre fini d'elements). La modelisation des ensembles infinis (ayant un nombre infinis d'elements) n'etant pas facile en informatique nous supposerons donc que E est fini, ce qui bien comode pour proposer des permutations...

eheh il n'est pas necessaire
d'avoir un ensemble fini pour enumerer
ses elements, il suffit qu'il soit denombrable.
mais pour s'en convaincre il suffit de se dire
que si l'enumeration doit se terminer a l'element n
pour raison X ou Y (memoire, ou capacite en bits),
alors rien n'interdit de doubler la memoire ou la ressource
qui fait defaut pour enumerer l'element n+1.
Bon evidemment se pose le probleme de la terminaison
et de l'argent necessaire si les besoins en ressources
croissent avec le nombre d'element a enumerer.
 
Par contre si l'ensemble n'est pas denombrable
(ensemble des reels), alors le probleme est insoluble
avec les machines universelles classiques.
Ce qui fait dire a certains que les nombres
reels n'existent pas et sont une conspiration de mathematiciens
mais je m'egare
 
A+
LEGREG

[HS]Hop, l'extrait en question[/HS]
 

 
LEGREG

waouw, pleins de réponses  
 
 
Merci les gens. je vais lire tout ca...

 
 
oki je crois que j'ai capté.
 
J'ai pas mis le language parce que je voulais pas qu'on me le fasse non plus.
 
En tout cas, merci

cessez le feu , je me rends , je l'ai oublié , il faut rajouter  

si vide(E)
  alors arreter  

avant la boucle for

sache que mathématiquement, même l'ensemble vide est un ensemble, c'est même un espace vectoriel (voire une C-algèbre si tu veux...)

 
c'est pas grave c'était juste l'occasion d'avoir une discussion intéressante.

certes...  
mais il me semble que son nom le laissait supposer...