Генерация перестановок

Алгоритмизация / Генерация перестановок

 

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N!. Действительно:

  • на первое место может быть помещен любой из N элементов (всего вариантов N),
  • на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1)),
  • если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1, то есть всего N! перестановок.

 
Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N, а последней — N N-1 … 1.

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

  • Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
  • Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
  • Поменять местами два полученных элемента.
  • Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
  int s = a[i];
  a[i] = a[j];
  a[j] = s;
}
bool NextSet(int *a, int n)
{
  int j = n - 2;
  while (j != -1 && a[j] >= a[j + 1]) j--;
  if (j == -1)
    return false; // больше перестановок нет
  int k = n - 1;
  while (a[j] >= a[k]) k--;
  swap(a, j, k);
  int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
  while (l<r)
    swap(a, l++, r--);
  return true;
}
void Print(int *a, int n)  // вывод перестановки
{
  static int num = 1; // номер перестановки
  cout.width(3); // ширина поля вывода номера перестановки
  cout << num++ << ": ";
  for (int i = 0; i < n; i++)
    cout << a[i] << " ";
  cout << endl;
}
int main() 
{
  int n, *a;
  cout << "N = ";
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = i + 1;
  Print(a, n);
  while (NextSet(a, n))
    Print(a, n);
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Перестановка без повторений

 

Перестановки с повторениями

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n1, n2... nk, где элемент n1 повторяется r1 раз, n2 повторяется r2 раз и т.д. При этом n1+n2+...+nk=N.  Если мы будем считать все n1+n2+...+nk элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n1+n2+...+nk)! . Однако среди этих перестановок не все различны. В самом деле, все r1 элементов n1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n2, n3 и т. д. В итоге имеем r1! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n1. Таким образом, всякая перестановка может быть записана r1!·r2!·...·rk! способами. Следовательно, число различных перестановок с повторениями равно

Число перестановок с повторениями

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
  int s = a[i];
  a[i] = a[j];
  a[j] = s;
}
bool NextSet(int *a, int n)
{
  int j = n - 2;
  while (j != -1 && a[j] >= a[j + 1]) j--;
  if (j == -1)
    return false; // больше перестановок нет
  int k = n - 1;
  while (a[j] >= a[k]) k--;
  swap(a, j, k);
  int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
  while (l<r)
    swap(a, l++, r--);
  return true;
}
void Print(int *a, int n)  // вывод перестановки
{
  static int num = 1; // номер перестановки
  cout.width(3); // ширина поля вывода номера перестановки
  cout << num++ << ": ";
  for (int i = 0; i < n; i++)
    cout << a[i] << " ";
  cout << endl;
}
int main() 
{
  int n, *a;
  cout << "N = ";
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = i + 1;
  a[1] = 1; // повторяющийся элемент
  Print(a, n);
  while (NextSet(a, n))
    Print(a, n);
  cin.get(); cin.get();
  return 0;
}

Результат работы приведенного выше алгоритма:
Перестановка с повторениями


Назад: Алгоритмизация

Комментариев к записи: 19

  • 3D Mountain Bike
    В вашем первом посте приведен алгоритм получения одной перестановки из другой. В алгоритме получения всех перестановок множества это только часть задачи.

    • Елена Вставская
      Этот алгоритм предназначен для получения следующей перестановки в лексикографическом порядке. Для генерации всех перестановок функция NestSet() должна вызываться в цикле. Условием выхода из цикла является значение false, которое возвращает функция NestSet(), что означает, что больше перестановок не найдено.

  • Алгоритм перестановки с повторениями немного неправильно работает, ибо P(4)=12600, а не 12.

  • Здравствуйте Вы не могли бы мне помочь с этой программой не могу понять что и как ! Мне нужно определить последовательности для 5 чисел (1,2,3,4,5)! Спасибо . напишите на почту !

  • Спасибо Вам Огромное  Елена за тот невероятный потенциал который Вы привносите. Спасибо огромное за Вашу отзывчивость и оказанную помощь. С Уважением адъюнкт Военной Академии  г. Санкт-Петербург (капитан Романов Р.С.)

  • Вебер Владимир
    Просто и красиво. Главное - короткая программа. Жаль немного, что это не на Паскале, но ничего. Спасибо.

  • https://github.com/dcc0/permutations/tree/master/.gitignore Перестановки с повторением и без. Итеративно. Без рекурсии.

  • Там же в репозитариях аккаунта размещения, сочетания, разбиения, композиции. Все прокомментировано на русском и английском. Всего 8 переборных алгоритмов классической комбинаторики: https://github.com/dcc0 Надеюсь, кому-нибудь пригодится.

  • Добрый днь. подскажите как сделать перестановку слов от 1 до 5? к примеру 1цифра это одно слово. имеется 4 слова. нужно: 1 2 3 4 11 12 21 31 32 43 14 41 111 124 431 444 431 и т.д.

    • Елена Вставская
      А где например 22, 13, 33, 44? Из каких соображений эти перестановки опущены? И почему 431 два раза?

      • привел просто пример. так они идут по порядку. (слишком много вариантов). т.е. начинаются с 1 слово и заканчивается 5. (к примеру имеется 4 слова (dog cat duck banana) и их нужно перемешать со все возможными вариантами от 1 до 5)

        • Елена Вставская
          Посмотрите алгоритм <a href="/placement/" rel="nofollow">генерации размещений с повторениями</a>. Нужно вызвать этот алгоритм для M=1, 2, 3, 4. Ну, а чтоб связать со словами, каждому значению поставить в соответствие слово: строка 22 изменится на
          1
          2
          3
          4
          5
          6
          7
          switch(a[i])
          {
          case 1: cout << word1 << "  "break;
          case 2: cout << word2 << " "break;
          case 3: cout << word3 << " "break;
          case 4: cout << word4 << " "break;
          }

  • У меня очень сложно. Пожалуйста сжелайте ВСЕ возможные варианты чисел от 1 до 20. Причём каждый вариант должен быть по четыре цифры, т.е. 1234 2341 И тд. ВСЕ ВОЗМОЖНЫЕ варианты до 20. Спасибо. Я знаю это очень тяжело. Отправьте в почту пожалуйста

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <stdio.h>
    #include <malloc.h>

    void swapInts(int pos1, int pos2, int arr[]) {
      int temp = arr[pos1];
      arr[pos1] = arr[pos2];
      arr[pos2] = temp;
    }

    void printArray(int length, int arr[]) {
      for (int i=0; i < length; i++) {
        printf("%d ", arr[i]);
      }
      putchar('\n');
    }

    void printPermutations(int index, int length, int arr[]) {
      if (index == length) {
        printArray(length, arr);
        return;
      }
      for (int i=index; i < length; i++) {
        swapInts(i, index, arr);
        printPermutations(index + 1, length, arr);
        swapInts(i, index, arr);
      }
    }

    int main(int argc, char *argv[]) {
      int length;
      printf("Type length of array: ");
      scanf("%d", &length);
      int *arr = malloc(length*sizeof(int));
      printf("Type elements of array: ");
      for (int i=0; i < length; i++) {
        scanf("%d", &arr[i]);
      }
      printPermutations(0, length, arr);
      return 0;
    }

  • Евгения
    Имеется перестановка с особенностью, например n(6)=123456. Особенность в том, что члены, стоящие на нечетных позициях меньше членов стоящих на четных. Подскажите, как модифицировать приведенный Вами алгоритм, чтобы все получаемые последующие перестановки сохраняли это же свойство. Общее число таких перестановок существенно меньше N=6!/(3!*2!*2!*2!)=15 (Производные перестановки, например от 123456: 125634,563412,345612 и т.д. считаются неразличимыми и могут не вычисляться). Метод "грубой силы" когда каждая перестановка проверяется на соблюдение этого условия не подходит, т.к. в реале уже при n(>10) работает очень медленно. Мне не нужна программа. Достаточно идеи.Или может дадите ссылки?

    • Елена Вставская
      Ну, допустим таких перестановок будет не 15, а 90 :) И если известно число n, то более эффективно использовать вложенные циклы, а не рекурсию:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50

      #include <iostream> 
      using namespace std;
      int main()
      {
        int count = 1;
        for (int n1 = 1; n1 <= 6; n1++)
        {
          for (int n2 = 1; n2  <= 6; n2++)
          {
            if (n2 == n1) continue;
            for (int n3 = 1; n3 <= 6; n3++)
            {
              if (n3 == n1) continue;
              if (n3 == n2) continue;
              for (int n4 = 1; n4  <= 6; n4++)
              {
                if (n4 == n1) continue;
                if (n4 == n2) continue;
                if (n4 == n3) continue;
                for (int n5 = 1; n5  <= 6; n5++)
                {
                  if (n5 == n1) continue;
                  if (n5 == n2) continue;
                  if (n5 == n3) continue;
                  if (n5 == n4) continue;
                  for (int n6 = 1; n6  <= 6; n6++)
                  {
                    if (n6 == n1) continue;
                    if (n6 == n2) continue;
                    if (n6 == n3) continue;
                    if (n6 == n4) continue;
                    if (n6 == n5) continue;
                    if (n1 > n2) continue;
                    if (n3 > n4) continue;
                    if (n5 > n6) continue;
                    cout << fixed;
                    cout.width(3);
                    cout << count++ << ": ";
                    cout << n1 << " " << n2 << " " << n3 << " ";
                    cout << n4 << " " << n5 << " " << n6 << endl;
                  }
                }
              }
            }
          }
        }
        getchar();
        return 0;
      }

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *