Генератор перестановок на С

Question

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

Answer 1

Переставляет числа:

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

#include <stdio.h>
#include <stdlib.h>

/**
   Read a number, N, from standard input and print the
   permutations.
 */

void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
} // print


void swap(int *v, const int i, const int j)
{
  int t;
  t = v[i];
  v[i] = v[j];
  v[j] = t;
}


void rotateLeft(int *v, const int start, const int n)
{
  int tmp = v[start];
  for (int i = start; i < n-1; i++) {
    v[i] = v[i+1];
  }
  v[n-1] = tmp;
} // rotateLeft


void permute(int *v, const int start, const int n)
{
  print(v, n);
  if (start < n) {
    int i, j;
    for (i = n-2; i >= start; i--) {
      for (j = i + 1; j < n; j++) {
    swap(v, i, j);
    permute(v, i+1, n);
      } // for j
      rotateLeft(v, i, n);
    } // for i
  }
} // permute


void init(int *v, int N)
{
  for (int i = 0; i < N; i++) {
    v[i] = i+1;
  }
} // init


int main()
{
    int *v = (int*) malloc(sizeof(int)*10);
    init(v, 10);
    permute(v, 0, 10);
    free(v);
}

Answer 2

все

Я нашел алгоритмы для генерации перестановок в лексикографическом порядке из «Искусства компьютерного программирования» (TAOCP):

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Генерация в лексикографическомorder Есть много способов систематически генерировать все перестановки данной последовательности [цитата нужна].Один классический алгоритм, который является одновременно простым и гибким, основан на нахождении следующей перестановки в лексикографическом порядке, если он существует.Он может обрабатывать повторяющиеся значения, и в этом случае он генерирует различные перестановки мультимножества каждый раз.Даже для обычных перестановок это значительно более эффективно, чем генерирование значений для кода Лемера в лексикографическом порядке (возможно, с использованием факториальной системы счисления) и преобразование их в перестановки.Чтобы использовать его, нужно начать с сортировки последовательности в (слабо) возрастающем порядке (что дает ее лексикографически минимальную перестановку), а затем повторить переход к следующей перестановке, пока она найдена.Этот метод восходит к Нараяне Пандиту в Индии в 14 веке и с тех пор часто переоткрывается.

Следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки.Он изменяет данную перестановку на месте.

1. Найдите наибольший индекс k такой, что a [k] Найдите наибольший индекс l такой, что a [k] Поменяйте местами a [k] с [l].
2. Обратный порядок последовательности от a [k +1] до и включая последний элемент a [n].

После шага 1 известно, что все элементы строго после позиции k образуют слабо убывающую последовательность, поэтому перестановка этих элементов отсутствуетсделает это заранее в лексикографическом порядке;чтобы продвинуться, нужно увеличить [k].Шаг 2 находит наименьшее значение a [l] для замены a [k] на, а при их замене на шаге 3 последовательность после позиции k остается в слабо убывающем порядке.Обращение этой последовательности на шаге 4 приводит к ее лексикографически минимальной перестановке и лексикографическому преемнику начального состояния для всей последовательности

Answer 3

Это классический алгоритм, найденный (среди других мест) в TAOCP Кнута.

Вот пример, который я использовал для задачи проекта Эйлера. Он создает все перестановки строки в лексикографическом порядке и выводит их на стандартный вывод.

#include<stdio.h>
int main()
{
        char set[10]="0123456789";
        char scratch;
        int lastpermutation = 0;
        int i, j, k, l;
        printf("%s\n",set);
        while (!lastpermutation)
        {
                //find largest j such that set[j] < set[j+1]; if no such j then done
                j = -1;
                for (i = 0; i < 10; i++)
                {
                        if (set[i+1] > set[i])
                        {
                                j = i;
                        }
                }
                if (j == -1)
                {
                        lastpermutation = 1;
                }
                if (!lastpermutation)
                {
                        for (i = j+1; i < 10; i++)
                        {
                                if (set[i] > set[j])
                                {
                                        l = i;
                                }
                        }
                        scratch = set[j];
                        set[j] = set[l];
                        set[l] = scratch;
                        //reverse j+1 to end
                        k = (9-j)/2; // number of pairs to swap
                        for (i = 0; i < k; i++)
                        {
                                scratch = set[j+1+i];
                                set[j+1+i] = set[9-i];
                                set[9-i] = scratch;
                        }
                        printf("%s\n",set);
             }
        }
        return 0;
}

Answer 4

Вот простое рекурсивное решение для получения всех перестановок набора символов, передаваемых в командной строке:

#include <stdio.h>
#include <string.h>

int perm(const char *src, int len, char *dest, char *destbits, int n) {
    if (n == len) {
        printf("%.*s\n", len, dest);
        return 1;
    } else {
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (destbits[i] == 0) {
                destbits[i] = 1;
                dest[n] = src[i];
                count += perm(src, len, dest, destbits, n + 1);
                destbits[i] = 0;
            }
        }
        return count;
    }
}

int main(int argc, char *argv[]) {
    const char *src = (argc > 1) ? argv[1] : "123456789";
    int len = strlen(src);
    char dest[len], destbits[len];

    memset(destbits, 0, sizeof destbits);
    int total = perm(src, len, dest, destbits, 0);
    printf("%d combinations\n", total);

    return 0;
}