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

Besoin d'aide [Générer un permutoèdre] - C++ - Programmation

Marsh Posté le 27-05-2003 à 23:05:45    

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
Reply

Marsh Posté le 27-05-2003 à 23:05:45   

Reply

Marsh Posté le 27-05-2003 à 23:50:48    

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
Reply

Marsh Posté le 28-05-2003 à 00:17:38    

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
Reply

Marsh Posté le 28-05-2003 à 06:23:46    

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

Reply

Marsh Posté le 28-05-2003 à 08:50:16    

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

Reply

Marsh Posté le 28-05-2003 à 18:23:05    

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:

Reply

Marsh Posté le 28-05-2003 à 18:26:24    

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

Reply

Marsh Posté le 28-05-2003 à 20:45:51    

++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  ;)

Reply

Marsh Posté le 28-05-2003 à 20:49:55    

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

Reply

Marsh Posté le 28-05-2003 à 21:01:09    

cool merci !!!!!!!!!

Reply

Marsh Posté le 28-05-2003 à 21:01:09   

Reply

Marsh Posté le 28-05-2003 à 21:26:57    

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)

Reply

Marsh Posté le 28-05-2003 à 21:39:21    

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

Reply

Sujets relatifs:

Leave a Replay

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