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

[square]

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

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

[moonlight]

24 перестановки из 8 чисел.
Если найду больше добавлю.
Показать скрытый текст

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

[square]

Спасибо, но мало 

Я сама начала программку писать, но что-то со скрипом она у меня идёт. Никак не могу совладать со всеми проверками всех пар чисел во всех перестановках.

Да, начать нужно с приведённой выше группы уникальных перестановок, начинающихся с числа 1, следующие перестановки уже с этими сравнивать.

Если вы посмотрите на пример с числами 1,2,3,4, то увидите, что есть ровно 4 группы перестановок, первая начинается с числа 1, вторая - с числа 2 и т.д., в каждой группе 3 перестановки, всего 12.
Думаю, что для чисел 1,2, ..., 8 будет полная аналогия. В каждой группе будет 7 перестановок, всего 8 групп.
Я начала искать вторую группу - перестановки, начинающиеся с числа 2.

Пока предположительно у меня такая перестановка получилась с числа 2:

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

Вроде ни с какой перестановкой первой группы не пересекается (в смысле определения).
Но это пока предположительно. Программу ещё не дописала. И пишу её только для второй группы.
Хоть бы эту группу составить. Там, может быть, какие-то закономерности проявятся.
Если у меня программа с числа 2 составит перестановки норамально, 7 штук, тогда можно будет проанализировть их.

[square]

Вот, например, такая вторая группа у меня получилась (с числа 2 начинаются перестановки):

Код:

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

Вроде нормально, но не уверена.

Кто видит тут какие-то закономерности? Чтобы можно было следующую группу написать, с числа 3 начинаются перестановки.

Вот интересно: если все 56 перестановок найти, они, наверное, чётко получатся.
Смотрю в приведённых выше перестановках много всяких. Но вот если до 56 перестановок дойти, наверное многие перестановки не впишутся, будут пересекаться. И останутся действительно уникальные. И будет их, вероятно, ровно 56. Но это пока предположения. Ничего определённого не знаю сама.
Можно на перестановках для чисел 1,2,3,4 проверить.

[zhekas]

n=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
2 1 8 5 4 7 6 3
2 8 5 4 7 6 3 1
2 5 4 7 6 3 1 8
2 4 7 6 3 1 8 5
2 7 6 3 1 8 5 4
2 6 3 1 8 5 4 7
2 3 1 8 5 4 7 6
3 1 2 4 6 8 7 5
3 2 4 6 8 7 5 1
3 4 6 8 7 5 1 2
3 6 8 7 5 1 2 4
3 8 7 5 1 2 4 6
3 7 5 1 2 4 6 8
3 5 1 2 4 6 8 7
4 1 3 5 7 2 8 6
4 3 5 7 2 8 6 1
4 5 7 2 8 6 1 3
4 7 2 8 6 1 3 5
4 2 8 6 1 3 5 7
4 8 6 1 3 5 7 2
4 6 1 3 5 7 2 8
5 1 4 8 3 6 2 7
5 4 8 3 6 2 7 1
5 8 3 6 2 7 1 4
5 3 6 2 7 1 4 8
5 6 2 7 1 4 8 3
5 2 7 1 4 8 3 6
5 7 1 4 8 3 6 2
6 1 7 3 2 5 8 4
6 7 3 2 5 8 4 1
6 3 2 5 8 4 1 7
6 2 5 8 4 1 7 3
6 5 8 4 1 7 3 2
6 8 4 1 7 3 2 5
6 4 1 7 3 2 5 8
7 1 5 2 6 4 3 8
7 5 2 6 4 3 8 1
7 2 6 4 3 8 1 5
7 6 4 3 8 1 5 2
7 4 3 8 1 5 2 6
7 3 8 1 5 2 6 4
7 8 1 5 2 6 4 3
8 1 6 5 3 7 4 2
8 6 5 3 7 4 2 1
8 5 3 7 4 2 1 6
8 3 7 4 2 1 6 5
8 7 4 2 1 6 5 3
8 4 2 1 6 5 3 7
8 2 1 6 5 3 7 4

n=9
Показать скрытый текст

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

[square]

Здорово!
Правда, на уникальность не проверила, только бегло просмотрела визуально.
А как искали? Программу писали?

Я как раз собиралась сообщить, что задачу помогли решить на форуме dxdy.ru
//текст доступен после регистрации//

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

[zhekas]

Здорово!
Правда, на уникальность не проверила, только бегло просмотрела визуально.
А как искали? Программу писали?

Я как раз собиралась сообщить, что задачу помогли решить на форуме dxdy.ru
//текст доступен после регистрации//

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

Я немного изменил поиск. Искал не 56 перестановок, а 8 наборов по 7 чисел в каждой  (в каждом наборе отсутствуют разные числа). При этом чтобы в каждой паре наборов не было одинаковой пары рядомстоящих чисел (одинаковоориентированых).

А дальше вся комбинация получается путём сдвига этих наборов и приписывания слева недостающее число

[square]

Отличное решение!
А вы смотрели по ссылке, как просто, оказывается, находятся эти уникальные перестановки?
Просто выписываются столбцы из полного комплекта попарно ортогональных латинских квадратов.

Кстати, вы не хотите в международном конкурсе программистов поучаствовать?
//текст доступен после регистрации//

Это ведь задачка у меня вспомогательная была для решения конкурсной задачи.

[square]

zhekas
а из чисел 1,2,3,4,5,6 есть комплект из 30 уникальных перестановок?
Весьма интересно!
Если у вас есть программа, прикиньте, пожалуйста.

Ну, две группы по 5 штук написать просто. Например, такие:

Код:

1 2 3 4 5 6
1 3 4 5 6 2
1 4 5 6 2 3
1 5 6 2 3 4
1 6 2 3 4 5
2 1 6 5 4 3
2 6 5 4 3 1
2 5 4 3 1 6
2 4 3 1 6 5
2 3 1 6 5 4

Думаю, что первую группу изменять не стоит, а вторую, конечно, можно изменить. Впрочем, программа сама разберётся.

[zhekas]

zhekas
а из чисел 1,2,3,4,5,6 есть комплект из 30 уникальных перестановок?
Весьма интересно!
Если у вас есть программа, прикиньте, пожалуйста.

Ну, две группы по 5 штук написать просто. Например, такие:

Код:

1 2 3 4 5 6
1 3 4 5 6 2
1 4 5 6 2 3
1 5 6 2 3 4
1 6 2 3 4 5
2 1 6 5 4 3
2 6 5 4 3 1
2 5 4 3 1 6
2 4 3 1 6 5
2 3 1 6 5 4

Думаю, что первую группу изменять не стоит, а вторую, конечно, можно изменить. Впрочем, программа сама разберётся.

2 3 4 5 6
1 4 6 5 3
1 5 2 6 4
1 6 3 2 5
1 2 4 3 6
1 3 5 4 2

Относительно первой группы, остальные группы единственны с точностью до сдвига

[square]

Если я правильно поняла, первая группа будет такая:

Код:

1 1 1 1 1 2
3 2 6 5 4 3
5 4 3 2 6 4
4 3 2 6 5 5
2 6 5 4 3 6

Если читать перестановки как у вас написано, то они получаются из 5 чисел.

Как писать следующую группу, не соображу.
Написала так:

Код:

2 2 2 2 2 3
4 3 1 6 5 4
6 5 4 3 1 5
5 4 3 1 6 6
3 1 6 5 4 1

Не получились уникальные, пара (4,3) совпадает.

Думаю дальше... Если так, как вы написали, то будет 6 групп по 6 штук... Да?
Наверное, так...То есть к вашей группе надо приписать ещё 5 групп.

Вторая группа такая будет?

Код:

3 4 5 6 2
4 6 5 3 1
5 2 6 4 1
6 3 2 5 1
2 4 3 6 1
3 5 4 2 1

Кажется, нет пересечений с первой группой.

И третья группа вроде получилась 

Неужели и из чисел 1,2,3,...,10 тоже существуют уникальные перестановки? Вот дела...
Не попробуте для этого случая?

[zhekas]

Если я правильно поняла, первая группа будет такая:

Код:

1 1 1 1 1 2
3 2 6 5 4 3
5 4 3 2 6 4
4 3 2 6 5 5
2 6 5 4 3 6

Если читать перестановки как у вас написано, то они получаются из 5 чисел.

Как писать следующую группу, не соображу.
Написала так:

Код:

2 2 2 2 2 3
4 3 1 6 5 4
6 5 4 3 1 5
5 4 3 1 6 6
3 1 6 5 4 1

Не получились уникальные, пара (4,3) совпадает.

Первая группа составляется из первого набора чисел:2 3 4 5 6 путём их сдвига и прибавления слева недостающего числа 1

1 2 3 4 5 6
1 3 4 5 6 2
1 4 5 6 2 3
1 5 6 2 3 4
1 6 2 3 4 5

Вторая группа из второго набора:1 4 6 5 3  путём сдвига и приставления слева недостающего числа 2

2 1 4 6 5 3
2 4 6 5 3 1
2 6 5 3 1 4
2 5 3 1 4 6
2 3 1 4 6 5

И так далее. В итоге получается
Показать скрытый текст

1 2 3 4 5 6
1 3 4 5 6 2
1 4 5 6 2 3
1 5 6 2 3 4
1 6 2 3 4 5
2 1 4 6 5 3
2 4 6 5 3 1
2 6 5 3 1 4
2 5 3 1 4 6
2 3 1 4 6 5
3 1 5 2 6 4
3 5 2 6 4 1
3 2 6 4 1 5
3 6 4 1 5 2
3 4 1 5 2 6
4 1 6 3 2 5
4 6 3 2 5 1
4 3 2 5 1 6
4 2 5 1 6 3
4 5 1 6 3 2
5 1 2 4 3 6
5 2 4 3 6 1
5 4 3 6 1 2
5 3 6 1 2 4
5 6 1 2 4 3
6 1 3 5 4 2
6 3 5 4 2 1
6 5 4 2 1 3
6 4 2 1 3 5
6 2 1 3 5 4

[square]

А-а-а...поняла.
Спасибо большое! Классная закономерность получается.

А с числами 1,2,3,...,10 попробуете?

Жутко интересно. В этом случает такая же будет схема составления?

[zhekas]

для n=10 программа справляется за 5часов. А записать я не записал. Так что скоро не ждите. Время растёт экспоненциально
Для n=9 программа отработала меньше секунды

[square]

Ну, я подожду У меня времени много.

Спасибо вам огромное.
Весьма интересные получаются перестановки!