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

[Nataly-Mak]

Leu в сообщении #583240 писал(а):

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

(Оффтоп)

Не следует учить профессионального программиста с 25-летним стажем, с чего надо начинать писать программу. Я "блок-схемами" писала 40 лет назад. А теперь уже все блок-схемы у меня просто в голове, я их не пишу. И здесь писать не собираюсь.

Почему-то на другом форуме тот, кто заинтересовался задачей и захотел помочь, не спрашивал с меня никаких блок-схем, а сам написал программу и прислал её мне!
К сожалению, оказалось, что перебор в этой задаче очень вязкий, чего я никак не ожидала. У него, к примеру, программа работала сутки, но так и не нашла решение. Может быть, его и не существует. Но это ещё надо доказать, как вы сами говорили.

Есть программы (например, по последней проблеме, решаемой в теме "Магические квадраты"), которые работают неделями! И это программы, написанные очень грамотными программистами (Алексей Чернов, Сергей Беляев). Я поднимала эту проблему (по ускорению работы этих программ) в теме "Распараллеливание для многоядерных процессоров", однако никто не предложил конструктивного решения. Так и работаю по этим программам, вот уже несколько недель, ежедневно с утра запускаю программу, а вечером прерываю. Программа у меня работает весь день, это не мешает мне параллельно выполнять все другие работы, у меня двухядерный процессор.

[кстати, один из форумчан брался вроде написать более эффективную программу, но... что-то я пока программы не вижу]

Я уже сказала вам, что больше не отвечаю на вопросы "зачем нужны магические квадраты", "зачем нужны латинские квадраты". Если вам не нужны, ходите мимо

-- Пн июн 11, 2012 05:12:33 --

О программе, которую мне прислал форумчанин с форума nazva.net

Удивительно! Программа находит десятки, сотни наборов из 30 комбинаций, причём за одну секунду, а вот набора из 31 комбинации у меня за несколько часов работы не выдала ни одного.
Вот пример, программа выдала набор из 30 комбинаций:

Pervaia stroka:
1 1 1 1 1 1 
Maximum=30
1 1 1 1 1 1 
1 2 2 2 2 2 
1 3 3 3 3 3 
1 4 4 4 4 4 
1 5 5 5 5 5 
1 6 6 6 6 6 
2 1 2 3 4 5 
2 2 1 4 3 6 
2 3 4 5 6 1 
2 4 3 6 5 2 
2 5 6 1 2 3 
2 6 5 2 1 4 
3 1 3 5 2 4 
3 2 4 6 1 3 
3 3 5 1 4 6 
3 4 6 2 3 5 
3 5 1 3 6 2 
3 6 2 4 5 1 
4 1 4 2 5 6 
4 2 3 1 6 5 
4 3 6 4 1 2 
4 4 5 3 2 1 
4 5 2 6 3 4 
4 6 1 5 4 3 
5 1 5 4 6 3 
5 2 6 3 5 4 
5 3 1 6 2 5 
5 4 2 5 1 6 
5 5 3 2 4 1 
5 6 4 1 3 2

Но набор из 31-комбинации мной получен (о чём рассказано выше). Я получила его по своей программке, добавив к набору из 30 комбинаций, выложенному на форуме nazva.net, 31-ую комбинацию.
Оказывается, мне с этим крупно повезло, потому что сотни других наборов из 30 комбинаций просто не допускают добавление 31-ой комбинации.

Кто не верит, пусть попробует добавить 31-ую комбинацию к приведённому здесь набору из 30 комбинаций.
Я скормила этот набор своей программке, она моментально отработала и сказала, что добавление 31-ой комбинации в данном случае невозможно.

И остаётся открытым вопрос, существует ли набор таких комбинаций из 32 штук.

Напомню, что речь идёт о непересекающихся комбинациях в смысле данного в самом начале темы определения.
Только определение было дано для перестановок. Теперь я работаю не с перестановками, а с произвольными комбинациями из чисел 1,2,3,4,5,6.

-- Пн июн 11, 2012 05:35:46 --

Leu в сообщении #583240 писал(а):

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

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

Читайте тему "Новый конкурс программистов".

[Nataly-Mak]

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

В связи с этим у меня есть гипотеза: существует аналогичный набор, стоящий из 90 комбинаций чисел 1,2,3,...,10.

Первая группа комбинаций пишется по аналогии с ходу:

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

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

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

Похоже?

Кто может заполнить пробелы?

-- Пн июн 11, 2012 08:19:25 --

Может быть, вторая комбинация такая:

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

[miflin]

(Оффтоп)

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

Не следует учить профессионального программиста с 25-летним стажем,

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

Вот у меня не хватает ума программу написать,

[Nataly-Mak]

Комплект из 20 уникальных перестановок чисел 1,2,3,...,10:

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

Составлен из двух известных ортогональных ЛК 10-го порядка.

В то время, когда я занималась ЛК, были известны только пары ортогональных ЛК 10-го порядка. Может быть, сейчас их найдено больше? Давно не слежу за темой.

[Nataly-Mak]

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

Может быть, вторая комбинация такая:

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

Написала программку для этой группы комбинаций, но добавляю только по одной комбинации (программу полного перебора писать не так просто).

Удалось добавить 7 комбинаций, в результате получилось:

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

Последняя комбинация (с пробелами) уже не добавляется.

Значит, все предыдущие комбинации составлены неверно.
Почти уверена, что аналогия с комбинациями из чисел 1,2,3,4,5,6 имеет место.

Напомню, что весь набор комбинаций такой:

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

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

[Nataly-Mak]

Полный набор из 64 непересекающихся комбинаций чисел 1,2,3,4,5,6,7,8:

(Оффтоп)

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

Решение найдено на форуме nazva.net
http://nazva.net/forum/index.php/topic,7758.30.html

А вот для чисел 1,2,3,...,10 никак не получается.
Вроде должен тоже быть набор непересекающихся комбинаций. Но как его найти

[Nataly-Mak]

Leu
вас интересовали чудеса
да, чудеса бывают...

На форуме nazva.net я тоже поставила задачу об уникальных перестановках и о непересекающихся комбинациях.

Чудо первое: нашёлся форумчанин, который эту задачу решал!

[здесь такого чуда не произошло ]

Чудо второе
форумчанин выкладывает первый попавшийся набор из 30 непересекающихся комбинаций из чисел 1,2,3,4,5,6:

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

Таких наборов, как я уже говорила, программа выдаёт сотни.

Я пишу программку добавления к данному набору из 30 комбинаций следующей - 31-ой - комбиниции. Выполняю программу и... получаю сразу же (мгновенно!) 31-ую комбинацию:

1 1 6 6 6 5

32-ая комбинация к этому набору уже не добавляется.

Тем временем форумчанин сутки крутит свою программу в поисках набора из 32 комбинаций. И не получает даже ни одного набора из 31 комбинации!

А теперь попробуйте найти хоть один набор из 31 непересекающихся комбинаций из чисел 1,2,3,4,5,6, отличный от того, который нашли мы с форумчанином.
(может быть, вы сумеете написать такую программу, которая решит эту задачу мгновенно )
Далее, докажите, что набора из 32 непересекающихся комбинаций не существует (не факт!).
Это посложнее, чем рассуждать о том, как надо писать программы.

Чудо третье
я привела выше набор из 20 уникальных перестановок чисел 1,2,3,...,10.
Эти перестановки выписаны из двух известных ортогональных латинских квадратов 10-го порядка.
За много-много лет все математики мира нашли всего 3-4 пары ортогональных ЛК 10-го порядка!
20 штук перестановок мне мало. Тогда я разрешаю повторение чисел и ставлю задачу о неперекающихся комбинациях чисел 1,2,3,...,10.
Казалось бы, произвольных комбинаций должно быть больше, чем уникальных перестановок. Но увы! Пока найден набор всего из 19 непересекающихся комбинаций (он показан выше). И на 20-ой комбинации программа надолго задумывается.

Вполне возможно, что программу форумчанин написал не очень эффективную, перебор захлёбывается.
Ну так асы программирования на этом форуме что-то помалкивают в тряпочку

В самом деле, зачем нужны эти непересекающиеся комбинации? 19 штук их или 90 - какая разница!

Или вот те же ортогональные ЛК, зачем их все математики ищут? Кому они нужны? Представляете, до порядка n=1000 уже добрались Это же с ума можно сойти: найти ортогональные ЛК 1000-го порядка.

[Nemiroff]

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

А теперь попробуйте найти хоть один набор из 31 непересекающихся комбинаций из чисел 1,2,3,4,5,6, отличный от того, который нашли мы с форумчанином.
(может быть, вы сумеете написать такую программу, которая решит эту задачу мгновенно )
Далее, докажите, что набора из 32 непересекающихся комбинаций не существует (не факт!).
Это посложнее, чем рассуждать о том, как надо писать программы.

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

Вполне возможно, что программу форумчанин написал не очень эффективную, перебор захлёбывается.
Ну так асы программирования на этом форуме что-то помалкивают в тряпочку

Вы когда-нибудь про Неуловимого Джо слышали?

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

Или вот те же ортогональные ЛК, зачем их все математики ищут? Кому они нужны? Представляете, до порядка n=1000 уже добрались

Вы сами-то знаете, зачем?

[cepesh]

Тема перемещена из форума «Дискретная математика, комбинаторика, теория чисел» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.