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

[Профессор Снэйп]

dimkadimon в сообщении #581399 писал(а):

Вообще то на этой картинке нет перестановок.

Я тоже никаких перестановок там не увидел.

[Nataly-Mak]

dimkadimon в сообщении #581399 писал(а):

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

Эта задача возникла у меня из указанного алгоритма построения 4-цветного квадрата 16х16. Как раз того квадрата, который требуется в конкурсной задаче. Я его построила по данному алгоритму (он показан в теме "Новый конкурс программистов").

Никакой новой задачи я не создавала

-- Ср июн 06, 2012 10:39:25 --

Профессор Снэйп в сообщении #581401 писал(а):

dimkadimon в сообщении #581399 писал(а):

Вообще то на этой картинке нет перестановок.

Я тоже никаких перестановок там не увидел.

Ах!

Ну, а здесь вы видите перестановки?

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

Я же сказала, что заменила символы на числа.
А что, перестановки из символов - это уже и не перестановки?
То есть

A B C D
A C B D

нельзя назвать перестановками? Странно!

Может, всё-таки хватит демагогии?!!
Лучше бы задачу решили...

[dimkadimon]

Nataly-Mak в сообщении #581400 писал(а):

Пардон!
Я написала, что перестановки в строках 4 - f. Разве в этих строках не перстановки?

Простите я не заметил 4-f.

Кажется я понял вашу задачу. Для С=4 я нашёл только 12. Зато для С=8 я нашёл 22:

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

Все равно это далеко до решения задачи по раскраске.

[Nataly-Mak]

Да я могу хоть 100 найти (по программе, которая у меня уже есть).
Но мне нужен полный комплект из 56 перестановок! (для n=8)

[dimkadimon]

Nataly-Mak в сообщении #581404 писал(а):

Да я могу хоть 100 найти (по программе, которая у меня уже есть).
Но мне нужен полный комплект из 56 перестановок! (для n=8)

Я имел ввиду что я нашёл комплект из 22 которые имеют те свойства которые вам нужны. Я почти уверен что не существует комплекта из 56ти.

Кстати для С=9 я нашёл 16:

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

[Nataly-Mak]

dimkadimon в сообщении #581406 писал(а):

Я почти уверен что не существует комплекта из 56ти.

А я на все 100 уверена в обратном!
И для n=16 тоже существует полный комплект из 240 уникальных перестановок.
И для n=9, скорее всего, тоже.

Для всех этих n существуют полные комплекты попарно ортогональных латинских квадратов, а это как-то дьявольски связано. Только я пока не могу понять эту связь.

[lek]

Nataly-Mak в сообщении #581400 писал(а):

Написала программу для перестановок, начинающихся с числа 2, и нашла эту группу перестановок. Дальше я запуталась в циклах и бросила писать программу.

Попробуйте реализовать следующую идею. Сопоставьте каждой упорядоченной паре натуральное число и работайте далее с перестановками натуральных чисел. Например $(1,2)\to1,\dots,(3,4)\to6$ и, соответственно, $(1,2,3,4)\to(1,2,3,4,5,6)$. Разумеется, что в этом случае необходимо накладывать определенные ограничения на последовательности натуральных чисел. Но думаю, что программно эту идею реализовать легче, чем работать непосредственно с "уникальными перестановками".

[Nataly-Mak]

lek в сообщении #581409 писал(а):

Попробуйте реализовать следующую идею. Сопоставьте каждой упорядоченной паре натуральное число и работайте далее с перестановками натуральных чисел. Например $(1,2)\to1,\dots,(3,4)\to6$ и, соответственно, $(1,2,3,4)\to(1,2,3,4,5,6)$.

Пока ничего не поняла.
И как я буду в этом случае проверять совпадения в позициях перестановок, если я по два числа "сверну" в одно?

[lek]

Nataly-Mak в сообщении #581410 писал(а):

И как я буду в этом случае проверять совпадения в позициях перестановок, если я по два числа "сверну" в одно?

Вы не сворачиваете, а переобозначаете. Если хотите, то можете написать так: $(1,2)\to 1^{*}$.

[Nataly-Mak]

Для n=9 первая группа (перестановки, начинающиеся с числа 1) пишется с ходу:

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

Дальше я пока не думала. Надо сначала для n=8 решить задачу.

-- Ср июн 06, 2012 11:20:42 --

lek в сообщении #581411 писал(а):

Nataly-Mak в сообщении #581410 писал(а):

И как я буду в этом случае проверять совпадения в позициях перестановок, если я по два числа "сверну" в одно?

Вы не сворачиваете, а переобозначаете. Если хотите, то можете написать так: $(1,2)\to 1^{*}$.

Нет, не понимаю всё равно И что мне даст такое переобозначение?
Вместо пары (1,2) у меня будет (1), и что я в программе должна писать вместо пары (1,2)? Писать (1) и подразумевать, что это у меня (1,2)?

-- Ср июн 06, 2012 11:24:24 --

Вот на этом форуме сделали хотя бы попытку решить задачу:
http://nazva.net/forum/index.php?topic=7758.new

Нашли 24 перестановки:

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

Но это опять же не полный комплект из 56 перестановок.

[dimkadimon]

Nataly-Mak в сообщении #581407 писал(а):

dimkadimon в сообщении #581406 писал(а):

Я почти уверен что не существует комплекта из 56ти.

А я на все 100 уверена в обратном!
И для n=16 тоже существует полный комплект из 240 уникальных перестановок.
И для n=9, скорее всего, тоже.

Для всех этих n существуют полные комплекты попарно ортогональных латинских квадратов, а это как-то дьявольски связано. Только я пока не могу понять эту связь.

В ортогональных латинских квадратах строчки (то есть перестановки) только попарно уникальны, но не уникальны все между собой (что вы требуете). Постараюсь объяснить на примере. Вот 2 ортогональных латинских квадрата (из вашей статьи):

123
231
312

123
312
231

Второй ряд нам даёт 2 уникальные перестановки: 231 и 312. Третий ряд нам тоже даёт 2 уникальные перестановки: 312 и 231. Но обратите внимание что это те же самые перестановки только в другом порядке.

[lek]

Nataly-Mak в сообщении #581414 писал(а):

Нет, не понимаю всё равно И что мне даст такое переобозначение?
Вместо пары (1,2) у меня будет (1), и что я в программе должна писать вместо пары (1,2)? Писать (1) и подразумевать, что это у меня (1,2)?

Дело не в переобозначении, а в иной записи "уникальных перестановок". Например ваша перестановка $(1,2,3,4)$ может быть записана в виде $[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]$ или, что эквивалентно, $(1^{*},2^{*},3^{*},4^{*},5^{*},6^{*})$.

[Nataly-Mak]

dimkadimon в сообщении #581416 писал(а):

Nataly-Mak в сообщении #581407 писал(а):

dimkadimon в сообщении #581406 писал(а):

Я почти уверен что не существует комплекта из 56ти.

А я на все 100 уверена в обратном!
И для n=16 тоже существует полный комплект из 240 уникальных перестановок.
И для n=9, скорее всего, тоже.

Для всех этих n существуют полные комплекты попарно ортогональных латинских квадратов, а это как-то дьявольски связано. Только я пока не могу понять эту связь.

В ортогональных латинских квадратах строчки (то есть перестановки) только попарно уникальны, но не уникальны все между собой (что вы требуете).

Вы вроде тему о конкурсе читаете... Так к чему вы мне объясняете то, что я и сама знаю?
Совсем недавно я показала в теме два ортогональных ЛК 8-го порядка и сказала, что престановки в них совсем не уникальны. Вы это не видели?

Говорю о другом, что существует какая-то связь между полными комплектами попарно ортогональных ЛК и данной задачей об уникальных перестановках.
Это гарантирует, что полный комплект из 56 уникальных перестановок для n=8 существует.

Идея у меня такая.
Вот первый ЛК из полного комплекта попарно ортогональных квадратов 8-го порядка:

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

В этом квадрате имеем набор уникальных перестановок.

Каждая из строк этого ЛК будет первой в группе из 7 перестановок.

Так, первая строка порождает первую группу из 7 перестановок (эту группу я уже приводила), все перстановки этой группы начинаются с числа 1.

Вторая строка этого ЛК порождает вторую группу перестановок, начинающихся с числа 2, их тоже будет 7 штук.

Итак, 8 строк дадут нам 8 групп перестановок по 7 штук, итого 56 перестановок.

Пишем вторую строку из ЛК:

2  1  4  3  6  5  8  7

теперь продолжаем эту группу перестановок:

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

Но вот как записать эти перестановки, я не знаю.

Верна ли изложенная идея, тоже пока не знаю.
Но связь с ортогональными ЛК однозначно существует.

-- Ср июн 06, 2012 12:10:23 --

Pavlovsky в сообщении #581207 писал(а):

Nataly-Mak
Возми полный набор латинских квадратов 8х8, получишь 8*7=56 перестановок.

Вот эта цитата о чём-нибудь говорит?
По-моему, она полностью подтверждает мою мысль о связи ортогональных ЛК и задачи об уникальных перестановках.
Если, конечно, Pavlovsky не ошибается.

[dimkadimon]

Nataly-Mak в сообщении #581423 писал(а):

Итак, 8 строк дадут нам 8 групп перестановок по 7 штук, итого 56 перестановок.

В каждой из этих 8ми групп все 7 перестановок разные. НО (!) среди этих 56 перестановок будут те которые повторяются. Поэтому количество уникальных перестановок не 56, а гораздо меньше.

[Nataly-Mak]

dimkadimon в сообщении #581426 писал(а):

В каждой из этих 8ми групп все 7 перестановок разные. НО (!) среди этих 56 перестановок будут те которые повторяются. Поэтому количество уникальных перестановок не 56, а гораздо меньше.

Да почему будут повторяться? Кто вам это сказал? Доказать можете, что обязательно будут повторяться?
А нельзя ли записать все пререстановки так, что все 56 будут уникальными?

Ведь я привела пример из двух групп перестановок (14 штук), которые уникальны. Почему же нельзя составить 8 групп таких перестановок?

Ещё раз приведу эти 14 уникальных перестановок (2 группы):

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 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

Правда, у меня вторая группа перестановок начинается не с той строки, которая показана выше - из ЛК.