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

[Nataly-Mak]

Задачка вроде простая, но я что-то застряла

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

Смотрю на перестановки из чисел 1,2,3,4. Имеются ровно 4 группы перестановок, первая группа начинается с числа 1, вторая - с числа 2 и т.д., в каждой группе 3 перестановки.
Думаю, что для перестановок из чисел 1,2,3,..., 8 будет полная аналогия: 8 групп перестановок, в каждой группе 7 штук, первая группа - перестановки, начинающиеся с числа 1 (эту группу я уже написала), вторая группа - перестановки, начинающиеся с числа 2, и т.д.

Интересый вопрос: таких перестановок из чисел 1,2,3,...8 будет ровно 56?

Написала программку для второй группы перестановок, но со скрипом, что-то никак не могу справиться с проверкой всех пар чисел во всех перестановках, в циклах запуталась. Поэтому программу написала только для одной группы, это проще.

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

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

Вроде всё правильно в этой группе, пересечений нет ни внутри группы, ни с перестановками первой группы.

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

Надо ещё, как уже сказала, найти полный комплект уникальных перестановок для n=9 и для n=16.

[Nataly-Mak]

Опа!
А я думала, что задачка простенькая
Что-то решений пока не вижу.
Нет готовых методов решения? Значит, предстоит их изобрести.

[Sonic86]

Я просто не понял, что такое уникальная перестановка (или множество уникальных перестановок)
Мне сначала показалось, что $(\forall j)\pi (j)\neq j$, т.е. это беспорядки, но нет... Или $(\forall \pi,\sigma)\pi\neq\sigma\Rightarrow\pi (j)\neq\sigma(j)$, но тоже нет...
Можете определение формально выписать?

[Nataly-Mak]

Картинку покажу из статьи
http://bit-player.org/2009/the-17x17-challenge

На картинке вы видите уникальные перестановки для n=4:



Тут понятно? В строках 4 - f уникальные перестановки.
Я просто записала их в числах, мне так удобнее, чем с символами.

Вроде я дала вполне адекватное определение.

[Sonic86]

Тоже непонятно Я должен индуцировать закономерность в 16 элементах (не хватит у меня на это нейронов) и потом его индуцировать на все $n$ - это явно не определение

[Nataly-Mak]

Я дала ссылку на статью. Мне дополнительно никто ничего не объяснял.

Может быть, вы на основании информации из статьи дадите научное определение этих самых перестановок?
Назовите их по-своему, пусть не уникальные, пусть, например, непересекающиеся

Мне без разницы, как они будут называться, мне надо их найти.

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

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

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

Я просто не понял, что такое уникальная перестановка (или множество уникальных перестановок)

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

[Nataly-Mak]

Ну вот, научное определение уже имеем
К сожалению, не могу подтвердить его правильность, т.к. ничего в этих научных "крючках" не понимаю

Хорошо, пусть будет "уникальное множество перестановок". Но это уникальное множество перестановок как раз и состоит из уникальных перестановок в смысле данного мной определения. Или нет?

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

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

К сожалению, не могу подтвердить его правильность, т.к. ничего в этих научных "крючках" не понимаю

Ну а какого чёрта тогда берётесь писать на научном форуме?

-- Ср июн 06, 2012 11:40:08 --

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

Или нет?

Или нет.

[Nataly-Mak]

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

Ну а какого чёрта тогда берётесь писать на научном форуме?

Ах, ну прогоните меня отсюда

Я предложила конкретную задачу и прошу помочь её решить.
Демагогию, пожалуйста, не разводите.

К тому же, я дала ссылку на сатью, из которой взята эта информация.
Дала своё определение уникальных перестановок, показала их на иллюстрации из статьи.

Вам что-то непонятно?

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

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

Демагогию, пожалуйста, не разводите.

Демагогию разводите Вы. Всё это кокетство насчёт "научных крючков" выходит за рамки правил форума. Если Вы хотите, чтобы Вам помогли с решением задачи, будте добры её сформулировать. Если испытываете затруднения с формулировкой - Вам помогут. При условии, что Вы готовы учится. Пока этого не наблюдается.

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

Хорошо, пусть будет "уникальное множество перестановок". Но это уникальное множество перестановок как раз и состоит из уникальных перестановок в смысле данного мной определения. Или нет?

Раз уж всё так трудно, дам более развёрнутый ответ. Уникальность - свойство целого множества перестановок, а не одной перестановки самой по себе. Например, $\{ (1,2,3,4), (2,3,4,1) \}$ - уникальное множество перестановок, а $\{ (1,2,3,4), (1,2,4,3) \}$ - не уникальное. При этом перестановка $(1,2,3,4)$ входит в оба множества. Является ли она уникальной сама по себе? По-видимому, вопрос бессмысленен.

[Nataly-Mak]

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

Вот эти 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; больше ни в какой престановке в этих позициях нет такой пары чисел.

В этом определении говорится о 12 перестановках, которые я назвала уникальными. Именно о 12! Я не сказала нигде, что одна перестановка может быть уникальной!

Будьте внимательны, пожалуйста, при чтении определений.

Так что, у меня нет никаких трудностей с определением. У меня есть трудности с решением поставленной задачи.
А вот помощи в этом я пока не наблюдаю.

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

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

Я не сказала нигде, что одна перестановка может быть уникальной!

Да ну?

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

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

-- Ср июн 06, 2012 12:07:38 --

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

У меня есть трудности с решением поставленной задачи.
А вот помощи в этом я пока не наблюдаю.

Приведите Ваши попытки решения.

[dimkadimon]

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

Картинку покажу из статьи
http://bit-player.org/2009/the-17x17-challenge

На картинке вы видите уникальные перестановки для n=4:

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

[Nataly-Mak]

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

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

-- Ср июн 06, 2012 10:29:28 --

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

Цитата:

Приведите Ваши попытки решения.

Я привела здесь первые 14 уникальных перестановок или, если вам так больше нравится, уникальное множество перестановок, состоящее из 14 элементов.
Это не попытки решения что ли?

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