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

[Smith]

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

для простоты считайте не строки, а столбцы. все столбцы устроены по принципу очередности. т.о., если любая пара чисел проверена по своим местам (я показывал на примере 11-16), то нет смысла проверять остальные пять.

[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
2 1 2 3 4 5
2 2 3 4 5 6
2 3 4 5 6 1
2 4 5 6 1 2
2 5 6 1 2 3
2 6 1 2 3 4
3 1 3 6 2 4
3 2 4 1 3 5
3 3 5 2 4 6
3 4 6 3 5 1
3 5 1 4 6 2
3 6 2 5 1 3
4 1 4 2 6 3
4 2 5 3 1 4
4 3 6 4 2 5
4 4 1 5 3 6
4 5 2 6 4 1
4 6 3 1 5 2
5 1 5 4 3 2
5 2 6 5 4 3
5 3 1 6 5 4
5 4 2 1 6 5
5 5 3 2 1 6
5 6 4 3 2 1
6 1 6 2 5 3
6 2 1 3 6 4
6 3 2 4 1 5
6 4 3 5 2 6
6 5 4 6 3 1
6 6 5 1 4 2

Не ошиблась?
А теперь смотрите: в строках 7-ой и 23-ей (считаем сверху) повторяется пара чисел (2,4) - третья и пятая позиции в строках.

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

[Smith]

7:  2 и 4
23: 2 и 6

[Smith]

7:  2 и 4
23: 2 и 6

нет, вы правы - неверно я посчитал строку, действительно повтор. я проверю, спасибо.

[square]

Не поняла...

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

7-ая комбинация:

212345

23-ья комбинация:

452641

Сравните числа в третьей и пятой позиции, и там, и там стоят числа 2,4.

[Smith]

Не поняла...

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

7-ая комбинация:

212345

23-ья комбинация:

452641

Сравните числа в третьей и пятой позиции, и там, и там стоят числа 2,4.

посмотрите уже до конца тогда, если не трудно

[square]

Визуально это трудно.
У меня есть программка, которая добавляет к исходному набору из n комбинаций (n+1)-ую комбинацию. Но это долго тоже проверять по одной комбинации.
Общей программы у меня нет.
А у вас разве нет программы? Вы вручную что ли составили эти комбинации?

Далее, ещё есть один метод для проверки (которым я сразу и воспользовалась), но этот метод долго рассказывать.
Для этого вам надо вникнуть в конкурсную задачу текущего международного конкурса программитстов (здесь тему открыла "Monochromatic squares"). В этом конкурсе приложена программа, которая проверяет правильность построенного на базе 36 комбинаций квадрата 36х36. Квадрат я строю по программе, сразу загоняю в неё набор из 36 комбинаций и квадрат готов. Потом загоняю его в программу проверки правильности и вижу, что там куча ошибок. Это значит, что исходный набор из 36 комбинаций неправильный.

Вот для построения квадрата 36х36 мне и нужен базовый набор из 36 непересекающихся комбинаций. Мне удалось построить с помощью zhekas только набор из 31 комбинации.

[Smith]

 нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают. но это говорит лишь о том, что я где-тоне верно сдвинул прокрутку.
подумаю на досуге, а пока работаю.

зы: нет, программы у меня нет, а что такое программа? 

[square]

нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают.

И опять не поняла. Какие все шесть позиций совпадают? Ну, к примеру, вижу ещё одну совпадающую пару (4,6), но это в других комбинациях, хотя, да, в тех же позициях.

Программа - это... код на каком-то языке программирования для исполнения этого кода машиной, то бишь компьютером

[Smith]

нет, Вы не поняли. очевидно, что в этих (3-й и 5-й) позициях в указанных столбцах все шесть позиций совпадают.

И опять не поняла. Какие все шесть позиций совпадают? Ну, к примеру, вижу ещё одну совпадающую пару (4,6), но это в других комбинациях, хотя, да, в тех же позициях.

Программа - это... код на каком-то языке программирования для исполнения этого кода машиной, то бишь компьютером

смотрите столбцы 2 и 4-й, позиции 3 и 5: они ВСЕ в указанных столбцах не совпадают, поскольку использовалась кольцевая прокрутка сверху-в-низ чисел от 1 до 6 (в каждом столбике каждого столбца). я покручу чуть позже

[Smith]

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

ps^ а программкой мне служит EXCEL 

[square]

Wesson
ну как, покрутили? Не получилось?

А я вот сочинила 54 комбинации из 1,2,3,4,5,6 с пропусками чисел:

Код:

1 2 5 6 4 4
3 3 x x 6 4
x 6 6 x 1 x
6 1 2 4 x x
x 6 2 x 2 6
3 x 3 1 x 5
5 4 3 3 x 4
1 x x x 5 6
1 x 4 x 2 1
2 x 3 x x 3
x 5 4 x x x
x x 5 2 6 x
x 5 1 1 2 4
5 x 5 4 3 6
3 4 x x 4 1
5 3 6 x 5 3
x 6 x 3 4 5
1 1 1 3 1 x
4 2 4 1 3 x
2 2 x 2 x x
4 1 x x 5 5
x 4 1 2 x 3
6 x 6 1 x 6
x 3 2 3 x x
x 2 x 4 6 2
2 x 1 x 4 2
6 2 5 x x x
x 3 3 5 3 2
1 5 2 x x 2
2 1 6 6 2 x
4 4 x 5 1 x
4 x 2 2 x 1
6 5 5 x 1 5
x 6 1 x x 3
3 5 x 2 5 x
4 3 5 x 2 x
5 1 x x x 1
x 5 x x x 6
x x 4 4 5 4
x 5 6 3 6 1
1 6 x 2 3 x
3 x 5 5 x 3
5 x 2 1 1 x
6 x 1 x 6 x
x 2 3 x 1 1
x x x 4 1 3
1 4 6 4 x 5
4 x 6 x x 2
5 x 4 6 6 5
x 1 3 2 4 6
x x 1 x 3 5
x 4 x 6 x x
x x x 6 3 x
x x x 5 x 4

Можно ли этот набор из 54 неполных комбинаций свести полным перебором к набору из 36 (или хотя бы из 32, 33, 34, 35) непересекающихся комбинаций?

В комбинациях те числа, которые уже стоят на месте, пересечений не дают (искала комбинации по программе).

zhekas
не попробуете эту идею реализовать?

У меня от 36-градусной жары уже совсем мозги расплавились 

[Smith]

Wesson
ну как, покрутили? Не получилось?

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

если окажется, что нужный вариант существует и он будет найден (один из сотни для 5 чисел) тогда останется две позиции, потом одна. и нет необходимости сверять совпадения - их не будет по определению. тогда можно писАть программку для 10, 20 и 1000 чисел. а пока... пока 

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

[zhekas]

По методу Wesson все 6 групп по 6 столбцов (то есть 36 строк) не выходят. Максимум это 5 групп по 6 столбцов. (30 строк).

Для n=10 уже 5 групп тобишь 50 строк и перебор ещё идет

[square]

По методу Wesson все 6 групп по 6 столбцов (то есть 36 строк) не выходят. Максимум это 5 групп по 6 столбцов. (30 строк).

Да, я тоже это подозревала. Не получится.
А 30 комбинаций по вашей программе запросто получается. Мне даже удалось 31-ую найти.

Для n=10 уже 5 групп тобишь 50 строк и перебор ещё идет

O-о-о!!!
Это уже отлично. Ещё немного, ещё чуть-чуть

Вы нашли больше половины. Мне надо от 83 и выше. Если будет 9 групп, то бишь 90 комбинаций, будет классно.

В этих 50 комбинациях никакой закономерности не видно?