Комментарии 15
Код прошедший автоформатирование
#include <stdio.h>
#include <string.h>
int main() {
  char a[] = "4321";
  char d[5];
  int fact = 24;
  int i, j, z;
  int y = 0;
  char c;
  while (y != fact) {
    printf("%s\n", a);
    i = 1;
    while (a[i] > a[i - 1]) {
      i++;
    }
    j = 0;
    while (a[j] < a[i]) {
      j++;
    }
    c = a[j];
    a[j] = a[i];
    a[i] = c;
    strcpy(d, a);
    z = 0;
    for (i -= 1; i > -1; i--) a[z++] = d[i];
    y++;
  }
}
А можно без кода, для дибилов, вроде меня, что всё-таки было сделано, помимо изначальной рекурсивной перестановки? Особенно мне не понравились слова «ешё одна копия массива» в контекстве «оптимизация алгоритма»
А разве Алгоритм индуса является самым эффективным для генерации всех перестановок?

Простой перебор без сравнений и реверса должен быть в разы быстрее.

Не совсем. Рекурсивный перебор довольно медленнее. Ассимптотика точно такая же, но при переборе есть накладные расходы на рекурсию, а главное, на поиск следующего не использованного элемента.

Для n = 13 проверял без вывода, рекурсивный и данный. Рекурсивный быстрее все равно на доли секунд.

Итеративный метод правильно реализован, без копирования? Последний этап разворота части массива у автора сделан весьма не оптимально. Не нужно никакого d и strcopy, а нужно:


j--;
for (i = 0; i < j; i++, j--) {
  c = a[i];
  a[i] = a[j];
  a[j] = c;
}

Итеративный метод сразу в 2 раза ускоряется почти.

Спасибо. Думал об этом, уже после написания. Как четвертый шаг сокращения алгоритма.
Да, все верно. Просто переменные переназначены по другому.
#include <stdio.h>
#include <string.h>
int main() {
        char a[] = "4321";
        char d[9];
        int fact = 24; 
           int i, j, z;
           int y=0;
            char c;
          while (y != fact) {
          printf("%s\n", a);
          i=1;
          while(a[i] > a[i-1]) {
          i++;
          }
          j=0;
          while(a[j] < a[i]) {
          j++;    
          }
      c=a[j];
      a[j]=a[i];
      a[i]=c;

i--;
for (j = 0; j < i; i--, j++) {
  c = a[i];
  a[i] = a[j];
  a[j] = c;
}
y++;  
   }
}
 

Вы скажите, как вы рекурсивный делали, а то он у меня в 10 раз медленее итеративного. Хотя код получился сильно короче, это правда.


Итеративный:
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int n;
char a[15];
int nn;
int count;

void Gen() {
    int i, j;
    nn = n-1;
    for (i = 0; i < n; i++)
    a[i] = i;
    char c;
    while (true) {
        // Output;
        //for (i = 0; i < n; i++)
        //    cout << (int)a[i] << ' ';
        //cout << '\n';
        count++;
        i = nn;
        while ((i > 0) && (a[i] < a[i-1])) 
            i--;
        if (i == 0) break;
        j = nn;
        i--;
        while (a[j] < a[i]) 
            j--;
        c = a[j];
        a[j] = a[i];
        a[i] = c;
        i++;
        j = nn;
        while (i < j) {
            c = a[i];
            a[i] = a[j];
            a[j] = c;
            i++;
            j--;
        }
    }
    cout << count << "\n";
}

int main() {
    clock_t beg = clock();
    n = 12;
    Gen();
    clock_t total = clock() - beg;
    cout << float(total) / CLOCKS_PER_SEC << "\n";
}

Рекурсивный
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int n;
char a[15];
bool fr[15];
int count;

void Gen(int i) {
    if (i == n) {
/*        for (int k = 0; k < n; k++)
            cout << (int)a[k] << " ";
        cout << "\n";*/
        count++;
        return;
    }
    for (int j = 0; j < n; j++) {
        if (fr[j]) {
            fr[j] = false;
            a[i] = j;
            Gen(i+1);
            fr[j] = true;
        }
    }
}

int main() {
    clock_t beg = clock();    
    n = 12;
    for (int i = 0; i < n; i++)
        fr[i] = true;
    Gen(0);
    cout << count << "\n";
    clock_t total = clock() - beg;
    cout << float(total) / CLOCKS_PER_SEC << "\n";
}

Результаты n=12
perm-recursive.exe
479001600
9.93

perm-iterative.exe
479001600
1.392
Рекурсивный брал отсюда.
http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
Похоже с вашим вариантом оборота будет быстрее. Завтра проверю.

Отличный метод! Никаких проверок лишних элементов вообще. Это просто гениально. Но все-равно, он в 2 раза медленнее итеративной реализации. С учетом лишнего копирования, как раз они и будут примерно равны, как у вас.


Результат
>iterative
479001600
1.392
>recursive2
479001600
3.727

Код для тестирования
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int n;
char a[15];
int count;

void Gen(int i) {
    if (i == n) {
/*        for (int k = 0; k < n; k++)
            cout << (int)a[k] << " ";
        cout << "\n";*/
        count++;
        return;
    }
    char c;
    for (int j = i; j < n; j++) {
        c = a[j];
        a[j] = a[i];
        a[i] = c;
        Gen(i+1);
        c = a[j];
        a[j] = a[i];
        a[i] = c;
    }
}

int main() {
    clock_t beg = clock();    
    n = 12;
    for (int i = 0; i < n; i++)
        a[i] = i;
    Gen(0);
    cout << count << "\n";
    clock_t total = clock() - beg;
    cout << float(total) / CLOCKS_PER_SEC << "\n";
}
Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.
real 1m51.157s
user 0m4.060s
sys 0m24.410s

Но без вывода ваша правда
для n=12
С вашим вариантом оборота
real 0m8.763s
user 0m8.730s
sys 0m0.010s

Со strcpy
real 0m13.756s
user 0m13.720s
sys 0m0.000s

Прирост сразу существенный.
Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.


Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.

Вывод в терминал вообще очень тормознутый. Ничего с ним мерять нельзя.


Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.

Там еще каждую итерацию проверка на терминальный нулевой символ. Какой-нибудь memcpy() с фиксированным размером будет заметно быстрее. Вот тут бы никакого прироста почти и не было бы от удалиения.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.