Как получить конкретную последовательность, как это? - PullRequest
Новая
       1

Как получить конкретную последовательность, как это?

11 голосов
/ 18 августа 2010

Есть 100 чисел:

1, 1, 2, 2, 3, 3, .. 50, 50.

Как получить последовательность, в которой один номер находится междудва 1, два числа между двумя 2, три числа между двумя 3 ... и пятьдесят чисел между двумя 50 с использованием сотен чисел?

У кого-нибудь есть идея лучше, чем грубая сила?Или докажите, что нет решения, когда n = 50.

Ответы [ 6 ]

15 голосов
/ 18 августа 2010

Проблема: соединение Лэнгфорда

Проблема известна как Langford Pairing . Из Википедии:

Эти последовательности названы в честь К. Дадли Лэнгфорда, который поставил проблему их построения в 1958 году. Как описывает Кнут 1 , проблема перечисления ALL Спаривание Лэнгфорда для данного N может быть решено как пример точной задачи о покрытии (одна из 21-полной задачи Карпа ), но для больших N число решений может быть вычислено более эффективно алгебраическими методами.

1 : Искусство компьютерного программирования, IV, глава 0: Введение в комбинаторные алгоритмы и булевы функции

Стоит отметить, что для N = 50 решения не существует. Решения существуют только для N = 4k или N = 4k - 1. Это доказано в статье Роя А. Дэвиса ( О проблеме Лэнгфорда II , Math. Gaz. 43, 253-255, 1959), в которой также приведена схема построения единого решения для любого возможного N.

Ссылки по теме

Грубая сила в Java

Вот некоторые решения, которые моя быстрая и грязная программа грубой силы смогла найти для N < 100. Почти все они были найдены менее чем за секунду. 

 3 [3, 1, 2, 1, 3, 2]
 4 [4, 1, 3, 1, 2, 4, 3, 2]
 7 [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1]
 8 [8, 3, 7, 2, 6, 3, 2, 4, 5, 8, 7, 6, 4, 1, 5, 1]
11 [11, 6, 10, 2, 9, 3, 2, 8, 6, 3, 7, 5, 11, 10, 9, 4, 8, 5, 7, 1, 4, 1]
12 [12, 10, 11, 6, 4, 5, 9, 7, 8, 4, 6, 5, 10, 12, 11, 7, 9, 8, 3, 1, 2, 1, 3, 2]
15 [15, 13, 14, 8, 5, 12, 7, 11, 4, 10, 5, 9, 8, 4, 7, 13, 15, 14, 12, 11, 10, 9, 6, 3, 1, 2, 1, 3, 2, 6]
16 [16, 14, 15, 9, 7, 13, 3, 12, 6, 11, 3, 10, 7, 9, 8, 6, 14, 16, 15, 13, 12, 11, 10, 8, 5, 2, 4, 1, 2, 1, 5, 4]
19 [19, 17, 18, 14, 8, 16, 9, 15, 6, 1, 13, 1, 12, 8, 11, 6, 9, 10, 14, 17, 19, 18, 16, 15, 13, 12, 11, 7, 10, 3, 5, 2, 4, 3, 2, 7, 5, 4]
20 [20, 18, 19, 15, 11, 17, 10, 16, 9, 5, 14, 1, 13, 1, 12, 5, 11, 10, 9, 15, 18, 20, 19, 17, 16, 14, 13, 12, 8, 4, 7, 3, 6, 2, 4, 3, 2, 8, 7, 6]
23 [23, 21, 22, 18, 16, 20, 12, 19, 11, 8, 17, 4, 1, 15, 1, 14, 4, 13, 8, 12, 11, 16, 18, 21, 23, 22, 20, 19, 17, 15, 14, 13, 10, 7, 9, 3, 5, 2, 6, 3, 2, 7, 5, 10, 9, 6]
24 [24, 22, 23, 19, 17, 21, 13, 20, 10, 8, 18, 4, 1, 16, 1, 15, 4, 14, 8, 10, 13, 12, 17, 19, 22, 24, 23, 21, 20, 18, 16, 15, 14, 11, 12, 7, 9, 3, 5, 2, 6, 3, 2, 7, 5, 11, 9, 6]
27 [27, 25, 26, 22, 20, 24, 17, 23, 12, 13, 21, 7, 4, 19, 1, 18, 1, 4, 16, 7, 15, 12, 14, 13, 17, 20, 22, 25, 27, 26, 24, 23, 21, 19, 18, 16, 15, 14, 11, 9, 10, 5, 2, 8, 3, 2, 6, 5, 3, 9, 11, 10, 8, 6]
28 [28, 26, 27, 23, 21, 25, 18, 24, 15, 13, 22, 10, 6, 20, 1, 19, 1, 3, 17, 6, 16, 3, 10, 13, 15, 18, 21, 23, 26, 28, 27, 25, 24, 22, 20, 19, 17, 16, 14, 12, 9, 7, 11, 4, 2, 5, 8, 2, 4, 7, 9, 5, 12, 14, 11, 8]
31 [31, 29, 30, 26, 24, 28, 21, 27, 18, 16, 25, 13, 11, 23, 6, 22, 5, 1, 20, 1, 19, 6, 5, 17, 11, 13, 16, 18, 21, 24, 26, 29, 31, 30, 28, 27, 25, 23, 22, 20, 19, 17, 15, 12, 14, 9, 10, 2, 3, 4, 2, 8, 3, 7, 4, 9, 12, 10, 15, 14, 8, 7]
32 [32, 30, 31, 27, 25, 29, 22, 28, 19, 17, 26, 13, 11, 24, 6, 23, 5, 1, 21, 1, 20, 6, 5, 18, 11, 13, 16, 17, 19, 22, 25, 27, 30, 32, 31, 29, 28, 26, 24, 23, 21, 20, 18, 16, 15, 12, 14, 9, 10, 2, 3, 4, 2, 8, 3, 7, 4, 9, 12, 10, 15, 14, 8, 7]
35 [35, 33, 34, 30, 28, 32, 25, 31, 22, 20, 29, 17, 14, 27, 10, 26, 5, 6, 24, 1, 23, 1, 5, 21, 6, 10, 19, 14, 18, 17, 20, 22, 25, 28, 30, 33, 35, 34, 32, 31, 29, 27, 26, 24, 23, 21, 19, 18, 16, 13, 15, 12, 9, 4, 2, 11, 3, 2, 4, 8, 3, 7, 9, 13, 12, 16, 15, 11, 8, 7]
36 [36, 34, 35, 31, 29, 33, 26, 32, 23, 21, 30, 17, 14, 28, 10, 27, 5, 6, 25, 1, 24, 1, 5, 22, 6, 10, 20, 14, 19, 17, 18, 21, 23, 26, 29, 31, 34, 36, 35, 33, 32, 30, 28, 27, 25, 24, 22, 20, 19, 18, 16, 13, 15, 12, 9, 4, 2, 11, 3, 2, 4, 8, 3, 7, 9, 13, 12, 16, 15, 11, 8, 7]
40 [40, 38, 39, 35, 33, 37, 30, 36, 27, 25, 34, 22, 20, 32, 17, 31, 13, 11, 29, 7, 28, 3, 1, 26, 1, 3, 24, 7, 23, 11, 13, 21, 17, 20, 22, 25, 27, 30, 33, 35, 38, 40, 39, 37, 36, 34, 32, 31, 29, 28, 26, 24, 23, 21, 19, 16, 18, 15, 12, 4, 6, 14, 2, 5, 4, 2, 10, 6, 9, 5, 8, 12, 16, 15, 19, 18, 14, 10, 9, 8]
43 [43, 41, 42, 38, 36, 40, 33, 39, 30, 28, 37, 25, 23, 35, 20, 34, 16, 14, 32, 5, 31, 8, 6, 29, 2, 5, 27, 2, 26, 6, 8, 24, 14, 16, 22, 20, 23, 25, 28, 30, 33, 36, 38, 41, 43, 42, 40, 39, 37, 35, 34, 32, 31, 29, 27, 26, 24, 22, 21, 19, 17, 15, 18, 12, 7, 1, 3, 1, 13, 4, 3, 11, 7, 10, 4, 9, 12, 15, 17, 19, 21, 18, 13, 11, 10, 9]
44 [44, 42, 43, 39, 37, 41, 34, 40, 31, 29, 38, 26, 24, 36, 20, 35, 16, 14, 33, 5, 32, 8, 6, 30, 2, 5, 28, 2, 27, 6, 8, 25, 14, 16, 23, 20, 22, 24, 26, 29, 31, 34, 37, 39, 42, 44, 43, 41, 40, 38, 36, 35, 33, 32, 30, 28, 27, 25, 23, 22, 21, 19, 17, 15, 18, 12, 7, 1, 3, 1, 13, 4, 3, 11, 7, 10, 4, 9, 12, 15, 17, 19, 21, 18, 13, 11, 10, 9]
52 [52, 50, 51, 47, 45, 49, 42, 48, 39, 37, 46, 34, 32, 44, 29, 43, 26, 24, 41, 20, 40, 16, 14, 38, 7, 9, 36, 2, 35, 3, 2, 33, 7, 3, 31, 9, 30, 14, 16, 28, 20, 27, 24, 26, 29, 32, 34, 37, 39, 42, 45, 47, 50, 52, 51, 49, 48, 46, 44, 43, 41, 40, 38, 36, 35, 33, 31, 30, 28, 27, 25, 23, 21, 19, 22, 15, 8, 6, 1, 18, 1, 17, 4, 5, 6, 8, 13, 4, 12, 5, 11, 15, 10, 19, 21, 23, 25, 22, 18, 17, 13, 12, 11, 10]
55 [55, 53, 54, 50, 48, 52, 45, 51, 42, 40, 49, 37, 35, 47, 32, 46, 29, 27, 44, 23, 43, 20, 17, 41, 10, 11, 39, 4, 38, 8, 2, 36, 4, 2, 34, 10, 33, 11, 8, 31, 17, 30, 20, 23, 28, 27, 29, 32, 35, 37, 40, 42, 45, 48, 50, 53, 55, 54, 52, 51, 49, 47, 46, 44, 43, 41, 39, 38, 36, 34, 33, 31, 30, 28, 26, 24, 25, 21, 19, 16, 22, 9, 14, 6, 3, 18, 7, 5, 3, 15, 6, 9, 13, 5, 7, 12, 16, 14, 19, 21, 24, 26, 25, 22, 18, 15, 13, 1, 12, 1]
63 [63, 61, 62, 58, 56, 60, 53, 59, 50, 48, 57, 45, 43, 55, 40, 54, 37, 35, 52, 32, 51, 29, 27, 49, 23, 20, 47, 17, 46, 12, 9, 44, 10, 3, 42, 2, 41, 3, 2, 39, 9, 38, 12, 10, 36, 17, 20, 34, 23, 33, 27, 29, 32, 35, 37, 40, 43, 45, 48, 50, 53, 56, 58, 61, 63, 62, 60, 59, 57, 55, 54, 52, 51, 49, 47, 46, 44, 42, 41, 39, 38, 36, 34, 33, 31, 28, 30, 25, 26, 22, 19, 8, 18, 24, 11, 6, 4, 21, 5, 7, 8, 4, 6, 16, 5, 15, 11, 7, 13, 14, 19, 18, 22, 25, 28, 26, 31, 30, 24, 21, 16, 15, 13, 1, 14, 1]
64 [64, 62, 63, 59, 57, 61, 54, 60, 51, 49, 58, 46, 44, 56, 41, 55, 38, 36, 53, 33, 52, 29, 27, 50, 23, 20, 48, 17, 47, 12, 9, 45, 10, 3, 43, 2, 42, 3, 2, 40, 9, 39, 12, 10, 37, 17, 20, 35, 23, 34, 27, 29, 32, 33, 36, 38, 41, 44, 46, 49, 51, 54, 57, 59, 62, 64, 63, 61, 60, 58, 56, 55, 53, 52, 50, 48, 47, 45, 43, 42, 40, 39, 37, 35, 34, 32, 31, 28, 30, 25, 26, 22, 19, 8, 18, 24, 11, 6, 4, 21, 5, 7, 8, 4, 6, 16, 5, 15, 11, 7, 13, 14, 19, 18, 22, 25, 28, 26, 31, 30, 24, 21, 16, 15, 13, 1, 14, 1]
67 [67, 65, 66, 62, 60, 64, 57, 63, 54, 52, 61, 49, 47, 59, 44, 58, 41, 39, 56, 36, 55, 33, 30, 53, 26, 24, 51, 20, 50, 13, 11, 48, 12, 3, 46, 4, 45, 3, 7, 43, 4, 42, 11, 13, 40, 12, 7, 38, 20, 37, 24, 26, 35, 30, 34, 33, 36, 39, 41, 44, 47, 49, 52, 54, 57, 60, 62, 65, 67, 66, 64, 63, 61, 59, 58, 56, 55, 53, 51, 50, 48, 46, 45, 43, 42, 40, 38, 37, 35, 34, 32, 29, 31, 28, 25, 23, 21, 27, 18, 9, 10, 2, 5, 22, 2, 8, 6, 19, 5, 9, 17, 10, 16, 6, 8, 14, 15, 18, 21, 23, 25, 29, 28, 32, 31, 27, 22, 19, 17, 16, 14, 1, 15, 1]
72 [72, 70, 71, 67, 65, 69, 62, 68, 59, 57, 66, 54, 52, 64, 49, 63, 46, 44, 61, 41, 60, 38, 36, 58, 33, 30, 56, 27, 55, 23, 20, 53, 17, 14, 51, 10, 50, 5, 3, 48, 4, 47, 3, 5, 45, 4, 10, 43, 14, 42, 17, 20, 40, 23, 39, 27, 30, 37, 33, 36, 38, 41, 44, 46, 49, 52, 54, 57, 59, 62, 65, 67, 70, 72, 71, 69, 68, 66, 64, 63, 61, 60, 58, 56, 55, 53, 51, 50, 48, 47, 45, 43, 42, 40, 39, 37, 35, 32, 34, 31, 28, 26, 24, 22, 29, 15, 13, 8, 6, 25, 7, 12, 9, 11, 21, 6, 8, 19, 7, 18, 13, 15, 9, 16, 12, 11, 22, 24, 26, 28, 32, 31, 35, 34, 29, 25, 21, 19, 18, 2, 16, 1, 2, 1]
75 [75, 73, 74, 70, 68, 72, 65, 71, 62, 60, 69, 57, 55, 67, 52, 66, 49, 47, 64, 44, 63, 41, 39, 61, 36, 33, 59, 30, 58, 26, 24, 56, 20, 17, 54, 14, 53, 5, 6, 51, 7, 50, 3, 5, 48, 6, 3, 46, 7, 45, 14, 17, 43, 20, 42, 24, 26, 40, 30, 33, 38, 36, 39, 41, 44, 47, 49, 52, 55, 57, 60, 62, 65, 68, 70, 73, 75, 74, 72, 71, 69, 67, 66, 64, 63, 61, 59, 58, 56, 54, 53, 51, 50, 48, 46, 45, 43, 42, 40, 38, 37, 35, 32, 29, 34, 28, 25, 23, 31, 12, 15, 9, 11, 27, 21, 4, 13, 10, 8, 22, 4, 9, 12, 19, 11, 18, 15, 8, 10, 16, 13, 23, 25, 29, 28, 32, 21, 35, 37, 34, 31, 27, 22, 19, 18, 2, 16, 1, 2, 1]
76 [76, 74, 75, 71, 69, 73, 66, 72, 63, 61, 70, 58, 56, 68, 53, 67, 50, 48, 65, 45, 64, 42, 40, 62, 36, 33, 60, 30, 59, 26, 24, 57, 20, 17, 55, 14, 54, 5, 6, 52, 7, 51, 3, 5, 49, 6, 3, 47, 7, 46, 14, 17, 44, 20, 43, 24, 26, 41, 30, 33, 39, 36, 38, 40, 42, 45, 48, 50, 53, 56, 58, 61, 63, 66, 69, 71, 74, 76, 75, 73, 72, 70, 68, 67, 65, 64, 62, 60, 59, 57, 55, 54, 52, 51, 49, 47, 46, 44, 43, 41, 39, 38, 37, 35, 32, 29, 34, 28, 25, 23, 31, 12, 15, 9, 11, 27, 21, 4, 13, 10, 8, 22, 4, 9, 12, 19, 11, 18, 15, 8, 10, 16, 13, 23, 25, 29, 28, 32, 21, 35, 37, 34, 31, 27, 22, 19, 18, 2, 16, 1, 2, 1]
83 [83, 81, 82, 78, 76, 80, 73, 79, 70, 68, 77, 65, 63, 75, 60, 74, 57, 55, 72, 52, 71, 49, 47, 69, 44, 42, 67, 39, 66, 36, 33, 64, 30, 27, 62, 23, 61, 17, 14, 59, 15, 58, 7, 4, 56, 5, 11, 54, 4, 53, 7, 5, 51, 14, 50, 17, 15, 48, 11, 23, 46, 27, 45, 30, 33, 43, 36, 39, 42, 44, 47, 49, 52, 55, 57, 60, 63, 65, 68, 70, 73, 76, 78, 81, 83, 82, 80, 79, 77, 75, 74, 72, 71, 69, 67, 66, 64, 62, 61, 59, 58, 56, 54, 53, 51, 50, 48, 46, 45, 43, 41, 38, 40, 37, 34, 32, 29, 26, 35, 25, 16, 13, 24, 31, 8, 6, 3, 28, 12, 9, 3, 10, 6, 8, 22, 13, 21, 16, 20, 9, 19, 12, 10, 18, 26, 25, 29, 24, 32, 34, 38, 37, 41, 40, 35, 31, 28, 22, 21, 20, 19, 2, 18, 1, 2, 1]
84 [84, 82, 83, 79, 77, 81, 74, 80, 71, 69, 78, 66, 64, 76, 61, 75, 58, 56, 73, 53, 72, 50, 48, 70, 45, 43, 68, 39, 67, 36, 33, 65, 30, 27, 63, 23, 62, 17, 14, 60, 15, 59, 7, 4, 57, 5, 11, 55, 4, 54, 7, 5, 52, 14, 51, 17, 15, 49, 11, 23, 47, 27, 46, 30, 33, 44, 36, 39, 42, 43, 45, 48, 50, 53, 56, 58, 61, 64, 66, 69, 71, 74, 77, 79, 82, 84, 83, 81, 80, 78, 76, 75, 73, 72, 70, 68, 67, 65, 63, 62, 60, 59, 57, 55, 54, 52, 51, 49, 47, 46, 44, 42, 41, 38, 40, 37, 34, 32, 29, 26, 35, 25, 16, 13, 24, 31, 8, 6, 3, 28, 12, 9, 3, 10, 6, 8, 22, 13, 21, 16, 20, 9, 19, 12, 10, 18, 26, 25, 29, 24, 32, 34, 38, 37, 41, 40, 35, 31, 28, 22, 21, 20, 19, 2, 18, 1, 2, 1]
87 [87, 85, 86, 82, 80, 84, 77, 83, 74, 72, 81, 69, 67, 79, 64, 78, 61, 59, 76, 56, 75, 53, 51, 73, 48, 46, 71, 43, 70, 39, 36, 68, 33, 30, 66, 27, 65, 23, 17, 63, 14, 62, 16, 7, 60, 12, 3, 58, 4, 57, 3, 7, 55, 4, 54, 14, 17, 52, 12, 16, 50, 23, 49, 27, 30, 47, 33, 36, 45, 39, 44, 43, 46, 48, 51, 53, 56, 59, 61, 64, 67, 69, 72, 74, 77, 80, 82, 85, 87, 86, 84, 83, 81, 79, 78, 76, 75, 73, 71, 70, 68, 66, 65, 63, 62, 60, 58, 57, 55, 54, 52, 50, 49, 47, 45, 44, 42, 40, 41, 37, 35, 32, 38, 31, 28, 26, 24, 34, 8, 15, 9, 11, 6, 29, 13, 5, 10, 8, 25, 6, 9, 5, 22, 11, 21, 15, 20, 10, 13, 18, 19, 24, 26, 28, 32, 31, 35, 37, 40, 42, 41, 38, 34, 29, 25, 22, 21, 20, 18, 2, 19, 1, 2, 1]
95 [95, 93, 94, 90, 88, 92, 85, 91, 82, 80, 89, 77, 75, 87, 72, 86, 69, 67, 84, 64, 83, 61, 59, 81, 56, 54, 79, 51, 78, 48, 46, 76, 43, 40, 74, 36, 73, 33, 30, 71, 26, 70, 18, 15, 68, 17, 9, 66, 6, 65, 13, 14, 63, 4, 62, 6, 9, 60, 4, 15, 58, 18, 57, 17, 13, 55, 14, 26, 53, 30, 52, 33, 36, 50, 40, 49, 43, 46, 48, 51, 54, 56, 59, 61, 64, 67, 69, 72, 75, 77, 80, 82, 85, 88, 90, 93, 95, 94, 92, 91, 89, 87, 86, 84, 83, 81, 79, 78, 76, 74, 73, 71, 70, 68, 66, 65, 63, 62, 60, 58, 57, 55, 53, 52, 50, 49, 47, 45, 42, 39, 44, 38, 35, 32, 41, 31, 28, 34, 25, 37, 16, 12, 7, 11, 8, 3, 5, 10, 29, 3, 7, 27, 5, 8, 12, 11, 24, 16, 10, 23, 19, 20, 21, 22, 25, 28, 32, 31, 35, 39, 38, 42, 34, 45, 47, 44, 41, 37, 29, 27, 19, 24, 20, 23, 21, 2, 22, 1, 2, 1]
96 [96, 94, 95, 91, 89, 93, 86, 92, 83, 81, 90, 78, 76, 88, 73, 87, 70, 68, 85, 65, 84, 62, 60, 82, 57, 55, 80, 52, 79, 49, 46, 77, 43, 40, 75, 36, 74, 33, 30, 72, 26, 71, 18, 15, 69, 17, 9, 67, 6, 66, 13, 14, 64, 4, 63, 6, 9, 61, 4, 15, 59, 18, 58, 17, 13, 56, 14, 26, 54, 30, 53, 33, 36, 51, 40, 50, 43, 46, 48, 49, 52, 55, 57, 60, 62, 65, 68, 70, 73, 76, 78, 81, 83, 86, 89, 91, 94, 96, 95, 93, 92, 90, 88, 87, 85, 84, 82, 80, 79, 77, 75, 74, 72, 71, 69, 67, 66, 64, 63, 61, 59, 58, 56, 54, 53, 51, 50, 48, 47, 45, 42, 39, 44, 38, 35, 32, 41, 31, 28, 34, 25, 37, 16, 12, 7, 11, 8, 3, 5, 10, 29, 3, 7, 27, 5, 8, 12, 11, 24, 16, 10, 23, 19, 20, 21, 22, 25, 28, 32, 31, 35, 39, 38, 42, 34, 45, 47, 44, 41, 37, 29, 27, 19, 24, 20, 23, 21, 2, 22, 1, 2, 1]

Для ознакомления, вот исходный код: 

import java.util.*;

public class LangfordPairing {
    static void langford(int N) {
        BitSet bs = new BitSet();
        bs.set(N * 2);
        put(bs, N, new int[2 * N]);
    }
    static void put(BitSet bs, int n, int[] arr) {
        if (n == 0) {
            System.out.println(Arrays.toString(arr));
            System.exit(0); // one is enough!
        }
        for (int i = -1, L = bs.length() - n - 1;
                    (i = bs.nextClearBit(i + 1)) < L ;) {

            final int j = i + n + 1;
            if (!bs.get(j)) {
                arr[i] = n;
                arr[j] = n;
                bs.flip(i);
                bs.flip(j);
                put(bs, n - 1, arr);
                bs.flip(i);
                bs.flip(j);
            }
        }
    }
    public static void main(String[] args) {
        langford(87);
    }
}

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

Обратите внимание, что, как уже упоминалось, как правило, существует множество решений для любого N. Для N = 7 существует 26 решений: 

[7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1]
[7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1]
[7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1]
[7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5]
[7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2]
[7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5]
[7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2]
[7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1]

[5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1]
[3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1]
[5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2]
[5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4]
[1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5]
[5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2]
[1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4]
[2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6]

[6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1]
[2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3]
[3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5]
[5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3]
[2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4]
[4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5]
[5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4]
[3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1]
[3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4]
[2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5]

Ссылки по теме

Вложения

6 голосов
/ 18 августа 2010

Существует только решение этой проблемы для пар чисел от 1-n, где n = 4m или n = 4m-1 для любого натурального числа m.

Обновление:

ДляВ любом решении пары нечетных чисел должны занимать две нечетные или две четные позиции.Четные пары чисел должны занимать одну из каждой.Если существует нечетное количество нечетных пар (например, 1 1 2 2 3 3 4 4 5 5 - 3 нечетных пары), решения не существует.Невозможно разместить первое число каждой пары, не приводя к конфликту при попытке разместить второе.

См. http://en.wikipedia.org/wiki/Langford_pairing

Еще одно обновление:

Мой ответ был в основном от Кнута.Я все обдумывал и сам придумал следующее.

Для любой последовательности {1 1 2 2 ... nn} есть, скажем, m нечетных пар, nm четных пар и 2n позиций для их размещения (т.е. n позиций каждой четности).

Если вы сначала размещаете четные пары, то используете четные позиции nm и нечетные позиции nm, таким образом, у вас есть m позиций каждой четности слева, в которые можно разместить нечетные пары.

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

Если m нечетно, однако, вы можете разместить только m-1 нечетных пар, и в этот момент у вас останется одна нечетная пара и одна позиция каждой четности.Поскольку для нечетной пары требуются позиции одинаковой четности, решения, когда m (количество нечетных пар) нечетно, не существует.

2 голосов
/ 08 сентября 2012

Я применил метод исключения с бумагой и карандашом для L (2,7).

  1. Поместите две 7s. Всего три возможности
  2. Поместите две шестерки и т. Д.
  3. При размещении 1, 2 и 3-х секунд становится очевидным, есть решение или нет.
  4. Я нашел 18 из 26 решений таким образом.
  5. Когда время и бумага позволят, я займусь L (2,8).
1 голос
/ 18 августа 2010

Я почти уверен, что видел это в «Искусстве компьютерного программирования» Кнута. Я посмотрю, когда вернусь домой сегодня вечером.

0 голосов
/ 18 августа 2010

Всегда ли это возможно?Я вижу, что картина вероятна и не определена.Это не работает в течение 1 с или 1 с и 2 с.

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

0 голосов
/ 18 августа 2010

Я думаю, что хорошей эвристикой было бы начинать с самых больших чисел.Тем не менее, вам все равно потребуется откат назад.

Проблема в том, что решение n-1 обычно мало помогает в поиске решения для n.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...