удалить номера из списка без изменения общей суммы

Question

У меня есть список чисел (пример: [-1, 1, -4, 5]), и я должен удалить номера из списка без изменения общей суммы списка. Я хочу удалить числа с наибольшим возможным абсолютным значением, не меняя итоговое значение, в примере удаление [-1, -4, 5] оставит [1], поэтому сумма не изменится.

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

Вот код моей комбинации:

from itertools import chain, combinations

def remove(items):
    all_comb = chain.from_iterable(combinations(items, n+1) 
                                   for n in xrange(len(items)))
    biggest = None
    biggest_sum = 0
    for comb in all_comb:
        if sum(comb) != 0:
            continue # this comb would change total, skip
        abs_sum = sum(abs(item) for item in comb)
        if abs_sum > biggest_sum:
            biggest = comb
            biggest_sum = abs_sum
    return biggest

print remove([-1, 1, -4, 5])

Он печатает (-1, -4, 5). Однако я ищу какое-то умное, более эффективное решение, чем зацикливание на всех возможных комбинациях предметов.

Есть идеи?

Answer 1

если вы переопределите задачу как поиск подмножества, сумма которого равна значению полного набора, вы поймете, что это NP-сложная задача ( сумма подмножества )

так что для этой задачи не существует решения по полиномиальной сложности.

Answer 2

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Copyright © 2009 Clóvis Fabrício Costa
# Licensed under GPL version 3.0 or higher

def posneg_calcsums(subset):
    sums = {}
    for group in chain.from_iterable(combinations(subset, n+1) 
                                     for n in xrange(len(subset))):
        sums[sum(group)] = group
    return sums

def posneg(items):
    positive = posneg_calcsums([item for item in items if item > 0])
    negative = posneg_calcsums([item for item in items if item < 0])
    for n in sorted(positive, reverse=True):
        if -n in negative:
            return positive[n] + negative[-n]
    else:
        return None

print posneg([-1, 1, -4, 5])
print posneg([6, 44, 1, -7, -6, 19])

Работает нормально, и намного быстрее, чем мой первый подход. Спасибо Алону за ссылку в Википедии и ноутбук ivazquez | на канале #python irc за хороший совет, который привел меня к решению.

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

Answer 3

Это можно решить с помощью целочисленного программирования. Вы можете определить двоичную переменную s_i для каждого из элементов списка x_i и минимизировать \ sum_i s_i, ограниченную ограничением, что \ sum_i (x_i * s_i) равен исходной сумме вашего списка.

Вот реализация, использующая пакет lpSolve в R:

library(lpSolve)
get.subset <- function(lst) {
  res <- lp("min", rep(1, length(lst)), matrix(lst, nrow=1), "=", sum(lst),
            binary.vec=seq_along(lst))
  lst[res$solution > 0.999]
}

Теперь мы можем проверить это на нескольких примерах:

get.subset(c(1, -1, -4, 5))
# [1] 1
get.subset(c(6, 44, 1, -7, -6, 19))
# [1] 44 -6 19
get.subset(c(1, 2, 3, 4))
# [1] 1 2 3 4

Answer 4

В ваших требованиях не указано, разрешено ли функции изменять порядок списка или нет. Вот возможность:

def remove(items):
    items.sort()
    running = original = sum(items)
    try:
        items.index(original) # we just want the exception
        return [original]
    except ValueError:
        pass
    if abs(items[0]) > items[-1]:
        running -= items.pop(0)
    else:
        running -= items.pop()
    while running != original:
        try:
            running -= items.pop(items.index(original - running))
        except ValueError:
            if running > original:
                running -= items.pop()
            elif running < original:
                running -= items.pop(0)
    return items

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

from copy import copy

def remove_preserve_order(items):
    a = remove(copy(items))
    return [x for x in items if x in a]

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

Возможно, мы могли бы написать лучшую версию, которая обходит список, чтобы каждый раз находить два числа, наиболее близкие к итоговой сумме, и убирать их ближе к двум, но тогда мы, вероятно, в итоге получили бы производительность O (N ^ 2) , Я полагаю, что производительность этого кода будет O (N * log (N)), поскольку он просто должен отсортировать список (я надеюсь, что сортировка списка Python не O (N ^ 2)), а затем получить сумму.

Answer 5

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

1. Найти сумму
2. Добавляйте числа с наименьшим значением, пока не получите ту же сумму
3. Все остальное можно удалить

Надеюсь, это поможет