удалите числа из списка, не изменяя полную сумму

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). Однако я ищу некоторое умное, более эффективное решение, чем цикличное выполнение по всем возможным комбинациям объекта.

Какие-либо идеи?

7

python math sum combinations mathematical-optimization

задан josliber 7 May 2014 в 17:51

4 ответа

Другие вопросы по тегам:

python math sum combinations mathematical-optimization

Похожие вопросы:

score 4 · Answer 1

#!/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 | laptop на #python irc-канале за хороший намек, который привел меня к решению.

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

score 11 · Answer 2

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

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

score 0 · Answer 3

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

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 , если вы действительно хотите сохранить порядок. Если вы можете гарантировать уникальность своего списка, вы можете получить большой выигрыш, используя вместо него набор .

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

score 0 · Answer 4

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

Найдите сумму
Сложите числа с наименьшим значением, пока не получите ту же сумму
Все остальное можно удалить

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