총계를 변경하지 않고 목록에서 번호를 제거하십시오.

Question

숫자 목록 (예 : [-1, 1, -4, 5])을 가지고 있으며 목록의 총계를 변경하지 않고 목록에서 번호를 제거해야합니다. 예를 들어 총계를 변경하지 않고 가능한 가장 큰 절대 값을 가진 숫자를 제거하려면 [-1, -4, 5]은 [1]을 남겨두고 합계가 변경되지 않도록합니다.

나는 총 값을 변경하지 않고 가능한 가장 큰 절대 값을 제거하는 모든 가능한 조합을 찾는 순진 접근법을 작성했습니다. 그러나 실제 목록이 그보다 훨씬 커질 것이기 때문에 그것은 정말로 느립니다. 그것은 corectly (-1, -4, 5) 인쇄

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]) 

:

여기 내 조합 코드입니다. 그러나 모든 가능한 항목 조합을 반복하는 것보다 영리하고 효율적인 솔루션을 찾고 있습니다.

아이디어가 있으십니까? 당신은 누구의 합이 완전한 세트의 값과 동일한 하위 집합을 찾는 등의 문제를 다시 정의 할 경우

Answer 1

, 당신은

그렇게에 대한 다항식의 복잡성 솔루션이 없습니다, 이것은 NP-하드 문제입니다 (subset sum)을 실현한다 이 문제 .

Answer 2

저는 파이썬으로 프로그래밍하지 않으므로 코드를 제공하지 않는 것에 대해 사과드립니다. 당신은 다른 모든

I를 삭제할 수 있습니다

같은 금액에 도달 할 때까지

1. 는
2. 가장 낮은 값으로 숫자를 추가 합을 찾기 :하지만 내가 알고리즘에 도움이 할 수 있다고 생각 이 도움이되기를 바랍니다.

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 이것을 다시 작성해야하지만. 목록에서 고유성을 보장 할 수 있다면 set을 사용하면 큰 효과를 얻을 수 있습니다.

매번 누적 합계에 가장 가까운 두 개의 숫자를 찾고 더 가까운 것을 제거하기 위해 목록을 탐색하는 더 나은 버전을 작성할 수 있지만, 아마도 O (N^2) 공연. 필자는이 코드의 성능은 O (N * log (N)) 일 것이라고 생각합니다. 목록을 정렬해야하므로 (파이썬의 목록 정렬이 O (N^2)이 아닌 경우) 합계를 구해야합니다.

Answer 4

#!/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]) 

그것은 잘 작동, 내 첫 번째 방법보다 훨씬 빠른 입니다.wikipedia 링크는 Alon, #python irc 채널은 iazesquez 노트북 덕분에 해결책을 찾았습니다.

나는 그것이 더 최적화 될 수 있다고 생각한다. 해결책이 발견되면 값 비싼 부분을 계산하는 것을 멈추고 싶다. 나는 계속 노력할 것이다.

Answer 5

이것은 정수 프로그래밍을 사용하여 해결할 수 있습니다. \ sum_i (x_i * s_i)가리스트의 최초 합계와 같은 제약 조건에 의해 제한되는 각리스트 요소 x_i와 minimize \ sum_i s_i에 대해 이진 변수 s_i를 정의 할 수 있습니다. 우리는 몇 가지 예제를 테스트 할 수 있습니다, 지금

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