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

[zhekas]

для 9 также тупит на 18 строке

[square]

Вот ведь!
Ладно, пожалуйста, пришлите мне программу для n=10. Попробую покрутить, авось получится.
А сама тем временем буду думать над аналогией.

Приглашаю всех подумать вместе со мной

[square]

Хорошая головоломка! Я уже всю голову сломала 



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

Это для аналогии n=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

Неужели аналогия не пройдёт? 

Да, напомню: должны получиться непересекающиеся комбинации.

[zhekas]

Есть задумка попробовать реализовать переход от n до n+1 следующим образом. Взять вторую группу из n=8. В ней прослеживаются две главные диагонали. Это диагональ едениц и диагональ восьмерок.

Взять например диагональ едениц и относительно её раздвинуть треугольники прилегающие к этой диагонали на одну позицию вправо для верхнего треугольника и на одну позицию вниз для нижнего треугольника. При этом числа в треугольниках увеличить на еденицу. А затем искать числа н позициях около этой диагонали

[square]

Хорошая задумка! Попробуйте.

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

Ну не может быть, чтобы для n=10 не было!

[square]

Zhekas
ну что там с десятками? Тоже глухо?

А что дадут комбинации из чисел 1,2,3,...,12?
Может, тут повезёт... Или тоже сразу программа будет тупить?

Задачка оказалась крепким орешком

Кстати, вы когда крутили программу для шестёрок, отслеживали появление 32 комбинаций?
Мне бы и 32 комбинации очень сгодились!

Тот вариант, который вы мне прислали, как я понимаю, это отслеживает. То есть он выдаст и 31 комбинацию, если будет найдено 31 штук, и 32 комбинации тоже выдаст. Правильно понимаю?

Я крутила несколько часов с параметром 6. Не выдалось даже ни одного набора из 31 комбинации, так и остался максимум=30.

[zhekas]

с 12 тоже глухо. Полный перебор и, соответственно, експоненциальный рост времени неумолимо приводят к ожидаемому результату (отсутствию резултата.)

[square]

Да-а-а... Вот ситуация...

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

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

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

Можно вообще начать с одной комбинации, любой.

[Smith]

Да-а-а... Вот ситуация...

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

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

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

Можно вообще начать с одной комбинации, любой.

111111   212345   313624   414263   515432   616253
122222   223456   324135   425314   526543   621364
133333   234561   335246   436425   531654   632415
144444   245612   346351   441536   542165   643526
155555   256123   351462   452641   553216   654631
166666   261234   362513   463152   564321   665142

зы: а что такое рэндом? 

[Smith]

square, а почему вы решили, что для n=8 всего 56 возможных перестановок на указанных условиях?
 
зы: т.е., может оно и так, но интересно - почему Вы так считаете?

[square]

С 36 комбинациями из чисел 1,2,3,4,5,6 у вас здорово получилось!

А мы с zhekas бились, бились, так ничего и не нашли.

А они у вас точно непересекающиеся? Я ещё не проверила.

Как вы их нашли? Расскажите, пожалуйста, интересно

Насчёт уникальных перестановок для n=8 всё просто: существует ровно 7 попарно ортогональных ЛК 8-го порядка. Перестановки эти из этих самых квадратов берутся, вот и будет их ровно 56.

А вот непересекающихся комбинаций для n=8 получается ровно 64, zhekas их нашёл.

Ах, да, про рэндом не ответила. Ну, это я на форуме dxdy.ru подцепила, там один товарищ так написал.
Вообще-то это функция такая - случайная величина

А с десяточками вы тоже можете выдать непересекающиеся комбинации? Мне надо мно-о-о-г-о Не меньше 90.

[Smith]

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

что касается проверки: там первые две значащие цифры вообще не нуждаются в проверке как между собой, так и в сочетании с иными, и это очевидно. в остальном проверка легко осуществляется по принципу создания, например. проверяем 3 и 4 значащие цифры. у нас в первом столбце 11, 2-12, 3-13, 4-14,5-15,6-16. аналогично везде и все вплоть до 66.

[square]

А что именно вы не понимаете? Есть задача:

а) для уникальных перестановок;
б) для непересекающихся комбинаций.

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

А вот с непересекающимися комбинациями никак не разберусь.
Из "десяточек" (т.е. из чисел 1,2,3,...10) нашла всего 19 непересекающихся комбинаций. И дальше ни тпру, ни ну

Так значит, говорите, что "шестёрки" у вас не пересекаются? Сейчас проверим...

[Smith]

другое дело - как доказать, что 36 - максимально возможное решение? вариант с квадратами предлагает способ решения для некоторых "квадратно" устроенных n. доказательства максимальности я пока не встречал. имхо, понимая природу "максимальности" можно вывести универсальную формулу для определения максимального количества вариантов перестановок.
другой интересный аспект (полагаю тесносвязаный с первым) - это возможное количество вариантов перестановок 36 из 6.

[square]

Я ушла проверять ваше решение

Да, вы ничего не сказали о "десяточках".