2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 14:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А вот существует ли комплект из 30 уникальных перестановок чисел 1,2,3,4,5,6?
Как известно, ортогональных классических латинских квадратов 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 6 5 4 3
2 3 1 6 5 4
2 4 3 1 6 5
2 5 4 3 1 6
2 6 5 4 3 1

Дальше можно добавить?

Нужно не просто добавить несколько престановок, образующих с имеющимися множество уникальных перестановок. Это множество должно состоять точно из 30 перестановок.

Разумеется, первые 10 перестановок могут быть и не такими, как в приведённом примере.

Очень любопытно, имеет ли эта задача решение.

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 17:31 


30/05/12
332
Nataly-Mak в сообщении #582424 писал(а):
На форуме nazva.net (полная ссылка приведена выше) решили задачу и программно.
Здорово!

такие задачи, похоже, проще решать именно так: написал программу - а она пусть себе перебирает! :D

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


22/03/08

7154
Саратов
Угу...
Только программу надо с умом писать. А ежели без ума, то она будет перебирать до второго пришествия Христа :D

Вот у меня не хватает ума программу написать, начала и бросила, запуталась в циклах.

На форуме nazva.net тот же товарищ нашёл одно решение.
Увы, ошибся, перестановки не уникальные, одна пара повторяется (может, и не одна, но я дальше не проверяла, увидела первую повторяющуюся пару и дальше не смотрела уже).
Вот это решение:

Код:
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

Повторяется пара (2,4).

Существуют ли полный комплект из 30 уникальных перестановок чисел 1,2,3,4,5,6? Вот в чём вопрос!

Если вы умеете программы писать, решите, пожалуйста, задачу для уникальных перестановок чисел 1,2,3,4,5,6. Здесь перебор небольшой, программа не должна работать долго. Надо только её грамотно написать.

(Оффтоп)

Только без вознаграждения, за "спасибо" :D

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 22:24 


20/04/12
147
Что-то я не вижу чтобы (2,4) повторялась.
Какой ряд и номер сверьху?

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 22:48 


30/05/12
332
Nacuott в сообщении #582762 писал(а):
Что-то я не вижу чтобы (2,4) повторялась.
Какой ряд и номер сверьху?

4-я и 11-я строки сверху

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


22/03/08

7154
Саратов
Первый и тринадцатый ряд, позиции вторая и четвёртая (слева).

Сейчас на форуме nazva.net
http://nazva.net/forum/index.php?topic= ... #msg204095

сообщили, что полный перебор не дал решения.

Тогда я переформулировала задачу:
искать будем не перестановки, а произвольные комбинации из 6 чисел, но условие запрещения повторения пары чисел в одинаковых позициях в любой паре комбинаций остаётся.

Таких комбинаций надо сочинить 36 штук.

-- Сб июн 09, 2012 23:51:39 --

Leu в сообщении #582771 писал(а):
Nacuott в сообщении #582762 писал(а):
Что-то я не вижу чтобы (2,4) повторялась.
Какой ряд и номер сверьху?

4-я и 11-я строки сверху

Да, верно, и там тоже повторяется эта пара чисел.
В общем, повторение не одно, их несколько.

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 22:57 


30/05/12
332
Nataly-Mak в сообщении #582726 писал(а):
Угу...
Только программу надо с умом писать. А ежели без ума, то она будет перебирать до второго пришествия Христа :D

Вот у меня не хватает ума программу написать, начала и бросила, запуталась в циклах.

Существуют ли полный комплект из 30 уникальных перестановок чисел 1,2,3,4,5,6? Вот в чём вопрос!

Если вы умеете программы писать, решите, пожалуйста, задачу для уникальных перестановок чисел 1,2,3,4,5,6. Здесь перебор небольшой, программа не должна работать долго. Надо только её грамотно написать.

Думаю, существует, почему нет. В основу надо положить ЛК 5х5 (как выше с ДК 7х7)

Чтоб не запутаться в циклах при написании программы сначала можно написать алгоритм.
Хотите - напишите, мы подскажем, если что

Теоретически, программу написать-то можно, но смысл?
Я не пойму, какое прикладное значение имеют эти квадраты? :D

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


22/03/08

7154
Саратов
Leu в сообщении #582777 писал(а):
Nataly-Mak в сообщении #582726 писал(а):
Существуют ли полный комплект из 30 уникальных перестановок чисел 1,2,3,4,5,6? Вот в чём вопрос!

Думаю, существует, почему нет. В основу надо положить ЛК 5х5 (как выше с ДК 7х7)

Так ведь я только что сообщила: на другом форуме сделали полный программный перебор и решения не нашли.
Так что, неправильно вы думаете :-)

В общем, результат вполне ожидаемый. Я так и предполагала, что полного комплекта из 30 уникальных перестановок чисел 1,2,3,4,5,6 не существует. Потому что не существует полного комплекта попарно ортогональных латинских квадратов 6-го порядка. Не существует даже одной пары ортогональных ЛК 6-го порядка.

Цитата:
Я не пойму, какое прикладное значение имеют эти квадраты? :D

Ну, на такие вопросы я уже давно не отвечаю :D Надоело!

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение09.06.2012, 23:14 


30/05/12
332
Nataly-Mak в сообщении #582782 писал(а):
Так ведь я только что сообщила: на другом форуме сделали полный программный перебор и решения не нашли.
Так что, неправильно вы думаете :-)


Ну, на такие вопросы я уже давно не отвечаю :D Надоело!

А может они ошиблись? Вот Вы уверены, в том, что тот кто решал тоже не запутался в циклах?
Я не уверен. Отсутствие решения должно быть доказано

Мне не отвечали :-) Прошу))

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


22/03/08

7154
Саратов
Leu в сообщении #582785 писал(а):

А может они ошиблись? Вот Вы уверены, в том, что тот кто решал тоже не запутался в циклах?
Я не уверен. Отсутствие решения должно быть доказано

Уверена! Если бы такой комплект из 30 уникальных перестановок существовал, из него можно было бы составить хотя бы два ортогональных ЛК 6-го порядка. А таких квадратов, как давно известно и доказано, не существует.
Я надеялась на чудо, но чудо не произошло :-)
Говорят, что чудес не бывает. Наверное, это правда.

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

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение10.06.2012, 00:04 


30/05/12
332
Nataly-Mak в сообщении #582799 писал(а):
Уверена! Если бы такой комплект из 30 уникальных перестановок существовал, из него можно было бы составить хотя бы два ортогональных ЛК 6-го порядка. А таких квадратов, как давно известно и доказано, не существует.
Я надеялась на чудо, но чудо не произошло :-)
Говорят, что чудес не бывает. Наверное, это правда.

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

чудеса бывают, только над ними нужно усиленно работать :D

Так какова польза таких квадратов, её нету?

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


22/03/08

7154
Саратов
Leu в сообщении #582809 писал(а):
чудеса бывают, только над ними нужно усиленно работать :D

(Оффтоп)

Спасибо, что сказали. А я и не знала :D
Это о чудесах не знала.
А насчёт "усиленно работать" - это я как-нибудь знаю. Тему мою "Магические квадраты" посмотрите :-)
Только на форуме я работаю над ней пятый год, до настоящего момента.
То, что до форума, не считаем.
Кстати, совсем забыла... И чудеса у меня случались, именно с квадратами. Но я это уже где-то рассказывала. Не буду повторять.

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

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #582799 писал(а):
Надо попытаться решить задачу в новой формулировке.

Ну, вот я пытаюсь решить задачу в новой формулировке.
Говорят: выкладывай попытки решения, ну вот выкладываю :-)

Начинала я не с нуля, на форуме nazva.net нашли 30 нужных мне комбинаций, вот они:

Код:
1 2 3 4 5 6
1 3 1 1 1 1
1 4 2 2 2 2
1 5 4 3 3 3
1 6 5 5 4 4
2 1 1 2 3 4
2 3 2 3 4 5
2 4 3 5 6 1
2 5 5 6 5 2
2 6 6 4 1 3
3 1 2 5 5 3
3 2 4 6 1 4
3 4 5 4 3 5
3 5 6 1 2 6
3 6 1 3 6 2
4 1 5 3 1 6
4 2 6 2 4 1
4 3 3 6 2 3
4 5 2 4 6 4
4 6 4 1 5 5
5 1 3 1 4 2
5 2 1 5 2 5
5 3 4 2 6 6
5 4 6 3 5 4
5 6 2 6 3 1
6 1 4 4 2 1
6 2 5 1 6 3
6 3 6 5 3 2
6 4 1 6 4 6
6 5 3 2 1 5

(ссылку на форум давала выше)

Я проверила, эти комбинации действительно непересекающиеся.
Теперь осталось к этим комбинациям добавить ещё 6 штук с таким же свойством (непересекаемость).

Пишу программу, сначала для добавления к этим 30 комбинациям только одной комбинации.
Текст программы (примитивно, я пишу на QBASIC, но это дела не меняет):

(Оффтоп)

#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
LOCAL I,J,K,N,M,T,J1,J2,J3,J4,J5,J6 AS LONG

N=30:M=6:K=31
DIM A(K,M) AS LONG,B(6) AS LONG
OPEN "A1.TXT" FOR INPUT AS #1
FOR I=1 TO N
FOR J=1 TO M
INPUT #1,A(I,J)
NEXT J
NEXT I
CLOSE #1
OPEN "A2.TXT" FOR OUTPUT AS #1
FOR T=1 TO 6:B(T)=T:NEXT T

FOR J1=1 TO 6
A(31,1)=B(J1)
FOR J2=1 TO 6
A(31,2)=B(J2)

FOR T=1 TO 30
IF A(31,1)=A(T,1) THEN IF A(31,2)=A(T,2) THEN 100
NEXT T

FOR J3=1 TO 6
A(31,3)=B(J3)

FOR T=1 TO 30
IF A(31,3)=A(T,3) THEN IF A(31,1)=A(T,1) THEN 98
NEXT T
FOR T=1 TO 30
IF A(31,3)=A(T,3) THEN IF A(31,2)=A(T,2) THEN 98
NEXT T

FOR J4=1 TO 6
A(31,4)=B(J4)

FOR T=1 TO 30
IF A(31,4)=A(T,4) THEN IF A(31,1)=A(T,1) THEN 96
NEXT T
FOR T=1 TO 30
IF A(31,4)=A(T,4) THEN IF A(31,2)=A(T,2) THEN 96
NEXT T
FOR T=1 TO 30
IF A(31,4)=A(T,4) THEN IF A(31,3)=A(T,3) THEN 96
NEXT T

FOR J5=1 TO 6
A(31,5)=B(J5)

FOR T=1 TO 30
IF A(31,5)=A(T,5) THEN IF A(31,1)=A(T,1) THEN 94
NEXT T
FOR T=1 TO 30
IF A(31,5)=A(T,5) THEN IF A(31,2)=A(T,2) THEN 94
NEXT T
FOR T=1 TO 30
IF A(31,5)=A(T,5) THEN IF A(31,3)=A(T,3) THEN 94
NEXT T
FOR T=1 TO 30
IF A(31,5)=A(T,5) THEN IF A(31,4)=A(T,4) THEN 94
NEXT T

FOR J6=1 TO 6
A(31,6)=B(J6)

FOR T=1 TO 30
IF A(31,6)=A(T,6) THEN IF A(31,1)=A(T,1) THEN 92
NEXT T
FOR T=1 TO 30
IF A(31,6)=A(T,6) THEN IF A(31,2)=A(T,2) THEN 92
NEXT T
FOR T=1 TO 30
IF A(31,6)=A(T,6) THEN IF A(31,3)=A(T,3) THEN 92
NEXT T
FOR T=1 TO 30
IF A(31,6)=A(T,6) THEN IF A(31,4)=A(T,4) THEN 92
NEXT T
FOR T=1 TO 30
IF A(31,6)=A(T,6) THEN IF A(31,5)=A(T,5) THEN 92
NEXT T

90 FOR T=1 TO 6:PRINT #1,A(31,T);:NEXT T
GOTO 500

92 NEXT J6
94 NEXT J5
96 NEXT J4
98 NEXT J3
100 NEXT J2
110 NEXT J1

500 END

END FUNCTION

Выполняю программу, она выдаёт такую 31-ую комбинацию:

Код:
1  1  6  6  6  5

Вроде всё правильно, комбинация удовлетворяет требуемому свойству.

Мне осталось найти ещё 5 комбинаций.

Черепашьими шагами буду двигаться. Авось дойду до конца :-)

Асы программирования только рассуждают о том, что теоретически программу можно написать, но зачем оно нужно :D

-- Вс июн 10, 2012 09:17:01 --

Немного изменила программку, и теперь она пригодна для поиска 32-ой комбинации.

И вот тут облом, 32-ая комбинация не формируется!
Программа выдаёт только первые два числа в этой комбинации, третье число добавить уже невозможно.

Значит, нужно изменять первые 30 комбинаций.
То есть по-хорошему надо писать одну программу на поиск всех 36 комбинаций. Но в такой программе я уже запутываюсь.

Как я понимаю, желающих помочь нет.
Я же выложила попытки решения :D

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


22/03/08

7154
Саратов
Начала писать программу для получения нового набора комбинаций, опять же не полный вариант (программы); удалось получить по этой программе новый набор комбинаций с требуемым свойством, но... набор этот состоит всего из 21 комбинации, дальше уже ничего невозможно добавить, если моя программа не врёт.

Вот этот набор:

Код:
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 3 1 6 5 4
2 4 3 1 6 5
2 5 4 3 1 6
2 6 5 4 3 1
3 1 2 4 6 4
3 2 5 1 4 2
3 6 1 5 2 6
4 2 1 3 6 1
4 3 5 2 1 5
5 1 4 6 3 5
5 3 6 1 2 1
6 4 2 5 1 1
4 5 2 1 5 3
6 1 3 2 2 2
3 3 3 3 3 3

А мне надо по крайней мере 32 комбинации, так как набор из 31 комбинации я уже нашла.

Пока не знаю даже, существует ли набор из 32 комбинаций. Думаю, что существует, но могу ошибаться.

 Профиль  
                  
 
 Re: Уникальные перестановки
Сообщение10.06.2012, 23:36 


30/05/12
332
Nataly-Mak в сообщении #582837 писал(а):
Спасибо, что сказали. А я и не знала :D
Это о чудесах не знала.
А насчёт "усиленно работать" - это я как-нибудь знаю.

усиленно работать, разумеется, для всего нужно

Цитата:
Тему мою "Магические квадраты" посмотрите :-)

она достаточно объемная. Если надо что-то посмотреть - пожалуйста, давайте номер конкретной страницы

Цитата:
Кстати, совсем забыла... И чудеса у меня случались, именно с квадратами. Но я это уже где-то рассказывала. Не буду повторять.

очень любопытно :D Дайте ссылку, пожалуйста)

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

у меня решение задач начинается с мотивационного аспекта, т. е. уяснения, зачем ту или иную задачу решать.
На счет квадратов это как раз и очень непонятно.
Просил Вас пояснить, но вы отмалчиваетесь. Значит, составлять такие квадраты - бесполезное занятие

Nataly-Mak в сообщении #582853 писал(а):
Асы программирования только рассуждают о том, что теоретически программу можно написать, но зачем оно нужно :D

Как я понимаю, желающих помочь нет.
Я же выложила попытки решения :D

Почему ж нету, иначе меня в этой теме давно б уже не было

Правильно делаю асы программирования, что так рассуждают. Потому что программы нужно писать с пользой, а не "напишу что-нибудь, авось программа задачу рассчитает" :lol:

Хорошо, что Вы выложили попытки решения. Но это преждевременно. Начинать надо с написания алгоритма. Не программы, а именно алгоритма (блок-схемами).
А на каком языке потом реализовывать этот алгоритм - дело второе.
Поэтому, сначала напишите алгоритм. Вот его и проверим

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

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



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

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


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

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