Круговая перестановка с двумя итераторами

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

Я получаю это:
ТМ: а, во-первых: а
ТМ: а, во-первых: а
ТМ: а, во-первых: а
ТМ: а, во-первых: а
ТМ: а, во-первых: а

И я не знаю почему, мой главный:

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

Если вы знаете, почему не стесняйтесь …

0

c++iterator iterator-traits

Решение

Другие решения

Если все, что вам нужно сделать, это переместить последний элемент в начало списка, вы можете использовать:

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

0

Предыдущие ответы — это то, что вы должен делать. С вашим кодом, в частности, есть несколько проблем; Один из них: в вашем цикле for вы увеличиваете первый шаг вперед и заканчиваете на temp! = last, что произойдет, если у вас есть список размера 1? Ваш первый == конец, и вы делаете * first = * temp, также перемещаете ваш оператор cout на одну строку выше перед * first = * temp, и таким образом вы получите то, что вы хотите на выходе.

0

Мне наконец удалось исправить мою проблему, вот мое решение, спасибо всем за вашу помощь:

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

Снова извините за ошибки.

0

Источник

Accepted Answer

Как упоминается 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 вращает

а, б, в, д, е

в

е, а, б, в, д

Если бы вы использовали, скажем 2 вместо size() - 1 вы получите:

с, д, е, а, б

Также учтите: next_permutation а также prev_permutation если вы не хотите вращаться.

1