Уникальные перестановки

Форум для обсуждения вопросов математики

Модератор: Admin

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Уникальные перестановки

Сообщение omega » Вт июн 05, 2012 4:32 am

Вот эти 12 перестановок из чисел 1,2,3,4 назовём уникальными в таком смысле: ни в каких двух перестановках в одинаковых позициях нет одинаковой пары чисел:

Код: Выделить всё

1 2 3 4
1 3 4 2
1 4 2 3
2 1 4 3
2 3 1 4
2 4 3 1
3 1 2 4
3 2 4 1
3 4 1 2
4 1 3 2
4 2 1 3
4 3 2 1

Например, в первой перестановке в первой и второй позиции имеем пару чисел 1,2; больше ни в какой престановке в этих позициях нет такой пары чисел.

Задача такая: составить 56 уникальных перестановок из чисел 1,2,3,4,5,6,7,8 (ещё 72 перестановки из чисел 1,2,3,...,9 и 240 перестановок из чисел 1,2,3,...,16).

Вот начала писать перестановки из чисел 1,2,...,8. Первые семь штук:

Код: Выделить всё

1,2,3,4,5,6,7,8
1,3,4,5,6,7,8,2
1,4,5,6,7,8,2,3
1,5,6,7,8,2,3,4
1,6,7,8,2,3,4,5
1,7,8,2,3,4,5,6
1,8,2,3,4,5,6,7

Дальше не знаю, как писать.

По-хорошему, конечно, надо программку написать. Но для 16 чисел, наверное, очень долго работать будет :(
Слишком много перестановок. Может быть, тут какая-то хорошая есть закономерность, или хорошая оптимизирующая тупой перебор идея.

Помогите, пожалуйста.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Уникальные перестановки

Сообщение Kitonum » Ср июн 06, 2012 3:20 pm

omega писал(а):Вот эти 12 перестановок из чисел 1,2,3,4 назовём уникальными в таком смысле: ни в каких двух перестановках в одинаковых позициях нет одинаковой пары чисел:

Код: Выделить всё

1 2 3 4
1 3 4 2
1 4 2 3
2 1 4 3
2 3 1 4
2 4 3 1
3 1 2 4
3 2 4 1
3 4 1 2
4 1 3 2
4 2 1 3
4 3 2 1

Например, в первой перестановке в первой и второй позиции имеем пару чисел 1,2; больше ни в какой престановке в этих позициях нет такой пары чисел.

Задача такая: составить 56 уникальных перестановок из чисел 1,2,3,4,5,6,7,8 (ещё 72 перестановки из чисел 1,2,3,...,9 и 240 перестановок из чисел 1,2,3,...,16).


По-хорошему, конечно, надо программку написать. Но для 16 чисел, наверное, очень долго работать будет :(
Слишком много перестановок. Может быть, тут какая-то хорошая есть закономерность, или хорошая оптимизирующая тупой перебор идея...


Идея очень простая: на первое место ставите любое из n чисел, а все другие числа переставляете, используя циклические перестановки из какой-то одной. Поэтому число таких уникальных перестановок равно n*(n-1). Можете проверить эту формулу для своих частных случаев.
На основе этой идеи легко написать и программу, которая выдаёт все такие перестановки.

IVVA
Сообщения: 1036
Зарегистрирован: Вт апр 05, 2005 6:44 pm

Сообщение IVVA » Сб июн 09, 2012 6:36 pm

По такому алгоритму получаются совпадения.Для первой группы из n-1 подстановок все хорошо.Но когда n таких групп состыковать получаются совпадения.