fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 12:46 
Заслуженный участник


08/04/08
8562
dimkadimon, а Вы можете формальное определение подмножества уникальных перестановок выписать?
Ой!... :oops:
Профессор Снэйп в сообщении #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$ действуют на некоторых двух элементах одинаково, то они равны... Сейчас проверю... Похоже на правду!...

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 13:02 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 14:19 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ааа понял... посмотрите на колонки в ЛК.

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 14:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Пришло письмо от знакомого программиста. Все 56 уникальных перестановок для n=8 найдены!

(Оффтоп)


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

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

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

Мне осталось выполнить чисто техническую процедуру. Если программист не ошибся, решения для 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).

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 16:04 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Последний раз советую. Вы смотрите на ряды ЛК, а вам надо посмотреть на колонки ЛК.

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 18:02 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
dimkadimon в сообщении #581530 писал(а):
Последний раз советую. Вы смотрите на ряды ЛК, а вам надо посмотреть на колонки ЛК.

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

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 18:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 квадратов.

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 18:37 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Nataly-Mak в сообщении #581400 писал(а):
Профессор Снэйп
Ну ведь "из уникальных перестановок", а не из одной перестановки. Вы отличаете единственное число от множественного?

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 19:14 
Заблокирован
Аватара пользователя


22/03/08

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

(Оффтоп)


 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение06.06.2012, 20:23 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение07.06.2012, 02:49 


30/05/12
332
вообщем, задача сводится к магическим квадратам

сравните 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, и далее меняете цифры, как в примере выше

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение07.06.2012, 03:56 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение07.06.2012, 06:12 
Заблокирован
Аватара пользователя


22/03/08

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

(Оффтоп)


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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение07.06.2012, 21:26 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение08.06.2012, 22:40 
Заблокирован
Аватара пользователя


22/03/08

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

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

(Оффтоп)


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 69 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group