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

[Sonic86]

dimkadimon, а Вы можете формальное определение подмножества уникальных перестановок выписать?
Ой!...

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

Я так понял, что лучше ввести термин "уникальное множество перестановок". Что-то типа следующего: множество $X \subseteq S_n$ называется уникальным, если для любых $\sigma, \pi \in X$ и любых $1 \leqslant i < j \leqslant n$ из $\pi(i) = \sigma(i)$ и $\pi(j) = \sigma(j)$ следует $\pi = \sigma$.

А разве это не просто определение одинаковых перестановок? (наверное "и любых" надо заменить "и для некоторых")
...
А понял! Если перестановки $\pi$ и $\sigma$ из $M$ действуют на некоторых двух элементах одинаково, то они равны... Сейчас проверю... Похоже на правду!...

[Nataly-Mak]

Sonic86 в сообщении #581459 писал(а):

А понял! Если перестановки $\pi$ и $\sigma$ из $M$ действуют на некоторых двух элементах одинаково, то они равны... Сейчас проверю... Похоже на правду!...

Ну, наверное, не из M, а из X

Я бы сказала так: если две перестановки имеют хотя бы в одной паре позиций i, j соответственно одинаковые элементы, то эти престановки считаются равными.

[dimkadimon]

Ааа понял... посмотрите на колонки в ЛК.

[Nataly-Mak]

Пришло письмо от знакомого программиста. Все 56 уникальных перестановок для 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  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  1  2  4  5  6  7  8
3  2  4  5  6  7  8  1
3  4  5  6  7  8  1  2
3  5  6  7  8  1  2  4
3  6  7  8  1  2  4  5
3  7  8  1  2  4  5  6
3  8  1  2  4  5  6  7
4  1  8  7  6  5  3  2
4  2  1  8  7  6  5  3
4  3  2  1  8  7  6  5
4  5  3  2  1  8  7  6
4  6  5  3  2  1  8  7
4  7  6  5  3  2  1  8
4  8  7  6  5  3  2  1
5  1  2  3  4  6  7  8
5  2  3  4  6  7  8  1
5  3  4  6  7  8  1  2
5  4  6  7  8  1  2  3
5  6  7  8  1  2  3  4
5  7  8  1  2  3  4  6
5  8  1  2  3  4  6  7
6  1  8  7  5  4  3  2
6  2  1  8  7  5  4  3
6  3  2  1  8  7  5  4
6  4  3  2  1  8  7  5
6  5  4  3  2  1  8  7
6  7  5  4  3  2  1  8
6  8  7  5  4  3  2  1
7  1  2  3  4  5  6  8
7  2  3  4  5  6  8  1
7  3  4  5  6  8  1  2
7  4  5  6  8  1  2  3
7  5  6  8  1  2  3  4
7  6  8  1  2  3  4  5
7  8  1  2  3  4  5  6
8  1  7  6  5  4  3  2
8  2  1  7  6  5  4  3
8  3  2  1  7  6  5  4
8  4  3  2  1  7  6  5
8  5  4  3  2  1  7  6
8  6  5  4  3  2  1  7
8  7  6  5  4  3  2  1

Я оказалась права, они существуют. Иначе и быть не могло.

Более того, найдены 72 уникальных перестановки для n=9 и 240 уникальных перестановок для n=16.

Вот! И программист понял моё не научное определение!

Мне осталось выполнить чисто техническую процедуру. Если программист не ошибся, решения для 8, 9 и 16 цветов должны получиться.

Визуально глянула на перестановки для n=8, вроде всё верно.
Кстати, у него точно такие же первые 14 перестановок, как и у меня.

-- Ср июн 06, 2012 16:08:47 --

Увы! Программист ошибся!

Перестановки не уникальные.
Выполнила программу составления квадрата 64х64, проверила его в программе Эда, он получился неправильный.
Начала внимательно смотреть на перестановки и увидела повторяющуюся пару чисел (6,7).

Так что задача остаётся открытой.

Вот начало перестановок для 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  9  8  7  6  5  4  3
2  3  1  9  8  7  6  5  4
2  4  3  1  9  8  7  6  5
2  5  4  3  1  9  8  7  6
2  6  5  4  3  1  9  8  7
2  7  6  5  4  3  1  9  8
2  8  7  6  5  4  3  1  9
2  9  8  7  6  5  4  3  1
3  1  2  4  5  6  7  8  9
. . . . . . . . . . .

И сразу вижу повторение пары (5,6).

[dimkadimon]

Последний раз советую. Вы смотрите на ряды ЛК, а вам надо посмотреть на колонки ЛК.

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

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

Последний раз советую. Вы смотрите на ряды ЛК, а вам надо посмотреть на колонки ЛК.

Да нет, есть и в рядах. В 1 и 17 (последнем из процитированных).

В смысле каждая строка - запись перестановки. Цитируется список перестановок, составляющий типа уникальное множество. Но это не так

Nataly-Mak, Вы избрали форум dxdy для того, чтобы публично поругать программиста, написавшего для Вас некорректную программу? Но чего Вы хотите от нас?

[Nataly-Mak]

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

Последний раз советую. Вы смотрите на ряды ЛК, а вам надо посмотреть на колонки ЛК.

О!!!
И вам не жалко давать такой совет?

Вот так просто, как всё гениальное...
Выписала из первых трёх ортогональных квадратов, да, перестановки вроде уникальные:

Цитата:

7 6 5 4 3 2 1 0
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
2 3 0 1 6 7 4 5
1 0 3 2 5 4 7 6
0 1 2 3 4 5 6 7
3 1 7 5 6 4 2 0
2 0 6 4 7 5 3 1
1 3 5 7 4 6 0 2
0 2 4 6 5 7 1 3
7 5 3 1 2 0 6 4
6 4 2 0 3 1 7 5
5 7 1 3 0 2 4 6
4 6 0 2 1 3 5 7
4 7 2 1 5 6 3 0
5 6 3 0 4 7 2 1
6 5 0 3 7 4 1 2
7 4 1 2 6 5 0 3
0 3 6 5 1 2 7 4
1 2 7 4 0 3 6 5
2 1 4 7 3 0 5 6
3 0 5 6 2 1 4 7

Сейчас припишу остальные 5 квадратов.

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

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

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

Профессор Снэйп
Ну ведь "из уникальных перестановок", а не из одной перестановки. Вы отличаете единственное число от множественного?

Вот если $X$ состоит из уникальных перестановок, а $\sigma \in X$, то является ли $\sigma$ уникальной перестановкой?

Либо да, либо "низачод" по русскому языку

[Nataly-Mak]

Готово! Выписала из всех 7 квадратов.

(Оффтоп)

7 6 5 4 3 2 1 0
6 7 4 5 2 3 0 1
5 4 7 6 1 0 3 2
4 5 6 7 0 1 2 3
3 2 1 0 7 6 5 4
2 3 0 1 6 7 4 5
1 0 3 2 5 4 7 6
0 1 2 3 4 5 6 7
3 1 7 5 6 4 2 0
2 0 6 4 7 5 3 1
1 3 5 7 4 6 0 2
0 2 4 6 5 7 1 3
7 5 3 1 2 0 6 4
6 4 2 0 3 1 7 5
5 7 1 3 0 2 4 6
4 6 0 2 1 3 5 7
4 7 2 1 5 6 3 0
5 6 3 0 4 7 2 1
6 5 0 3 7 4 1 2
7 4 1 2 6 5 0 3
0 3 6 5 1 2 7 4
1 2 7 4 0 3 6 5
2 1 4 7 3 0 5 6
3 0 5 6 2 1 4 7
6 2 3 7 1 5 4 0
7 3 2 6 0 4 5 1
4 0 1 5 3 7 6 2
5 1 0 4 2 6 7 3
2 6 7 3 5 1 0 4
3 7 6 2 4 0 1 5
0 4 5 1 7 3 2 6
1 5 4 0 6 2 3 7
1 4 6 3 2 7 5 0
0 5 7 2 3 6 4 1
3 6 4 1 0 5 7 2
2 7 5 0 1 4 6 3
5 0 2 7 6 3 1 4
4 1 3 6 7 2 0 5
7 2 0 5 4 1 3 6
6 3 1 4 5 0 2 7
5 3 4 2 7 1 6 0
4 2 5 3 6 0 7 1
7 1 6 0 5 3 4 2
6 0 7 1 4 2 5 3
1 7 0 6 3 5 2 4
0 6 1 7 2 4 3 5
3 5 2 4 1 7 0 6
2 4 3 5 0 6 1 7
2 5 1 6 4 3 7 0
3 4 0 7 5 2 6 1
0 7 3 4 6 1 5 2
1 6 2 5 7 0 4 3
6 1 5 2 0 7 3 4
7 0 4 3 1 6 2 5
4 3 7 0 2 5 1 6
5 2 6 1 3 4 0 7

[Nataly-Mak]

Сомнений не осталось!
8-цветный квадрат 64х64 построен.

dimkadimon
ещё раз благодарю!

[Leu]

вообщем, задача сводится к магическим квадратам

сравните 3 первые строки исходного примера, и 3 следующие:

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

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

видим - столбцы 2, 3 и 4 в каждом из этих блоков образуют магические квадраты (в которых цифры 1 и 2, поменяны местами, и сроки переставлены).

Значит, в аналогичной задаче для 8 цифр будет 7х8=56 комбинаций.
Для этого выписываете магический квадрат 7х7, и далее меняете цифры, как в примере выше

[Nataly-Mak]

Точнее: задача сводится к ортогональным латинским квадратам.

Берём полный комплект из 7 попарно ортогональных латинских квадратов 8-го порядка, например в этой статье.

Далее выписываем из каждого квадрата колонки (столбцы), и всё! Больше ничего не надо. Полный комплект уникальных перестановок готов.
Можно просто повернуть каждый ЛК на 90 градусов (либо по часовой стрелке, либо против); тогда столбцы станут строками, и выписывать надо уже строки. Так, собственно, я и делала, выписывать строки удобнее, нежели столбцы.

Сейчас точно так же буду составлять полный комплект из 72 уникальных перестановок. Теперь надо взять полный комплект попарно ортогональных латинских квадратов 9-го порядка.

[Nataly-Mak]

Вот полный комплект из 72 уникальных перестановок из чисел 1,2,...,9:

(Оффтоп)

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

Полный комплект из 8 попарно ортогональных латинских квадратов 9-го порядка, из которых получены уникальные перестановки, приведён в той же статье.

Осталось составить полный комплект из 240 уникальных перестановок из чисел 1,2,...,16.
Все 15 попарно ортогональных ЛК 16-го порядка тоже есть в моей статье.
Теперь дело техники.

[Nataly-Mak]

Полный комплект из 240 уникальных перестановок чисел 1,2,3,...,16 составила.
Не буду его здесь выкладывать, очень громоздкий.

Если кого интересует, напишите в личку, пришлю комплект.

[Nataly-Mak]

На форуме nazva.net (полная ссылка приведена выше) решили задачу и программно.
Здорово! Никак не связано с ЛК.

Вот решение для n=8 и n=9:

(Оффтоп)

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

Оригинальное решение!