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

[zhekas]

для n=10 по методу Wesson не больше 50 строк

[square]

А вот посмотрите, какой набор из 32 непересекающихся комбинаций из чисел 1,2,3,...,10 выложили на форуме dxdy.ru

Код:

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

Кажется, совершенно хаотично числа берутся. Правда?
Никакой закономерности нету, я не вижу, во всяком случае.

Попробовала добавить к этому набору ещё комбинации, добавляла по одной (не полный перебор!), удалось добавить всего 3 штуки, больше не добавляется.
Конечно, если делать полный перебор, может быть, и больше удастся добавить.

[square]

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

Пример:

Код:

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

Но в этом примере комбинации длины 6 (6 чисел в строке), а нам надо тогда составлять комбинации длины 12 (12 чисел в строке). И таких комбинаций тоже надо 36 штук.

Возможно ли такую задачу решить?

[square]

Вот пытаюсь вручную такие длинные комбинации сочинить, чтобы разрешалось повторяться только числам 1 и 2. Комбинации надо составлять из чисел 1,2,3,4,5,6, в каждой комбинации 12 чисел. И таких комбинаций надо 36 штук.

1 1 1 1 1 1 2 2 2 2 2 2
1 2 2 2 2 2 2 1 1 1 1 1
2 2 1 3 3 1 1 1 2 3 3 3
. . . . . . . . . . . . .

Я могла тут ошибиться, трудно визуально всё проверить, надо по программе проверять.

Смотрите, пара (1,2) повторяется в первой и второй строках (1-ая и 7-ая позиции), а также в первой и третьей строках (6-ая и 9-ая позиции). Числам 1,2 разрешается повторяться в люьых строках и в любых позициях. Я так поняла.

Ну, выше пример есть из статьи.

[square]

Вижу ошибку, пара (1,1) повторяется, получается во всех четырёх позициях стоят 1.
Вот трудно визуально все ошибки сразу увидеть

Тогда так попробуем написать:

1 1 1 1 1 1 2 2 2 2 2 2
1 2 2 2 2 2 2 1 1 1 1 1
2 2 1 3 3 3 1 1 2 3 3 3
. . . . . . . .

Так получается?

[Smith]

да. у меня получается только 30. больше таким способом не получается пока, увы.

[square]

zhekas
как у вас дела с десятками? Сколько комбинаций нашли?

50 комбинаций покажите, пожалуйста, которые уже нашли.

Просьба такая: можете сделать набор непересекающихся комбинаций из чисел 1,2,3,4,5?
Это, наверное, быстро получится. Их должно быть 25 штук.

Уникальные перестановки для n=5 у меня есть, а вот непересекающихся комбинаций нет.

Заранее спасибо.

[zhekas]

с десятками на 50-и всё остановилось. Больше нет (по методу Wesson)
Показать скрытый текст

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 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 1
2 4 5 6 7 8 9 10 1 2
2 5 6 7 8 9 10 1 2 3
2 6 7 8 9 10 1 2 3 4
2 7 8 9 10 1 2 3 4 5
2 8 9 10 1 2 3 4 5 6
2 9 10 1 2 3 4 5 6 7
2 10 1 2 3 4 5 6 7 8
3 1 3 10 9 8 5 6 2 5
3 2 4 1 10 9 6 7 3 6
3 3 5 2 1 10 7 8 4 7
3 4 6 3 2 1 8 9 5 8
3 5 7 4 3 2 9 10 6 9
3 6 8 5 4 3 10 1 7 10
3 7 9 6 5 4 1 2 8 1
3 8 10 7 6 5 2 3 9 2
3 9 1 8 7 6 3 4 10 3
3 10 2 9 8 7 4 5 1 4
4 1 10 9 7 4 8 8 4 4
4 2 1 10 8 5 9 9 5 5
4 3 2 1 9 6 10 10 6 6
4 4 3 2 10 7 1 1 7 7
4 5 4 3 1 8 2 2 8 8
4 6 5 4 2 9 3 3 9 9
4 7 6 5 3 10 4 4 10 10
4 8 7 6 4 1 5 5 1 1
4 9 8 7 5 2 6 6 2 2
4 10 9 8 6 3 7 7 3 3
5 1 9 8 10 7 7 3 7 8
5 2 10 9 1 8 8 4 8 9
5 3 1 10 2 9 9 5 9 10
5 4 2 1 3 10 10 6 10 1
5 5 3 2 4 1 1 7 1 2
5 6 4 3 5 2 2 8 2 3
5 7 5 4 6 3 3 9 3 4
5 8 6 5 7 4 4 10 4 5
5 9 7 6 8 5 5 1 5 6
5 10 8 7 9 6 6 2 6 7

для n=5
Показать скрытый текст

 1 1 1 1 1
 1 2 2 2 2
 1 3 3 3 3
 1 4 4 4 4
 1 5 5 5 5
 2 1 2 3 4
 2 2 3 4 5
 2 3 4 5 1
 2 4 5 1 2
 2 5 1 2 3
 3 1 3 5 2
 3 2 4 1 3
 3 3 5 2 4
 3 4 1 3 5
 3 5 2 4 1
 4 1 4 2 5
 4 2 5 3 1
 4 3 1 4 2
 4 4 2 5 3
 4 5 3 1 4
 5 1 5 4 3
 5 2 1 5 4
 5 3 2 1 5
 5 4 3 2 1
 5 5 4 3 2

[square]

Спасибо большое.

Вот посмотрите, что мне удалось найти по своей простенькой программке (она только добавляет одну строку):

Код:

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

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

Однако лемму к этому прямоугольнику мне применить удалось (лемма делает из прямоугольника nxm прямоугольник nxkm).

Обсуждали мой пример на dxdy.ru
//текст доступен после регистрации//

Пришли к выводу, что и числа 2,3 могут повторяться, если 3 взять по модулю 2 и при этом не получится прямоугольник со весеми 4 одинаковыми вершинами.

То есть в приведённом примере

3  2
3  2

по модулю 2 будет

1  2
1  2
и всё нормально.

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

1  2
1  2
и больше пересечений нет.
Вот такая задача у меня

Хочу попросить вас, если есть время, продолжить этот набор по описанным правилам.

Надо 36 таких комбинаций. Комбинации с разрешением повторений ведь искать проще, чем непересекающиеся комбинации. Правда, комбинации теперь в два раза длиннее.

А я что-то никак не разберусь с циклами в программе полного перебора; вот сделала программу только для добавления одной строки к набору из n строк. Это простая программка, но она много строк не находит.

Если программа долго будет работать, то мне её пришлёте тогда, я сама буду крутить, у меня времени много свободного и машина свободна всегда

Wesson
и вас приглашаю порешать мою задачку,
а также и всех других форумчан.

В Экселе тоже вроде можно простенькие программки писать, но я не умею, никогда не пользовалась Экселем.

[square]

zhekas
начала строить квадрат на основе непересекающихся перестановок из чисел 1,2,3,...,10, он у меня не получился.
Стала смотртеть комбинации...

Что-то вы напутали. Смотрите вот на эту строку:

4 4 3 2 10 7 1 1 7 7

и на первую строку

1 1 1 1 1 1 1 1 1 1

Здесь есть пересечение

1 1
1 1
 
И ещё есть пересечения в других строках.

Или метод не сработал, или вы ошиблись.

[zhekas]

вечером взгляну

[zhekas]

С перебором всё так. Это с построением вышла маленькая заминка.
Попробуйте вот это
Показать скрытый текст

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 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 1
2 4 5 6 7 8 9 10 1 2
2 5 6 7 8 9 10 1 2 3
2 6 7 8 9 10 1 2 3 4
2 7 8 9 10 1 2 3 4 5
2 8 9 10 1 2 3 4 5 6
2 9 10 1 2 3 4 5 6 7
2 10 1 2 3 4 5 6 7 8
3 1 3 2 7 9 8 4 6 5
3 2 4 3 8 10 9 5 7 6
3 3 5 4 9 1 10 6 8 7
3 4 6 5 10 2 1 7 9 8
3 5 7 6 1 3 2 8 10 9
3 6 8 7 2 4 3 9 1 10
3 7 9 8 3 5 4 10 2 1
3 8 10 9 4 6 5 1 3 2
3 9 1 10 5 7 6 2 4 3
3 10 2 1 6 8 7 3 5 4
4 1 4 7 9 6 2 10 5 8
4 2 5 8 10 7 3 1 6 9
4 3 6 9 1 8 4 2 7 10
4 4 7 10 2 9 5 3 8 1
4 5 8 1 3 10 6 4 9 2
4 6 9 2 4 1 7 5 10 3
4 7 10 3 5 2 8 6 1 4
4 8 1 4 6 3 9 7 2 5
4 9 2 5 7 4 10 8 3 6
4 10 3 6 8 5 1 9 4 7
5 1 6 8 5 4 9 3 10 7
5 2 7 9 6 5 10 4 1 8
5 3 8 10 7 6 1 5 2 9
5 4 9 1 8 7 2 6 3 10
5 5 10 2 9 8 3 7 4 1
5 6 1 3 10 9 4 8 5 2
5 7 2 4 1 10 5 9 6 3
5 8 3 5 2 1 6 10 7 4
5 9 4 6 3 2 7 1 8 5
5 10 5 7 4 3 8 2 9 6

[square]

Да, из этого набора получилось.
Спасибо.

[Smith]

с десятками на 50-и всё остановилось. Больше нет (по методу Wesson)
Показать скрытый текст

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 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 1
2 4 5 6 7 8 9 10 1 2
2 5 6 7 8 9 10 1 2 3
2 6 7 8 9 10 1 2 3 4
2 7 8 9 10 1 2 3 4 5
2 8 9 10 1 2 3 4 5 6
2 9 10 1 2 3 4 5 6 7
2 10 1 2 3 4 5 6 7 8
3 1 3 10 9 8 5 6 2 5
3 2 4 1 10 9 6 7 3 6
3 3 5 2 1 10 7 8 4 7
3 4 6 3 2 1 8 9 5 8
3 5 7 4 3 2 9 10 6 9
3 6 8 5 4 3 10 1 7 10
3 7 9 6 5 4 1 2 8 1
3 8 10 7 6 5 2 3 9 2
3 9 1 8 7 6 3 4 10 3
3 10 2 9 8 7 4 5 1 4
4 1 10 9 7 4 8 8 4 4
4 2 1 10 8 5 9 9 5 5
4 3 2 1 9 6 10 10 6 6
4 4 3 2 10 7 1 1 7 7
4 5 4 3 1 8 2 2 8 8
4 6 5 4 2 9 3 3 9 9
4 7 6 5 3 10 4 4 10 10
4 8 7 6 4 1 5 5 1 1
4 9 8 7 5 2 6 6 2 2
4 10 9 8 6 3 7 7 3 3
5 1 9 8 10 7 7 3 7 8
5 2 10 9 1 8 8 4 8 9
5 3 1 10 2 9 9 5 9 10
5 4 2 1 3 10 10 6 10 1
5 5 3 2 4 1 1 7 1 2
5 6 4 3 5 2 2 8 2 3
5 7 5 4 6 3 3 9 3 4
5 8 6 5 7 4 4 10 4 5
5 9 7 6 8 5 5 1 5 6
5 10 8 7 9 6 6 2 6 7

для n=5
Показать скрытый текст

 1 1 1 1 1
 1 2 2 2 2
 1 3 3 3 3
 1 4 4 4 4
 1 5 5 5 5
 2 1 2 3 4
 2 2 3 4 5
 2 3 4 5 1
 2 4 5 1 2
 2 5 1 2 3
 3 1 3 5 2
 3 2 4 1 3
 3 3 5 2 4
 3 4 1 3 5
 3 5 2 4 1
 4 1 4 2 5
 4 2 5 3 1
 4 3 1 4 2
 4 4 2 5 3
 4 5 3 1 4
 5 1 5 4 3
 5 2 1 5 4
 5 3 2 1 5
 5 4 3 2 1
 5 5 4 3 2

я не понимаю, почему с н=5 можно 25, а с н=6 только 30 (по программе) и еще +1 (не проверял) по ТС...  и почему с 10 только 50??? оч. хотелось бы хотя бы намеки теории в базу.. 

[Smith]

и еще прямой вопрос: 36 из 6 - возможно? 

зы: ежли кто-нить знает это наверное...