Как найти все перестановки чисел - Исправление недочетов и поиск решений вместе с Examum.ru

Как перебрать все перестановки и о факториальном разложении натуральных чисел

Время на прочтение
3 мин

Количество просмотров 26K

Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок n предметов равно попросту факториалу числа n

n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1

Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Как видно, факториал 13-ти уже не умещается в тип данных long.

Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.

Для начала вспомним понятие позиционной системы счисления. Вклад каждого разряда числа в его значение в позиционной системе по основанию K есть разряд, умноженный на основание K в степени, равной позиции разряда в записи числа. Основание системы счисления обычно пишут как подстрочный индекс, таким образом

1966₁₀ = 1*10³ + 9 * 10² + 6 * 10¹ + 6 (*10⁰)

10110001₂ = 1 * 2⁷ + 0 * 2⁶ + 1 * 2⁵ + 1 * 2⁴ + 0 * 2³ + 0 * 2² + 0 * 2¹ + 1 * 2⁰ (=177₁₀)

Позиционная запись, помимо компактности, обладает тем бесценным свойством, что алгоритм выполнения арифметических операций оказывается чрезвычайно простым (есть историческая байка, что в школах средневековья изучение арифметики занимало несколько лет, поскольку вычисления над числами в НЕпозиционной римской записи имели множество правил для того, чтобы провести простое сложение!)

Оказывается, существует, и является однозначным разложение и способ записи числа, в котором каждый разряд в таком его представлении умножается на ФАКТОРИАЛ номера позиции.

Покажем это на примерах:

1985 = 2 * 6! + 4 * 5! + 2 * 4! + 2 * 3! + 2 * 2! + 1 * 1!

2 940 861 129 405 = 2*15! + 3*14! + 10*13! + 3*12! + 6*11! + 8*10! + 4*9! + 8*8! + 0*7! + 2*6! + 2*5! + 1*4! + 3*3! + 1*2! + 1*1!

В обычной позиционной системе значение каждого разряда должно быть строго меньше основания. В факториальной же системе каждый «разряд» меньше либо равен основанию факториала, перед которым он стоит. При этом действуют обычные для сложения правила переноса разряда при переполнении.

Более математически строго: каждое натуральное число n можно единственным образом представить в виде следующей суммы:

где
k_m <= m – коэффициент при m! — он же разряд числа в его факториальном представлении,
p – количество «разрядов» в числе в его факториальном представлении
то есть число записывается как k_p k_p-1 k_p-2… k₂ k₁

Теперь опишем, как использовать факториальное представление (разложение) числа для генерации соответствующей перестановки. Расположим n элементов в порядке возрастания индекса от 1 до n. Для каждого числа в диапазоне 0..n!-1 произведем факториальное разложение, вычислив его коэффициенты k_m. В разложении нуля коэффициенты k_m будут все нули, в разложении числа n!-1 все k_m = m, m меняется в диапазоне от 0 до n-1. Теперь поместим элемент с номером m на место с номером k_m+1, считая лишь свободные места, оставшиеся к этому шагу. Фактически, эта процедура повторяет рассуждения, которые приводятся при вычислении числа возможных перестановок из n элементов – первый элемент может быть размещен n способами, второй – (n-1) способом и так далее. Таким образом, мы получим все возможные перестановки из n несовпадающих элементов.

Проиллюстрируем это для 5 предметов (120 вариантов перестановок) и перестановки №77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!

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

Источник

Перестановка – это комбинация элементов из 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 элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n₁, n₂… n_k, где элемент n₁ повторяется r₁ раз, n₂ повторяется r₂ раз и т.д. При этом n₁+n₂+…+n_k=N. Если мы будем считать все n₁+n₂+…+n_k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n₁+n₂+…+n_k)! . Однако среди этих перестановок не все различны. В самом деле, все r₁ элементов n₁ мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n₂, n₃ и т. д. В итоге имеем r₁! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n₁. Таким образом, всякая перестановка может быть записана r₁!·r₂!·…·r_k! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив 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;
}

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

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

Источник

Формула числа перестановок

Полезная страница? Сохрани или расскажи друзьям

Определение факториала и числа перестановок

Пусть имеется $n$ различных объектов.
Будем переставлять их всеми возможными способами (число и состав объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно

$$P_n=n!=1cdot 2cdot 3 cdot … cdot (n-1) cdot n$$

Символ $n!$ называется факториалом и обозначает произведение всех целых чисел от $1$ до $n$. По определению, считают, что $0!=1, 1!=1$. Факториал растет невероятно быстро (недаром он обозначается восклицательным знаком!), например,
$$10!=3628800,$$ а $$50!=30414093201713378043612608166064768844377641568960512000000000000.$$ Как найти факториал? Умножать вручную, использовать функцию ФАКТР() в Excel или, если устанете умножать самостоятельно, используйте калькулятор ниже.

Пример всех перестановок из $n=3$ объектов (различных фигур) — на картинке справа. Согласно формуле ниже, их должно быть ровно $P_3=3!=1cdot 2cdot 3 =6$, так и получается (вам не напоминает картинка табло игральных автоматов?:)).

Общая формула, которая позволяет найти число перестановок из $n$ элементов, имеет вид (она же — формула для факториала числа $n$):

$$P_n=n!=1cdot 2cdot 3 cdot … cdot (n-1) cdot n.$$

Чтобы вычислить число перестановок $P_n$ онлайн, используйте калькулятор ниже.

Видеоролик о перестановках и Excel

Не все понятно? Посмотрите наш видеообзор для формулы перестановок: как использовать Excel для нахождения факториала и числа перестановок, как решать типовые задачи и использовать онлайн-калькулятор.

Расчетный файл из видео можно бесплатно скачать

Смотрите также: Факториал в Excel

Полезные ссылки

Как решать задачи по комбинаторике?
Основные формулы комбинаторики
Примеры решений
Заказать контрольную

Лучшее спасибо — порекомендовать эту страницу

Поиск решенных задач

Решебник по комбинаторике и теории вероятностей:

Источник

Анализ данных • 31 января 2023 • 5 мин чтения

Основы комбинаторики: перестановки, размещения, сочетания

Чтобы работать с теорией вероятностей и статистикой, нужно знать принципы комбинаторики — науки о подсчёте количества всевозможных комбинаций элементов.

Факториал, правила суммы и произведения
Перестановка
Размещение
Сочетание
Как использовать перестановки, размещения и сочетания в анализе данных
Совет эксперта

Факториал, правила суммы и произведения

Для таких расчётов понадобятся несколько понятий и правил.

Факториал натурального числа n — это произведение всех натуральных чисел от до n. Порядок множителей значения не имеет. Такое произведение обозначается через n!.

Самые популярные факториалы

Рекуррентная формула факториала

В этой формуле для получения следующего элемента необходимо знать предыдущий.

Правило суммы — если объект A можно выбрать способами, а объект B можно выбрать способами, то объект «A или B» можно выбрать n + m способами.

Правило произведения — если объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами, то для пары «A и B» есть n ∙ m вариантов выбора.

Когда важно одно или другое — варианты выбора складываются, когда одно и другое — умножаются. Оба правила позволяют найти, сколько есть вариантов на выбор или, например, сколько есть способов различного расположения предметов.

Получить больше практики по расчёту количества комбинаций можно в модуле «Комбинаторика» тренажёра «Основы математики для цифровых профессий».

Повторите математику, чтобы решать рабочие задачи

Вспомните проценты, алгебру и другие темы посложнее в бесплатном тренажёре «Основы математики для цифровых профессий».

Перестановка

Перестановка n объектов/элементов — это способ их последовательного расположения с учётом порядка. Например, abc, bca и cab — это разные перестановки трёх букв.

Перестановку n объектов ещё называют перестановкой длины n. Количество всех таких перестановок обозначается как Pₙ.

Пример. На странице интернет-магазина одежды размещены три футболки. Если поменять их расположение на странице, получится новая перестановка. Сколькими способами можно расположить футболки на странице?

Решение. Три футболки можно расположить на странице способами: P₃ = 3! = 1 ∙ 2 ∙ 3.

Пример. Чтобы выполнить ежедневный квест, игроку нужно принести магу корзину с четырьмя кристаллами разного цвета. Первой необходимо найти корзину, а кристаллы можно сложить в неё в произвольном порядке. Как найти число способов выполнить задание?

Решение. Для выполнения квеста нужно 5 предметов. Корзину всегда находят первой, поэтому её позиция зафиксирована. Порядок сбора 4 оставшихся предметов равен числу перестановок 4 элементов. Всего есть 4! = 24 способа выполнить задание.

Размещение

Когда порядок расстановки важен, говорят о размещении.

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

Количество размещений из n по k обозначают и вычисляют так:

В отличие от перестановки, у размещения два параметра: из скольких элементов выбирают (n) и сколько именно выбирают (k).

Порядок выбора элементов важен, когда:

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

Пример. Недалеко от пользователя есть 9 ресторанов. Из них надо выбрать 4, которые будут отображаться на главном экране. Сколько есть способов выбрать рестораны?

Решение. Порядок выбора важен, поэтому выбрать четыре ресторана поможет правило произведения: существует 9 ∙ 8 ∙ 7 ∙ 6 = 3024 способа. Это как раз и есть количество размещений из 9 по 4.

Пример. Сколькими способами можно заполнить спортивный пьедестал из трёх мест, если есть 10 претендентов?

Решение. Выбрать упорядоченную тройку можно 10 ∙ 9 ∙ 8 = 720 способами. По формуле для количества размещений это считается так:

Сочетание

Когда порядок выбора или расположения не важен, говорят о сочетании.

Сочетание из n по k — это неупорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть набор, для которого порядок выбора не имеет значения.

Количество сочетаний из n по k обозначают и вычисляют так:

Несколько частных значений для количества сочетаний:

Порядок выбора или расстановки не важен, когда:

● Выбирают несколько элементов одновременно. В учебниках по математике самый частый пример — мешок с шариками, откуда вытаскивают несколько шариков разом.
● Выбирают пару (тройку, группу) для взаимного или равноправного процесса. Например, двух человек для партии в шахматы, две команды для игры в хоккей, три бренда одежды для коллаборации, две точки для соединения отрезком, пять человек для хора.

Пример. Из 9 актёров выбирают четырёх для массовки. Порядок выбранных людей не важен. Сколько есть способов выбрать актёров?

Решение. Чтобы получить количество вариантов выбора 4 из 9 без учёта порядка, нужно

Это количество сочетаний из 9 по 4: сначала нашли количество способов выбрать 4 из 9, потом «склеили» все варианты с одним набором актёров, но разным порядком.

Пример. В сувенирном магазине продаются 6 видов кружек. Сколько есть способов выбрать 4 разные?

Решение. Общее количество перестановок для 6 элементов нужно разделить на (6 – 4)! и ещё на 4!, так как не нужно учитывать ни перестановки «невыбираемых» кружек, ни порядок среди выбираемых.

Поэтому для выбора 4 кружек из 6 есть

А если надо выбрать только 2 разные кружки?

Ответ получился такой же, потому что множители в знаменателе просто поменялись местами.

У этого есть и логическое обоснование: например, выбрать 4 кружки из 6 (и купить их) — это то же самое, что выбрать 2 кружки из 6 (и не купить их).

Аналогично получится, что

В общем виде это свойство выглядит так:

Его называют свойством симметрии для количества сочетаний.

Как использовать перестановки, размещения и сочетания в анализе данных

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

Комбинаторика вместе с другими дисциплинами из дискретной математики используется для построения алгоритмов. Например, алгоритмов поиска оптимального маршрута или оптимизации цепей поставок.

Комбинаторику применяют для оценки времени работы алгоритмов и для их ускорения. Это помогает делать эффективнее работу поисковых систем, голосовых помощников, навигаторов и других сервисов.

Совет эксперта

Диана Миронидис
Выбирать приходится каждый день: сколько блюд получится сделать из продуктов в холодильнике, сколькими способами можно добраться до работы — ответы на все эти вопросы даёт комбинаторика. Это отличный фундамент для изучения анализа данных и тех областей математики, которые связаны с теорией вероятностей и статистикой. Например, чтобы работать с биномиальным распределением, нужно знать, что такое биномиальные коэффициенты и как их находить. А это как раз комбинаторные задачи.

Автор и методист курсов по математике

Совместные и несовместные события в анализе данных

Как пересечение и объединение множеств используются в анализе данных

Источник

0 / 0 / 0

Регистрация: 09.05.2009

Сообщений: 72

Найти все возможные перестановки цифр

12.02.2010, 01:35. Показов 12624. Ответов 12

дано 6-розрядное число…надо найти все возможные перестановки цыфр…как ето организовать???помогите пожалуста!

insideone

3685 / 962 / 114

Регистрация: 10.01.2010

Сообщений: 2,550

12.02.2010, 02:13

В это время могу предложить лишь такую реализацию

C++

int x = 123456;
char str[7] = { 0 };
itoa(x, &str[0], 10);
for (int i = 0; i < 7; i++
{
   for (int j =0; j < 7; j++)
   {
       if ( i != j )
       {
          // тут нужно поменять в строке i и j символы
          // Распечатать эту строку
          // поменять эти символы обратно чтобы строка приняла исходный вид
       }
}

0 / 0 / 0

Регистрация: 09.05.2009

Сообщений: 72

12.02.2010, 15:05

[ТС]

можна и по другому поставить задачу..найти все возможные перестановки елементов масыва с 6 елементов!!!!!

Добавлено через 1 час 26 минут
не роботает!!!

3685 / 962 / 114

Регистрация: 10.01.2010

Сообщений: 2,550

12.02.2010, 18:32

Конечно не работает, замените комментарии на реальные действия. Это алгоритм а не готовый код. Готовые коды делают в соответствующих разделах. А алгоритм просто делает все возможные перестановки. Вернее алгоритм в цикле меняет 2 числа — номера элементов. Если номера элементов разные — значит их можно поменять местами Меняем — печатаем.

hugo007

0 / 0 / 0

Регистрация: 09.05.2009

Сообщений: 72

12.02.2010, 18:49

[ТС]

C++

#include <stdio.h>
#include <conio.h>
void new1 (int *);
void print(int*);
void rek(int);
void main(void)
{
    int n,temp;
    int m[4]={1,2,3,4};
    int i,j;
    clrscr();
    for(i=0;i<4;i++) {
        for(j=0;j<4;j++) {
            if(i!=j) {
                 temp=m[i];
                 m[i]=m[j];
                 m[j]=temp;
                 print(m);
                 new1(m);
            }
        }
        printf("n");
    }
 
}
void print(int *m)
{
    int i;
    for(i=0;i<4;i++)
        printf("%d  ",m[i]);
        printf("/");
}
void new1(int *m)
{
    int i;
    for(i=0;i<4;i++)
        m[i]=i+1;
}

так????

insideone

3685 / 962 / 114

Регистрация: 10.01.2010

Сообщений: 2,550

12.02.2010, 18:54

Мне кажется немного не так

C++

for(i=0;i<4;i++)
{
      for(j=0;j<4;j++)
      {
         if(i!=j)
         {
            temp=m[i];
            m[i]=m[j];
            m[j]=temp;
            printf("%d ",m[i]);
            temp=m[i];
            m[i]=m[j];
            m[j]=temp;
         }
      }
}

Помещайте код в [CODE]… тут код …[/CODE] для того чтобы код был читабельным

1177 / 987 / 83

Регистрация: 29.10.2009

Сообщений: 1,385

15.02.2010, 18:26

insideone, если взять 6-элементное множество, то перестановок должно быть 6! = 720
А по твоему алгоритму (for.. j<6…) получится только 6*6 — 6 = 30

3685 / 962 / 114

Регистрация: 10.01.2010

Сообщений: 2,550

15.02.2010, 18:39

Хм… я тут подумал как это можно сделать. А если элементы соединить в связанный список и перебирать так
запоминаем указатель на начало списка. изначальный список АБВГД. потом отрываем Д приклеиваем к А,получаем ДАБВГ. и так дальше до тех пор пока не вернемся а АБВГД (для этого мы запомнили указатель на начало списка). Тут меняем 1ый символ списка на 2ой символ и опять повторяем вышеизложенную операцию. Потом 1ый на 3ий… и т.д.
Так получится? Или как ещё можно если не так?

Day

1177 / 987 / 83

Регистрация: 29.10.2009

Сообщений: 1,385

15.02.2010, 19:45

Сообщение было отмечено как решение

Решение

Ничего умнее, чем сделать вот такую рекурсию, не придумал
Но, вроде бы, работает.

#include <stdio.h>
static char X[7];
Pere(char *p, int k)
{ char q[7]; int i, j, jj;
   if (k==1) {
      X[6-k] = *p;
      X[6] = '';
      printf("%sn", X);
      return;
   }
   for(i=0; i<k; i++) {
      X[6-k] = p[i];
      for(j=0, jj=0; j<k; j++)
        if (j!=i) q[jj++] = p[j];
      Pere(q, k-1);
   }
}
/*************/
main()
{
 char s[7] = "123456";
 Pere(s, 6);
}
/*****************/

Day

1177 / 987 / 83

Регистрация: 29.10.2009

Сообщений: 1,385

17.02.2010, 11:45

Сообщение было отмечено как решение

Решение

Вот такой симпатичный алгоритм генерации перестановок без всяких рекурсий.
Э.Рейнгольд, Ю.Нивельгерт, Н.Део «Комбинаторные алгоритмы» 1980

#include <stdio.h>
#define N 6
main()
{ char s[N+1], t; int i, j, r, k;
 for(i=0; i<N; i++) s[i] = '1'+i;
 s[N] = '';
 while(1) {
   printf("%sn", s);  // Вывод очередной перестановки
       // Находим самое правое место, где s[i] < s[i+1]
   for(i=N-1; i>=0 && s[i] > s[i+1]; i--) ;
   if (i<0) break; // Уже получили "654321" - самую старшую перестановку
       // Находим s[j] - наименьший элемент справа от s[i] и больший его
   for(j=N-1; s[i] > s[j]; j--) ;
       // Меняем s[i] <-> s[j]
   t = s[j];
   s[j] = s[i];
   s[i] = t;
       // То, что за "i" - переворачиваем
   for(k=i+1, r=N-1; r > k; k++, r--) {
     t = s[r];
     s[r] = s[k];
     s[k] = t;
   }
 }
}
/*****************/

3646 / 1378 / 243

Регистрация: 16.04.2009

Сообщений: 4,526

15.11.2010, 18:58

Day, а можете предложить вариант, чтобы символы распологались не друг за другом в таблице, т.е. наприме «fas» и т.д. (а не «abcd» или «1234»)

1177 / 987 / 83

Регистрация: 29.10.2009

Сообщений: 1,385

15.11.2010, 19:38

go, вот это место измени по вкусу

Код C
1234

Чушь какая-то.
Сбой.
Не до того

Диссидент

27488 / 17175 / 3784

Регистрация: 24.12.2010

Сообщений: 38,690

05.11.2018, 11:17

Есть еще такая задача. Пусть все перестановки расположены в лексикографическом порядке. По номеру k найти k-тую перестановку. (Не выписывая все, конечно). Где-то на форуме она решалась. (сейчас не найду) Так вот, на основе решения этой задачи легко решается и данная.
Без претензий на оптимальность.

Источник