Как разделить список отрицательных и положительных чисел на наибольшее количество подмножеств, сумма которых равна 0? - PullRequest
Новая
       95

Как разделить список отрицательных и положительных чисел на наибольшее количество подмножеств, сумма которых равна 0?

2 голосов
/ 20 марта 2020

Я пытаюсь решить эту проблему, но не могу понять, как.

Предположим, у меня есть список положительных и отрицательных чисел, сумма которых гарантированно равна 0. 

[-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]

Я хочу получить список с наибольшим количеством подмножеств, используя все элементы исходного списка только один раз. И каждое подмножество должно иметь сумму 0.

Так что в случае этого простого ввода: 

[-5, -4, 5, 2, 3, -1]

наилучшие результаты , которые можно получить: 

1. [[-5, 5], [[-4, -1, 2, 3]]]   #2 subsets
2. [[-5, 2, 3], [-4, -1, 5]]     #2 subsets

Это, например, было бы полностью неправильных ответов : 

1. [[-5, -4, -1, 2, 3, 5]]       #1 subsets that is the initial list, NO
2. [[-5,5]]                      #1 subset, and not all elements are used, NO

Даже если это NP-Complete, как мне решить эту проблему даже с метод грубой силы? Мне просто нужно решение для небольшого списка номеров.

Ответы [ 3 ]

3 голосов
/ 22 марта 2020 
def get_subsets(lst):
    N = len(lst)
    cand = []
    dp = [0 for x in range(1<<N)]   # maximum number of subsets using elements represented by bitset
    back = [0 for x in range(1<<N)]

    # Section 1
    for i in range(1,1<<N):
        cur = 0
        for j in range(N):
            if i&(1<<j):
                cur += lst[j]
        if not cur:
            cand.append(i)     # if subset sums to 0, it's viable
    dp[0] = 1

    # Section 2
    for i in range(1<<N):
        while cand and cand[0] <= i:
            cand.pop(0)
        if not dp[i]:
            continue
        for j in cand:
            if i&j:     # if subsets intersect, it cannot be added
                continue
            if dp[i]+1 > dp[i|j]:
                back[i|j] = j
                dp[i|j] = dp[i]+1

    # Section 3
    ind = dp.index(max(dp))
    res = []

    while back[ind]:
        cur = []
        for i in range(N):
            if back[ind]&(1<<i):
                cur.append(lst[i])
        res.append(cur)
        ind = ind^back[ind]

    return res

print (get_subsets([-5, -4, 5, 2, 3, -1]))

По сути, это решение собирает все подмножества исходного списка, которые могут суммироваться до нуля, а затем пытается объединить как можно больше из них, не сталкиваясь. Он выполняется в наихудшем случае за O (2 ^ {2N}) времени, где N - длина списка, но в среднем он должен достигать O (2 ^ N), поскольку обычно не должно быть слишком много подмножества, суммирующие до 0.

РЕДАКТИРОВАТЬ: я добавил разделы, чтобы облегчить объяснение алгоритма

Раздел 1. Я перебираю все возможные 2 ^ N-1 непустых подмножеств исходного списка и проверяю какое из этих подмножеств суммируется в 0; любые жизнеспособные подмножества с нулевой суммой добавляются в список cand (представленный как целое число в диапазоне [1,2 ^ N-1] с битами, установленными в индексах, составляющих подмножество).

Раздел 2: dp - это динамическая таблица программирования c, хранящая максимальное количество подмножеств, суммирующих до 0, которое может быть сформировано с использованием подмножества, представленного целым числом i в dp[i]. Первоначально все записи dp установлены в 0, кроме dp[0] = 1, поскольку пустой набор имеет сумму 0. Затем я перебираю каждое подмножество от 0 до 2 ^ N-1 и пробегаю список кандидатов подмножества и попытка объединить два подмножества.

Раздел 3: Это просто возвращение назад, чтобы найти ответ: при заполнении dp я также сохранил массив back, в котором хранится самое последнее подмножество, добавленное в достичь подмножества i на back[i]. Поэтому я нахожу подмножество, которое максимизирует количество подмножеств, суммирующих до 0 с ind = dp.index(max(dp)), и затем я возвращаюсь назад, сокращая подмножество, удаляя последнее добавленное подмножество, пока я наконец не вернусь к пустому набору.

1 голос
/ 02 апреля 2020

Эта задача является NP-полной, поскольку она представляет собой комбинацию из двух NP-полных задач:

  • поиск одного подмножества с суммой 0 называется суммой подмножества Задача
  • Когда вы найдете все подмножества, сумма которых составляет 0, вы должны решить задачу точного покрытия со специальным условием: вы хотите максимизировать количество подмножеств .

Следующие шаги обеспечат решение:

Несколько замечаний:

  1. Во-первых, мы знаем, что существует точное покрытие, потому что список число имеет сумму 0.

  2. Во-вторых, мы можем использовать только те подмножества, которые не являются надмножествами других подмножеств. Потому что, если A является надмножеством X (сумма равна 0), A не может быть в обложке с наибольшим количеством подмножеств. Пусть A, B, C, ... будет обложкой с максимальным числом подмножеств, тогда мы можем заменить A на X и A\X (легко увидеть, что сумма из A\X элементов 0) и мы получаем покрытие X, A\X, B, C, ... что лучше.

  3. В-третьих, когда мы используем алгоритм X, все пути в дереве поиска приведут к успеху. Пусть A, B, C, ... будут путями, состоящими из непересекающихся подмножеств, каждая из которых имеет сумму 0. Тогда у дополнения также есть сумма 0 (которая может быть надмножеством другого подмножества, и тогда мы будем использовать 2.).

Как видите, ничего нового здесь , и я буду использовать только хорошо известные методы / алгоритмы.

Найти подмножества, имеющие сумму 0.

Алгоритм хорошо известен. Вот реализация Python, основанная на объяснениях Википедии 

class Q:
    def __init__(self, values):
        self.len = len(values)
        self.min = sum(e for e in values if e <= 0)
        self.max = sum(e for e in values if e >= 0)
        self._arr = [False] * self.len * (self.max - self.min + 1)

    def __getitem__(self, item):
        index, v = item
        return self._arr[v * self.len + index]

    def __setitem__(self, item, value):
        index, v = item
        self._arr[v * self.len + index] = value


class SubsetSum:
    def __init__(self, values):
        self._values = values
        self._q = Q(values)

    def prepare(self):
        for s in range(self._q.min, self._q.max + 1):
            self._q[0, s] = (self._values[0] == s)
        for i in range(self._q.len):
            self._q[i, 0] = True

        for i in range(1, self._q.len):
            v = self._values[i]
            for s in range(self._q.min, self._q.max + 1):
                self._q[i, s] = (v == s) or self._q[i - 1, s] or self._q[
                    i - 1, s - v]

    def subsets(self, target=0):
        yield from self._subsets(self._q.len - 1, target, [])

    def _subsets(self, i, target, p):
        assert i >= 0
        v = self._values[i]
        c = self._q[i - 1, target]
        b = self._q[i - 1, target - v]
        if i == 0:
            if target == 0:
                if p:
                    yield p
            elif self._q[0, target]:
                yield p + [i]
        else:
            if self._q.min <= target - v <= self._q.max and self._q[
                i - 1, target - v]:
                yield from self._subsets(i - 1, target - v, p + [i])

            if self._q[i - 1, target]:
                yield from self._subsets(i - 1, target, p)

Вот как это работает: 

arr = [-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18]
arr = sorted(arr)
s = SubsetSum(arr)
s.prepare()
subsets0 = list(s.subsets())
print(subsets0)

Вывод: 

[[13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [13, 12, 11, 10, 9, 7, 6, 5, 3, 2, 1, 0], [13, 12, 11, 10, 9, 4, 2, 1, 0], [13, 12, 11, 10, 8, 7, 4, 2, 1, 0], [13, 12, 11, 10, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 10, 7, 2, 1, 0], [13, 12, 11, 10, 6, 5, 3, 1, 0], [13, 12, 11, 9, 8, 7, 4, 2, 1, 0], [13, 12, 11, 9, 8, 6, 5, 4, 3, 1, 0], [13, 12, 11, 9, 7, 2, 1, 0], [13, 12, 11, 9, 6, 5, 3, 1, 0], [13, 12, 11, 8, 7, 6, 5, 3, 1, 0], [13, 12, 11, 8, 4, 1, 0], [13, 12, 11, 1, 0], [13, 12, 10, 9, 8, 7, 6, 5, 4, 3, 1, 0], [13, 12, 10, 9, 8, 2, 1, 0], [13, 12, 10, 9, 7, 6, 5, 3, 1, 0], [13, 12, 10, 9, 4, 1, 0], [13, 12, 10, 8, 7, 4, 1, 0], [13, 12, 10, 7, 1, 0], [13, 12, 9, 8, 7, 4, 1, 0], [13, 12, 9, 7, 1, 0], [13, 11, 10, 8, 6, 5, 4, 3, 2, 0], [13, 11, 10, 6, 5, 3, 2, 0], [13, 11, 9, 8, 6, 5, 4, 3, 2, 0], [13, 11, 9, 6, 5, 3, 2, 0], [13, 11, 8, 7, 6, 5, 3, 2, 0], [13, 11, 8, 4, 2, 0], [13, 11, 7, 6, 5, 4, 3, 2, 1], [13, 11, 7, 6, 5, 4, 3, 0], [13, 11, 2, 0], [13, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0], [13, 10, 9, 7, 6, 5, 3, 2, 0], [13, 10, 9, 4, 2, 0], [13, 10, 8, 7, 4, 2, 0], [13, 10, 8, 6, 5, 4, 3, 2, 1], [13, 10, 8, 6, 5, 4, 3, 0], [13, 10, 7, 2, 0], [13, 10, 6, 5, 3, 2, 1], [13, 10, 6, 5, 3, 0], [13, 9, 8, 7, 4, 2, 0], [13, 9, 8, 6, 5, 4, 3, 2, 1], [13, 9, 8, 6, 5, 4, 3, 0], [13, 9, 7, 2, 0], [13, 9, 6, 5, 3, 2, 1], [13, 9, 6, 5, 3, 0], [13, 8, 7, 6, 5, 3, 2, 1], [13, 8, 7, 6, 5, 3, 0], [13, 8, 4, 2, 1], [13, 8, 4, 0], [13, 7, 6, 5, 4, 3, 1], [13, 2, 1], [13, 0], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 0], [12, 11, 10, 9, 8, 2, 0], [12, 11, 10, 9, 7, 6, 5, 3, 2, 1], [12, 11, 10, 9, 7, 6, 5, 3, 0], [12, 11, 10, 9, 4, 2, 1], [12, 11, 10, 9, 4, 0], [12, 11, 10, 8, 7, 4, 2, 1], [12, 11, 10, 8, 7, 4, 0], [12, 11, 10, 8, 6, 5, 4, 3, 1], [12, 11, 10, 7, 2, 1], [12, 11, 10, 7, 0], [12, 11, 10, 6, 5, 3, 1], [12, 11, 9, 8, 7, 4, 2, 1], [12, 11, 9, 8, 7, 4, 0], [12, 11, 9, 8, 6, 5, 4, 3, 1], [12, 11, 9, 7, 2, 1], [12, 11, 9, 7, 0], [12, 11, 9, 6, 5, 3, 1], [12, 11, 8, 7, 6, 5, 3, 1], [12, 11, 8, 4, 1], [12, 11, 1], [12, 10, 9, 8, 7, 6, 5, 4, 3, 1], [12, 10, 9, 8, 2, 1], [12, 10, 9, 8, 0], [12, 10, 9, 7, 6, 5, 3, 1], [12, 10, 9, 4, 1], [12, 10, 8, 7, 4, 1], [12, 10, 7, 1], [12, 9, 8, 7, 4, 1], [12, 9, 7, 1], [11, 10, 8, 6, 5, 4, 3, 2], [11, 10, 6, 5, 3, 2], [11, 9, 8, 6, 5, 4, 3, 2], [11, 9, 6, 5, 3, 2], [11, 8, 7, 6, 5, 3, 2], [11, 8, 4, 2], [11, 7, 6, 5, 4, 3], [11, 2], [10, 9, 8, 7, 6, 5, 4, 3, 2], [10, 9, 7, 6, 5, 3, 2], [10, 9, 4, 2], [10, 8, 7, 4, 2], [10, 8, 6, 5, 4, 3], [10, 7, 2], [10, 6, 5, 3], [9, 8, 7, 4, 2], [9, 8, 6, 5, 4, 3], [9, 7, 2], [9, 6, 5, 3], [8, 7, 6, 5, 3], [8, 4]]

Уменьшите количество подмножеств

У нас есть 105 подмножеств, которые составляют 0, но мы можем удалить подмножества, которые являются надмножеством других подмножеств. Нам нужна функция, чтобы определить, содержит ли список элементов все элементы другого списка. В Python: 

import collections

def contains(l1, l2):
    """
    Does l1 contain all elements of l2?
    """
    c = collections.Counter(l1)
    for e in l2:
        c[e] -= 1
    return all(n >= 0 for n in c.values())

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

def remove_supersets(subsets):
    subsets = sorted(subsets, key=len)
    new_subsets = []
    for i, s1 in enumerate(subsets):
        for s2 in subsets[:i]: # smaller subsets
            if contains(s1, s2):
                break
        else:  # not a superset
            new_subsets.append(s1)
    return new_subsets

В нашей ситуации: 

subsets0 = remove_supersets(subsets0)
print(len(subsets0))

Вывод: 

[[13, 0], [11, 2], [8, 4], [13, 2, 1], [12, 11, 1], [10, 7, 2], [9, 7, 2], [12, 10, 7, 1], [12, 9, 7, 1], [10, 9, 4, 2], [10, 6, 5, 3], [9, 6, 5, 3], [12, 11, 10, 7, 0], [12, 11, 9, 7, 0], [12, 10, 9, 8, 0], [12, 10, 9, 4, 1], [8, 7, 6, 5, 3], [12, 11, 10, 9, 4, 0], [12, 10, 9, 8, 2, 1], [11, 7, 6, 5, 4, 3], [13, 7, 6, 5, 4, 3, 1]]
[[0, 2, 10, 6, 4], [0, 2, 10, 8, 1], [0, 2, 11, 5, 4], [0, 2, 11, 7, 1], [0, 16, 9, 4], [0, 16, 15, 1], [0, 18, 19], [3, 2, 12, 11], [3, 2, 13, 10], [3, 17, 16], [3, 19, 14], [20, 14, 1]]

Нам удалось сократить количество подмножеств до 21, что является хорошим улучшением, поскольку нам нужно изучить все возможности для нахождения точного покрытия.

Алгоритм X

Я не использую здесь ссылки для танцев (я думаю, что эта техника предназначена для языков низкого уровня, таких как C, но вы можете реализовать их в Python, если хотите). Нам просто нужно отслеживать оставшиеся подмножества: 

class Matrix:
    def __init__(self, subsets, ignore_indices=set()):
        self._subsets = subsets
        self._ignore_indices = ignore_indices

    def subset_values(self, i):
        assert i not in self._ignore_indices
        return self._subsets[i]

    def value_subsets_indices(self, j):
        return [i for i, s in self._subsets_generator() if j in s]

    def _subsets_generator(self):
        return ((i, s) for i, s in enumerate(self._subsets) if
                i not in self._ignore_indices)

    def rarest_value(self):
        c = collections.Counter(
            j for _, s in self._subsets_generator() for j in s)
        return c.most_common()[-1][0]

    def take_subset(self, i):
        s = self._subsets[i]
        to_ignore = {i2 for i2, s2 in self._subsets_generator() if
                     set(s2) & set(s)}
        return Matrix(self._subsets,
                      self._ignore_indices | to_ignore)

    def __bool__(self):
        return bool(list(self._subsets_generator()))

И, наконец, функцию cover: 

def cover(m, t=[]):
    if m: # m is not empty
        j = m.rarest_value()
        for i in m.value_subsets_indices(j):
            m2 = m.take_subset(i)
            yield from cover(m2, t + [i])
    else:
        yield t

Наконец, мы имеем: 

m = Matrix(subsets0)
ts = list(cover(m))
t = max(ts, key=len)
print([[arr[j] for j in subsets0[i]] for i in t])

Вывод: 

[[100, -100], [10, -10], [15, 2, 1, -18], [15, 5, -20], [60, 20, -80]]
0 голосов
/ 22 марта 2020

Ниже, по сути, та же идея, что и у Майкла Хуанга, с еще 30 строками ...

Решение с кликом

  1. Мы можем предварительно построить все подмножества, сумма которых равна 0 .

    • Создайте подмножества из 1 элемента;
    • , затем размера 2, повторно используя предыдущие
    • и сохраняйте те, чья сумма равна нулю, по пути

Теперь скажем, что такое подмножество является узлом графа. Тогда узел находится в связи с другим, если их связанное подмножество не имеет общего числа.

Таким образом, мы хотим построить максимальную клику графа:

  • В клике все узлы связаны друг с другом, и их подмножества являются несвязанными
  • Максимальная клика дает нам максимальное количество подмножеств 

function forall (v, reduce) {
  const nexts = v.map((el, i) => ({ v: [el], i, s: el })).reverse()
  while (nexts.length) {
    const next = nexts.pop()
    for (let i = next.i + 1; i < v.length; ++i) {
      const { s, skip } = reduce(next, v[i])
      if (!skip) {
        nexts.push({ v: next.v.concat(v[i]), s: s, i })
      }
    }
  }
}
function buildSubsets (numbers) {
  const sums = []
  forall(numbers, (next, el) => {
    const s = next.s + el
    if (s === 0) {
      sums.push({ s, v: next.v.concat(el) })
      return { s, skip: true }
    }
    return { s }
  })
  return sums
}
const bin2decs = bin => {
  const v = []
  const s = bin.toString(2)
  for (let i = 0; i < s.length; ++i) {
    if (intersects(dec2bin(i), bin)) {
      v.push(i)
    }
  }
  return v
}
const dec2bin = dec => Math.pow(2, dec)
const decs2bin = decs => decs.reduce((bin, dec) => union(dec2bin(dec), bin), 0)
// Set methods on int
const isIn = (a, b) => (a & b) === a
const intersects = (a, b) => a & b
const union = (a, b) => a | b

// if a subset contains another one, discard it
// e.g [1,2,4] should be discarded if [1,2] is present
const cleanSubsets = bins => bins.filter(big => bins.every(b => big === b || !isIn(b, big)))
function bestClique (decs) {
  const cliques = []
  forall(decs, (next, el) => {
    if (intersects(next.s, el)) { return { skip: true } }
    const s = union(next.s, el)
    cliques.push({ s, v: next.v.concat(el) })
    return { s }
  })
  return cliques.sort((a, b) => b.v.length - a.v.length)[0]
}
// in case we have duplicated numbers in the list,
// they are still uniq thanks to their id: i (idem position in the list)
const buildNumbers = v => v.map((n, i) => {
  const u = new Number(n)
  u.i = i
  return u
})
function run (v) {
  const numbers = buildNumbers(v)
  const subs = buildSubsets(numbers)
  const bins = subs.map(s => decs2bin(s.v.map(n => n.i)))
  const clique = bestClique(cleanSubsets(bins))
  const indexedSubs = clique.v.map(bin2decs)
  const subsets = indexedSubs.map(sub => sub.map(i => numbers[i].valueOf()))
  console.log('subsets', JSON.stringify(subsets))
}

run([1, -1, 2, -2])
run([-10, 1, 2, 20, 5, -100, -80, 10, 15, 15, 60, 100, -20, -18, 10, -10])
run([-5, -4, 5, 2, 3, -1])
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...