Сгенерировать n! вариантов перемешиваний

Здравствуйте.
Математика, комбинаторика: Если из множества, состоящего из n элементов выбираем подмножество, состоящее из m элементов, то число таких подмножеств:


m n!
A =_______ ,
n (n-m)!

(Ошибка в формуле: пробел не считается за символ (по размеру). выравнивание нарушено)
если играет роль порядок следования элементов...
В случае, когда n=m => A=n!
Вопрос, а как получить эти n! вариаций. Интерисует алгоритм. Неужели такая задача не решена?

[Andrewpg]

и что тебе мешает создать цикл от 1 до н! ? Переменная цикла и будет твоей комбинацией. А дальше - делай с ней что хочешь - хоть переводи в i-тую систему исчисления, хоть из массива значение подставляй.

Пример генерации (проявил фантазию)
n=3 n!=3*2*1=6
1) ABC
2) ACB
3) BAC
4) BCA
5) CAB
6) CBA
________
Следующее любое другое перемешивание А В С будет совпадать с одним из перечисленых. Хотелось бы узнать алгоритм как можно получить вот эти АВС СВА и т. д.. Желательно итерационный.

[Trotil]

Во-первых, формула не верна. Число способов выбрать из множества мощности n подмножество мощности n равно одному, т.е. подмножество - это само множество, и других подможеств мощности n нет.
ТО. что исчисляется формулой n!, называется перестановками, это немного другое.
Уточни задание, что именно нужно получить?

Добавлено: все понял, такие вещи действительно называются перестановками.

Первое, это цитата из конспекта, которую мне диктовал кандидат по теории тевоятностей (проще говоря - препод). Я его понимаю как число перестановок. n!. Мне нужен n! перестановок символов в группе., состоящей из этих n символов.

[Trotil]

Алгоритм может быть таким:

1. Идешь с конца массива, ищешь элемент, который меньше предыдущего
(если смотреть справа)
2. В оставшейся части справа ищешь такой элемент, который больше найденного, но, при этом меньше всех остальных.
3. Этот элемент меняешь местами с найденным элементом.
4. Сортируешь по неубыванию оставшуюся правую часть.

Исходники можно посмотреть тут (но не вчитывался в алгоритм, не знаю, какой там подход реализован):
http://algolist.manual.ru/maths/comb...rmutations.php

Ok!

[Trotil]

Придумал алгоритм короче в реализации (как мне представляется) - рекурсивный:

Пусть существует способ способ получить (n-1)! перестановок для (n-1) элементов.
Способ получить перестановки для n элементов, где новый элемент обозначим как "K", следующий:
1) выводим все последовательности типа (K A1 A2 A3 ... An-1). для каждой из (A1 A2 A3 ... An) - (n-1)! перестановок
2) выводим все последовательности типа (A1 K A2 A3 ... An-1)...
...
n) выводим все последовательности типа (A1 A2 A3 ... An-1 K).

Таким образом мы выведем (n-1)!*n=n! последовательностей, все последовательности различны и состоят из n различных элементов. Таким образом доказано, что таким способом выводятся все последовательности.

P.S. Можно использовать сдвиг, т.е. из (K A1 A2 A3 ... An-1) последовательности получить последовтельности вида (A1 A2 A3 ... An-1 K ), (A2 A3 ... An-1 K A1). (A3 ... An-1 K A1 A2), ... , (An-1 K A1 A2 ... An-2), но так, ИМХО, сложнее.

Добавление: Первый алгоритм сохраняет лексиграфический порядок, второй (рекурсивный) - не сохраняет.