Красивый и простой способ перестановки с рекурсией


Я хочу поделиться лучший вариант перестановки с вами.

Вчера, когда я читал Хоровица основы структуры данных в C++, и я заметил, что в результате код, на стр. 32, в книге нет того, что я хочу.

Например, если у меня есть массив {'а', 'б', 'с'}, то результатом его является:

abc
acb
bac
bca
cba
cab

Обратите внимание, что в последних двух случаях не соответствуют тому, что я хочу: если 'c' является фиксированной, все остальные буквы в свои права следует начинать с относительно того, \долл \л б \л с \ЛТ \лдоц \ЛТ з\$, так что результат должен быть:

...
cab
cba

Вот мой код, который корректирует порядок с два модифицированных ОСП:

#include <iostream>
using namespace std;

void printPermutation(char *a, const int k, const int m);
void swap2(char *a, const int l, const int r);
void swap3(char *a, const int l, const int r);

int main() {
    char str[] = {'a', 'b', 'c', 'd', 'e'};
    printPermutation(&str[0], 0, sizeof(str)-1);
    return 0;
}

void printPermutation(char *a, const int k, const int m) {
    if (k == m) {
        for (int i = 0; i <= m; i++) {
            cout << a[i];
        }
        cout << endl;
    }
    else {
        for (int i = k; i <= m; i++) {
            // the code in the book just use swap, but I change them.
            swap2(a, k, i); // here
            printPermutation(a, k+1, m);
            swap3(a, k, i); // and here
        }
    }
}

// swap2 will move the element at index r to l,
// by continuously swap with element at its left
void swap2(char *a, const int l, const int r) {
    for (int i = r; l < i; i--) {
        swap(a[i], a[i-1]);
    }
}

// The same concept with swap2, but from left to right
void swap3(char *a, const int l, const int r) {
    for (int i = l; i < r; i++) {
        swap(a[i], a[i+1]);
    }
}

Как я могу еще больше упростить код?

Мне нравится идея, что автор использовал рекурсию, чтобы сделать вещи красиво простые. Но для достижения результата я хочу, как было описано выше, я должен добавить два дополнительных, немного похожие, функции.



3028
8
задан 10 марта 2018 в 03:03 Источник Поделиться
Комментарии
2 ответа

Чем проще код будет выглядеть примерно так:

#include <string>
#include <algorithm>
#include <iostream>

int main() {
std::string s = "abcde";

while (std::next_permutation(s.begin(), s.end()))
std::cout << s << "\n";
}

Если вы хотели сделать что-то на том же общем порядке в качестве генератора Python, вы бы использовать C++'S новый поддержка сопрограмм. Что в настоящее время включен (по желанию) на очень низком уровне, поэтому необходимо достаточное количество инфраструктуры на нем, прежде чем это легко написать на Python-как генератор.

Чтобы не быть похороненным в подробности вы, вероятно, не заботятся о (прямо сейчас) я использую Кенни Керр Generator класс (первое 173 линий, пересаживают в заголовке). Используя его, мы получаем нечто вроде этого:

#include "generator.hpp"
#include <iostream>
#include <string>
#include <algorithm>

template <class T>
generator<T> perm(T initial) {
while (std::next_permutation(initial.begin(), initial.end()))
co_yield initial;
}

int main() {
using namespace std::literals;
for (auto const &i : perm("abcde"s))
std::cout << i << "\n";
}

Как на ваш код, несколько пунктов выпрыгнуть:


  1. Не использовать std::endl. Он сбрасывает поток, который вы почти никогда не хочу. Просто использовать '\n'. В редких случаях, что вы хотите сбросить поток, использовать std::flush.

  2. Библиотека c резервы большинства имен, которые начинаются с strтак это, наверное, лучше не использовать это как имя.

  3. using namespace std; широко рассмотрены проблемы, за исключением небольшого числа довольно необычные обстоятельства.

  4. Если вы действительно хотите этого делать (больше) на свой собственный, вы, возможно, захотите взглянуть на std::rotate, которая может заменить ваши swap2 и swap3. std::rotate также, как правило, быть более эффективным, чем реализация.

  5. swap2 и swap3 поразили меня плохие имена. На первый взгляд, кажется, что rotate_left и rotate_right вероятно, будет лучше имена (а также см. выше).

13
ответ дан 10 марта 2018 в 04:03 Источник Поделиться

Я нахожу перестановок так весело и увлекательно, так что это довольно прохладно.

Я собирался сказать, что большинство из того, что @Джерри гроб сказал, так, а не повторять все это, я просто отмечу несколько вещей:


  • Ваш str переменная в main() выглядит как типичная нуль-терминированная строка C, но не. Он даже назвал str дальнейшей путаницы. Если будущему застройщику было позвонить, сказать, strlen() на нем, вероятно, аварии. Я бы переименовать его.

  • Ваши имена переменных зашифрованы. Что k и m в printPermutation()? Они индексы в a (тоже ужасное имя) на начало и конец перестановки. Я предлагаю переименовать их в что-то вроде startIndex и endIndex.

  • Также с l и r в swap2() и swap3().

  • Как было отмечено, swap2() и swap3() на самом деле поворот, нежели своп. Несмотря на это, имена подразумевают, что они делают что-то с 2 и 3 параметры, но это не так. Вы должны не просто добавлять номер к существующему аналогичную функцию, чтобы получить новое имя. Это антипаттерн, который сохраняется в программировании.

Один из способов вы могли бы сделать это более полезным сделать шаблонных функций для перестановки таким образом, что они работают на контейнеры любого типа. (Я предполагаю, что это то, что std::permutation() делает - но это всегда весело, чтобы учиться на собственных!)

7
ответ дан 10 марта 2018 в 05:03 Источник Поделиться