Алгоритм нахождения перестановок чисел

← →
Глеб © (2004-06-23 11:37) [0]

Здравствуйте!

Дано число N.
Мне нудно найти все возможные пеерстановки чисел от 1 до N. Точно знаю, что их n! (n-факториал).
Подскажите, пожалуйста, хороший алгоритм нахождения всех возможных перестановок чисел.

← →
nikkie © (2004-06-23 11:53) [1]

http://bspu.ab.ru/~pvv/shen/

← →
Глеб © (2004-06-24 07:54) [2]

Зачем давать мне ссылку на книгу?
Мне нужен алгоритм.

← →
Ozone © (2004-06-24 08:19) [3]

Делай обыкновенный перебор, как вариант.

← →
wal © (2004-06-24 09:37) [4]

1. Для одного числа тривиально.
2. Для n чисел ставишь на первое место по очереди числа от [1] до [n].
3. Для оставшихся после п. 2 чисел выполняешь п. 2 для n-1 чисел.
Короче рекурсия.
Где-то видел и более красивый алгоритм, но уже не помню где, да и сам алгоритм затрудняюсь вспомнить. Вроде сложность у него была ниже, чем предложенный мной вариант. Попробуй поискать.

С уважением.

← →
Igorek © (2004-06-24 11:39) [5]

поищи в архиве - был такой вопрос

← →
nikkie © (2004-06-24 18:14) [6]

>[2] Глеб
Глебушка, люби книгу - источник знаний. конкретно эта книжка научит тебя большему, чем мастер-класс по программированию.

← →
wl (2004-06-24 19:31) [7]

Мне нудно найти... замечательно...

← →
Ильичев С.А. © (2004-06-24 20:30) [8]

http://algolist.manual.ru/

← →
Aldor © (2004-06-24 21:52) [9]

Совсем недавно в Основной поднималась эта тема. Можете поискать там.

← →
Victor T (2004-06-24 22:14) [10]

Ваял такую програмку. Тока она дома. Завтра, если не забуду, кину исходник (он маленький кажись).

← →
Victor T (2004-06-24 22:20) [11]

А вот > Ильичев С.А. © (24.06.04 20:30) [8] нормальную ссылку дал кстати, вот тута нашлось: http://algolist.manual.ru/maths/combinat/permutations.php
И в книге Шена тоже есть (тоже ссылку дали)

← →
Victor T (2004-06-24 22:25) [12]

Я кстати когда ваял програмку (для друга, он всякого рода кроссвордами и т.п. увлекается, это нужно было, чтоб из набора букв все слова составить), сам алгоритм придумывал. Но вот как дублей не делать (типа когда есть одинаковые буквы), не придумал тогда. Т.е. у слова к примеру "аа" получалось две перестановки, а нужно, чтоб была одна.

> Т.е. у слова к примеру "аа" получалось две перестановки,
> а нужно, чтоб была одна.

По рекурсионному алгоритму [4] - пытаешься вставить символ в i-ую позицию - если i - равен текущему, то дальше вставляешь текущий символ в i + 2 позицию, иначе в i + 1..

то есть у тя есть строка 12345 и текущий символ 2. вставляешь его
в 1 поз. - 212345
во 2 - 122345 так как в исходной строке второй символ тоже 2, то
в 4 поз. 123245 и так далее

> Мне нудно найти... замечательно...

Ну описался просто.
Не "нудно", а "нужно".
Догадаться трудно?

Удалено модератором

Алгоритм нахождения перестановок чисел Найти похожие ветки