Circular permutation with two iterators

Question

I need to make an circular permutation of an list for example I have : (a,b,c,d,e) I want (e,a,b,c,d). But I don't succeed to do so, here what I tried :

#ifndef ALGORITHME_H
#define ALGORITHME_H

template<typename I>  
void permutationCirculaire(I first, I last) {
    typename std::iterator_traits<I>::value_type firstElement = *first;
    typename std::iterator_traits<I>::value_type res;
    I tmp = first;

    for (++first; tmp != last; ++tmp) {
        *first = *tmp;
        std::cout << "tmp : " << *tmp << ", first : " << *first << std::endl;
        ++first;
    }


}

#endif

I get this : tmp : a, first : a tmp : a, first : a tmp : a, first : a tmp : a, first : a tmp : a, first : a

And I don't know why, my main :

#include <iostream>
#include <list>
#include "algorithme.h"

using namespace std;

int main() {    
    list<char> liste;
    liste.push_back('a');
    liste.push_back('b');
    liste.push_back('c');
    liste.push_back('d');
    liste.push_back('e');

    cout << "( ";
    for (list<char>::iterator it = liste.begin(); it != liste.end(); ++it) {
        cout << *it << " ";
    }
    cout << ") " << endl;

    cout << "Permutation : " << endl;
    permutationCirculaire(liste.begin(),liste.end());

    cout << "( ";
    for (list<char>::iterator it = liste.begin(); it != liste.end(); ++it) {
        cout << *it << " ";
    }
    cout << ") " << endl;

    return 0; 
}

If you knwo why don't hesitate...

Answer 1

I finally succeed to correct my problem here is my solution, thanks everyone for your help :

template<typename I>  
void permutationCirculaire(I first, I last) {
    typename std::iterator_traits<I>::value_type current = *first;
    typename std::iterator_traits<I>::value_type save = *(--last);

    for(; first != last; ++first) {
        current = *first;
        *first = save;
        save = current;
    }
    *first = save;
}

Sorry again for the mistakes.

Answer 2

If all you need to do is move the last element to the front of the list the you can use:

liste.push_front(liste.back());
list.pop_back();

If you actually want an to use a function that uses iterators the I would walk through the list backwards and swap the elements which will bring the last element to the front.

template<typename I>  
void permutationCirculaire(I first, I last)
{
    --last;  // move last to the last element
    while(first != last)
    {
        iter_swap(last, last - 1);
        --last;
    }
}

Answer 3

As is mentioned by jaunchopanza rotate is what you should be using.

So replace this:

cout << ") " << endl;

cout << "Permutation : " << endl;
permutationCirculaire(liste.begin(),liste.end());

cout << "( ";

With this:

rotate(liste.begin(), advance(liste.begin(), liste.size() - 1), liste.end());

Note to adjust how many characters you rotate by change the number in the advance call.
size() - 1 rotates

a, b, c, d, e

to

e, a, b, c, d

If you were to use say 2 instead of size() - 1 you'd get:

c, d, e, a, b

Also consider: next_permutation and prev_permutation if you wnt to do something other than rotate.

Answer 4

Previous answers are what you should do. With you code specifically, there are several problems; one would be: in your for loop, you increment first ahead and terminate on temp != last, what happens if you have size 1 list? Your first == end and you do *first = *temp also move you cout statement one line higher before the *first = *temp and this way you will get what you want on the output.