Найти число способов разбиения {1,2, ..., П} в Р1 и Р2, такие, что сумма(П1) == сумма(Р2)


Я пытаюсь написать пространство и время эффективный алгоритм для вычисления количества способов разделения множества целых чисел {1, 2, ..., П} на два раздела, таких, что суммы чисел в обоих разделах одинаковы. Я начал с подхода грубой силы, что, кажется, дает мне правильные результаты:

from itertools import combinations
def f(n):
    s = set([i+1 for i in range(n)])
    valid_partitions = []
    for i in range(1,n):
        combos = combinations(s,i)
        for c in combos:
            p1 = frozenset(c)
            p2 = set(range(1,n+1)) - p1
            p2 = frozenset(p2)
            if sum(p1) == sum(p2):
                valid_partitions.append(frozenset((p1,p2)))

    return len(set(valid_partitions))

Кроме того, поскольку я проверяю каждый способ разбиения {1,2,...,П} на два непустых множества, правильно ли говорить, что о времени сложность этого подхода является S(N,2) (числа Стирлинга второго рода)? Также, как я оцениваю Большой о сложности пространства этот подход? Есть ли лучший подход я могу взять?



264
3
задан 8 февраля 2018 в 03:02 Источник Поделиться
Комментарии
3 ответа

Дублируется код/значения

У вас обоих:

s = set([i+1 for i in range(n)])

и

p2 = set(range(1,n+1)) - p1

Это плохо, потому что у вас одни и те же наборы генерируется на 2 места с 2 разных куска кода:


  • это не эффективно

  • это не легко читать и понимать

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

Вы должны написать что-то вроде:

        p2 = frozenset(s - p1)

Различные подсказки

Если sum(p1) == sum(p2)тогда sum(p1) == sum(p2) == sum(s) // 2 и sum(p1) == sum(s) // 2 является достаточным условием.
Вы могли бы написать что-то вроде:

def f(n):
s = set([i+1 for i in range(n)])
target_sum = sum(s) / 2
valid_partitions = []
for i in range(1,n):
for c in combinations(s,i):
if sum(c) == target_sum:
p1 = frozenset(c)
p2 = frozenset(s - p1)
valid_partitions.append(frozenset((p1,p2)))
return len(set(valid_partitions))

Можно просто рассматривать только p1 не позаботившись о p2. Разделы будут подсчитаны дважды, но вы всегда можете разделить результат в конце. Как только вы начинаете это, вы понимаете, что вся логика о удалив ненужные дубликаты могут быть удалены (все комбинации поколение уникальных): вам не нужно телеаппаратуры и вам не нужно frozensets:

def f(n):
s = set([i+1 for i in range(n)])
target_sum = sum(s) / 2
valid_partitions = []
for i in range(1,n):
for c in combinations(s,i):
if sum(c) == target_sum:
valid_partitions.append(c)
return len(valid_partitions) // 2

Затем, вам не нужно иметь все перегородки в контейнере, простой счетчик будет делать трюк:

def f(n):
s = set([i+1 for i in range(n)])
target_sum = sum(s) / 2
nb_partitions = 0
for i in range(1,n):
for c in combinations(s,i):
if sum(c) == target_sum:
nb_partitions += 1
return nb_partitions // 2

Затем, если вы хотите, чтобы сделать вещи более лаконичными, вы могли бы использовать sum встроенные и использовать тот факт, что истина-это 1, а false-это 0, чтобы писать что-то вроде:

def f(n):
s = set([i+1 for i in range(n)])
target_sum = sum(s) / 2
return sum(sum(c) == target_sum for i in range(1, n) for c in combinations(s, i)) // 2

Окончательной оптимизации

Если вы посмотрите на значение, возвращенное за первые 19 чисел, то получите что-то вроде:

0 0
1 0
2 0
3 1
4 1
5 0
6 0
7 4
8 7
9 0
10 0
11 35
12 62
13 0
14 0
15 361
16 657
17 0
18 0
19 4110

Мы видим, что функции возвращают 0 в 1 случае из 2. Это соответствует тому, что мы не можем раздел нечетное сумма. Это может быть приняты во внимание, чтобы избежать комбинации вычислений, когда это происходит:

def f(n):
s = set([i+1 for i in range(n)])
target_sum, rem = divmod(sum(s), 2)
if rem:
return 0
return sum(sum(c) == target_sum for i in range(1, n) for c in combinations(s, i)) // 2

Последняя деталь

Ваш первый звонок set это бесполезно, потому что элементы являются уникальными уже и вам просто нужно повторяемое. Кроме того, вы можете избавиться от списка понимания путем настройки параметров range: s = range(1, n+1).

6
ответ дан 8 февраля 2018 в 10:02 Источник Поделиться


Кроме того, поскольку я проверяю каждый способ разбиения {1,2,...,П} на два непустых множества, правильно ли говорить, что о времени сложность этого подхода является S(N,2) (числа Стирлинга второго рода)?

Нет. Во-первых, как указал Josay, алгоритм учитывает каждый набор секций в два раза. А во-вторых, он не выполняет \$О(1)\$ работы в установленный раздел. Он выполняет \$\тета(Н)\$ работать в расчете суммы. Насколько я вижу в документации itertools не гарантирует ничего о том, как долго это берет, чтобы создать каждый раздел, но Гарет Риз отмечает, что реализация тоже \$\тета(Н)\$. Так что сложность \$\тета(н{н \дубль 2}) = \тета(н \, 2^п)\$.


Есть ли лучший подход я могу взять?

Да. Решение варианта этой задачи является проблема подмножество сумма и известный динамическое программирование решение. Это решение легко адаптированы, чтобы дать отсчетов, а не только логические. В псевдо-код:

counts = { 0 => 1 }
for elt in range(1, n+1):
temp = { sum + elt => freq for (sum, freq) in counts }
possibleSums = keys(counts).union(keys(temp))
counts = { counts[sum] + temp[sum] for sum in possibleSums }
return counts[n * (n + 1) / 4]

В худшем случае counts имеет \$2^\textrm{ЭЛТ-1}\$ ключи в начале тела цикла, так что это работает в \$за O(2^н)\$ предполагаем быстро словарям.

Для полноты картины отмечу, что альтернативный, но более сложных, решение в \$\тета(2^н)\$ время будет идти через подмножеств с помощью кода Грея.

Еще более эффективных решений в данном конкретном случае (где задать вопрос range(1, n+1) а не произвольный набор), Вы можете взглянуть на портирование кода из ОЭИС A058377.

6
ответ дан 8 февраля 2018 в 11:02 Источник Поделиться


правильно ли говорить, что о большим сложность этого подхода состоит в сек(N,2) (число Стирлинга второго рода)?

Поскольку каждый элемент можно поставить на П1 или П2, есть два варианта для каждого элемента, что дает в общей сложности 2н разные варианты. Так вы избегаете тех случаях, где P1 или P2 пусты, это 2п- 2, который находится в два раза число Стирлинга второго рода (ты двойной учет, так как Стерлинг число зависит от П1 и П2 быть неразличимы). С большим игнорирует сложения или вычитания константы, это проще, чтобы просто дать сложности в части 2п , а не класть его в срок стерлингового чисел. И как @Питер Тейлор указывает, вы смотрите только на количество итераций, и не обращая внимания на сложности в рамках итерации.

Вы можете избежать большинства двойного подсчета, принимая сочетаний до N//2. Все прошлое это будет просто раздел, который вы уже получили с P1 и P2 местами. При Я == н//2, вам будет двойного счета, так что вы можете использовать @Питеру Тейлору предложение и выделить один элемент, а затем добавить его обратно в стационарной перегородкой.

1
ответ дан 8 февраля 2018 в 08:02 Источник Поделиться