Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1076 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  Besoin d'aide [Générer un permutoèdre]

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Besoin d'aide [Générer un permutoèdre]

n°409819
Fornium
until the end of the world...
Posté le 27-05-2003 à 23:05:45  profilanswer
 

Salut les codeurs,
j'ai un projet en C à rendre la semaine prochaine et je n'ai malheureusement toujours pas trouvé la solution  :fou: , ce serait sympa si vous pouviez m'aider svp ....  
 
Voilà les questions!!!
 
1. Générer un permutoèdre *
2. Une fois le permutoèdre généré, votre programme devra pouvoir retrouver la longueur d'une permutation donnée, ainsi qu'un chemin de l'identité vers cette permutation ( i.e. la décomposition de la permutation en produit de transpositions, plus les permutaions intermédiaires).
 
 
* On appellera "permutoèdre" un graphe orienté dont l'ensemble de sommets est constitué de toutes les permutations d'une taille donnée, et dans lequel on mettra un arc entre deux permutations, si la deuxième peut être obtenue à partir de la première en la multipliant juste par une transposition élémentaire, et sa longueur est supérieure à celle de la première.
 
 
Merci pour toute aide !!!!!!!!!!


Message édité par Fornium le 28-05-2003 à 00:11:58
mood
Publicité
Posté le 27-05-2003 à 23:05:45  profilanswer
 

n°409841
HORNY-Gran​dcornu
grumf !
Posté le 27-05-2003 à 23:50:48  profilanswer
 

Ahlàlà, le rush... On arrive à une semaine de l'échéance, et oh, on tombe nez à nez avec la feuille du projet :whistle:  
 
Sérieusement, déjà, j'ai rien pigé au permutoèdre, et qui va s'amuser à programmer ce truc ? (si ce n'est toi of course :d)
 
mets y toi, non seulement tu en retireras de la satisfaction :love: mais également de l'expérience ! :whistle:
 
edit : au fait, tu es en quoi ? Je viens de relire le coup du permutoèdre et j'y pige vraiment que dalle !


Message édité par HORNY-Grandcornu le 27-05-2003 à 23:58:08
n°409848
Fornium
until the end of the world...
Posté le 28-05-2003 à 00:17:38  profilanswer
 

HORNY-GRANDCORNU a écrit :

Ahlàlà, le rush... On arrive à une semaine de l'échéance, et oh, on tombe nez à nez avec la feuille du projet :whistle:  
 
Sérieusement, déjà, j'ai rien pigé au permutoèdre, et qui va s'amuser à programmer ce truc ? (si ce n'est toi of course :d)
 
mets y toi, non seulement tu en retireras de la satisfaction :love: mais également de l'expérience ! :whistle:
 
edit : au fait, tu es en quoi ? Je viens de relire le coup du permutoèdre et j'y pige vraiment que dalle !


 
 
T'inkietes t'es pas le seul à n'avoir rien compris  ;) et sinon j'suis en IUP Génie Maths et Info et c'est un sujet d'Algo !!! en fait c un truc qui à une relation avec les permutations des chiffres et transpositions élémentaires bref des truc pas trop passionnant et ça me rend fou  :pt1cable: !!!


Message édité par Fornium le 28-05-2003 à 18:20:21
n°409877
Taz
bisounours-codeur
Posté le 28-05-2003 à 06:23:46  profilanswer
 

et c'est quoi le rapport avec le C? moi j'ai bien l'impression que c'est de l'algo pure (permutometre, c'est dans le dico?)

n°409918
skeye
Posté le 28-05-2003 à 08:50:16  profilanswer
 

++Taz a écrit :

et c'est quoi le rapport avec le C? moi j'ai bien l'impression que c'est de l'algo pure (permutometre, c'est dans le dico?)


permutoèdre, pas permutomètre!:D
Mais en effet c'est plutot un pb d'algo...

n°410689
Fornium
until the end of the world...
Posté le 28-05-2003 à 18:23:05  profilanswer
 

skeye a écrit :


permutoèdre, pas permutomètre!:D
Mais en effet c'est plutot un pb d'algo...


 
t'as tout à fait raison c un sujet d'algo, j'me suis trompé en haut  ;) mais pour l'instant personne n'a trouvé une solution pour moi  :cry:

n°410691
Taz
bisounours-codeur
Posté le 28-05-2003 à 18:26:24  profilanswer
 

ben en C++ je t'aurais sorti le std::next_permutation, mais tu fais du C :D

n°410762
Fornium
until the end of the world...
Posté le 28-05-2003 à 20:45:51  profilanswer
 

++Taz a écrit :

ben en C++ je t'aurais sorti le std::next_permutation, mais tu fais du C :D  


 
je refuserais pas ton code alors ce serait sympa si tu me le files  ;)

n°410763
Taz
bisounours-codeur
Posté le 28-05-2003 à 20:49:55  profilanswer
 

Code :
  1. // next_permutation and prev_permutation, with and without an explicitly  
  2. // supplied comparison function.
  4. template <class _BidirectionalIter>
  5. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  6.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  7.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  8.                  _LessThanComparable);
  9.   if (__first == __last)
  10.     return false;
  11.   _BidirectionalIter __i = __first;
  12.   ++__i;
  13.   if (__i == __last)
  14.     return false;
  15.   __i = __last;
  16.   --__i;
  18.   for(;;) {
  19.     _BidirectionalIter __ii = __i;
  20.     --__i;
  21.     if (*__i < *__ii) {
  22.       _BidirectionalIter __j = __last;
  23.       while (!(*__i < *--__j))
  24.         {}
  25.       iter_swap(__i, __j);
  26.       reverse(__ii, __last);
  27.       return true;
  28.     }
  29.     if (__i == __first) {
  30.       reverse(__first, __last);
  31.       return false;
  32.     }
  33.   }
  34. }
  36. template <class _BidirectionalIter, class _Compare>
  37. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  38.                       _Compare __comp) {
  39.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  40.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  41.     typename iterator_traits<_BidirectionalIter>::value_type,
  42.     typename iterator_traits<_BidirectionalIter>::value_type);
  43.   if (__first == __last)
  44.     return false;
  45.   _BidirectionalIter __i = __first;
  46.   ++__i;
  47.   if (__i == __last)
  48.     return false;
  49.   __i = __last;
  50.   --__i;
  52.   for(;;) {
  53.     _BidirectionalIter __ii = __i;
  54.     --__i;
  55.     if (__comp(*__i, *__ii)) {
  56.       _BidirectionalIter __j = __last;
  57.       while (!__comp(*__i, *--__j))
  58.         {}
  59.       iter_swap(__i, __j);
  60.       reverse(__ii, __last);
  61.       return true;
  62.     }
  63.     if (__i == __first) {
  64.       reverse(__first, __last);
  65.       return false;
  66.     }
  67.   }
  68. }
  70. template <class _BidirectionalIter>
  71. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  72.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  73.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  74.                  _LessThanComparable);
  75.   if (__first == __last)
  76.     return false;
  77.   _BidirectionalIter __i = __first;
  78.   ++__i;
  79.   if (__i == __last)
  80.     return false;
  81.   __i = __last;
  82.   --__i;
  84.   for(;;) {
  85.     _BidirectionalIter __ii = __i;
  86.     --__i;
  87.     if (*__ii < *__i) {
  88.       _BidirectionalIter __j = __last;
  89.       while (!(*--__j < *__i))
  90.         {}
  91.       iter_swap(__i, __j);
  92.       reverse(__ii, __last);
  93.       return true;
  94.     }
  95.     if (__i == __first) {
  96.       reverse(__first, __last);
  97.       return false;
  98.     }
  99.   }
  100. }
  102. template <class _BidirectionalIter, class _Compare>
  103. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  104.                       _Compare __comp) {
  105.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  106.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  107.     typename iterator_traits<_BidirectionalIter>::value_type,
  108.     typename iterator_traits<_BidirectionalIter>::value_type);
  109.   if (__first == __last)
  110.     return false;
  111.   _BidirectionalIter __i = __first;
  112.   ++__i;
  113.   if (__i == __last)
  114.     return false;
  115.   __i = __last;
  116.   --__i;
  118.   for(;;) {
  119.     _BidirectionalIter __ii = __i;
  120.     --__i;
  121.     if (__comp(*__ii, *__i)) {
  122.       _BidirectionalIter __j = __last;
  123.       while (!__comp(*--__j, *__i))
  124.         {}
  125.       iter_swap(__i, __j);
  126.       reverse(__ii, __last);
  127.       return true;
  128.     }
  129.     if (__i == __first) {
  130.       reverse(__first, __last);
  131.       return false;
  132.     }
  133.   }
  134. }

n°410774
Fornium
until the end of the world...
Posté le 28-05-2003 à 21:01:09  profilanswer
 

cool merci !!!!!!!!!

mood
Publicité
Posté le 28-05-2003 à 21:01:09  profilanswer
 

n°410793
Taz
bisounours-codeur
Posté le 28-05-2003 à 21:26:57  profilanswer
 

TipOfTheDay: efface les __, c'est con, mais ça gagne en lisibilité
 
c'est des opérations sur des sequences: first pointe sur le premier élément, last pointe apres le dernier. tous les éléments sont conceptuellement contigus, c'est à dire accessible par incrémentation (comme balader un pointeur sur un tableau[N], first=tableau, et last=tableau+N)

n°410796
Fornium
until the end of the world...
Posté le 28-05-2003 à 21:39:21  profilanswer
 

++Taz a écrit :

TipOfTheDay: efface les __, c'est con, mais ça gagne en lisibilité
 
c'est des opérations sur des sequences: first pointe sur le premier élément, last pointe apres le dernier. tous les éléments sont conceptuellement contigus, c'est à dire accessible par incrémentation (comme balader un pointeur sur un tableau[N], first=tableau, et last=tableau+N)


 
c noté  :wahoo:  thank u !!!!


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  Besoin d'aide [Générer un permutoèdre]

 

Sujets relatifs
besoin d'aidedemande d'aide pour creer un agenda en php
besoin d'aide sur excel pour une courbe de temps...Aide ecriture fichier
Programmation d'une appli Web : besoin de conseils[BusinessObjects] Besoin de votre aide
Besoin d'un petit perl 101 
Plus de sujets relatifs à : Besoin d'aide [Générer un permutoèdre]

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.085 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR