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

← →
Dmitry S © (2008-06-17 19:25) [0]

Чтото не могу сообразить.
К примеру есть алфавит состоящий из N символов: {0, 1, 2, ...}
Нужно составить все возможные слова длиной M (M<=N), так, чтобы в слове ни один символ не повторялся.
И как посчитать количество таких слов длиной M?

Например, алфавит {0, 1} (N = 2)
При M = 1: два слова: 0, 1
При M = 2: два слова: 01, 10

Например, алфавит {0, 1, 2} (N = 3)
При M = 1: три слова: 0, 1, 2
При M = 2: шесть слов: 01, 02, 10, 12, 20, 21
При M = 3: тоже шесть слов 012, 021, 102, 120, 201, 210.

← →
Dmitry S © (2008-06-17 19:35) [1]

Блин, форум волшебный. Стоит только запостить, как сразу ответ в голову приходит.
Кому интересно: N!/(N-M)!

← →
Zeqfreed © (2008-06-17 20:35) [2]

Есть еще более волшебная штука :)
http://en.wikipedia.org/wiki/Permutation#Counting_permutations

← →
DrPass © (2008-06-17 20:36) [3]

http://www.nsu.ru/mmf/tvims/chernova/tv/lec/node3.html

Да, только эта короткая красивая формула из комбинаторики плоха по двум причинам. Во-первых, из нее не сразу виден способ решения задачи, а во-вторых, она содержит лишние вычисления. Поэтому куда лучше тупо
N*(N-1)*(N-2)*...*(N-M+1) .

Перестановки Найти похожие ветки