具有两个迭代器的循环排列

Question

我需要对列表进行循环排列，例如我有：（a，b，c，d，e）我想要（e，a，b，c，d）。但我没有成功这样做，这是我尝试过的：

#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

我得到这个：TMP ： A， 第一个 ： ATMP ： A， 第一个 ： ATMP ： A， 第一个 ： ATMP ： A， 第一个 ： ATMP ： A， 第一个 ： A

我不知道为什么，我的主要：

#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; 
}

如果你知道为什么不要犹豫...

Answer 1

正如jaunchopanza所提到的rotate这是你应该使用的。

所以替换这个：

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

有了这个：

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

请注意，要通过更改advance呼叫中的号码来调整旋转的字符数。
size() - 1旋转

A， B， C， D， E

自

E， A， B， C， D

如果你使用说2而不是size() - 1你会得到：

C， D， E， A， B

还要考虑：next_permutation和prev_permutation，如果你不想做旋转以外的事情。

Answer 2

如果您需要做的就是将最后一个元素移动到列表的前面，则可以使用：

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

如果你真的想使用一个使用迭代器的函数，我会向后浏览列表并交换元素，这将把最后一个元素带到前面。

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

以前的答案是你应该做的。具体使用代码，存在几个问题;一个是：在你的 for 循环中，你先递增，在 temp 上终止！= 最后，如果你有大小 1 的列表会发生什么？你的第一个 == 结束，你做 *first = *temp 也会在 *first = *temp 之前将你的 cout 语句向上移动一行，这样你就会在输出上得到你想要的。

Answer 4

我终于成功地纠正了我的问题，这是我的解决方案，谢谢大家的帮助：

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

再次为错误道歉。