xóa số khỏi danh sách mà không thay đổi tổng số

Question

Tôi có danh sách các số (ví dụ: [-1, 1, -4, 5]) và tôi phải xóa số khỏi danh sách mà không thay đổi tổng số của danh sách. Tôi muốn xóa các số có giá trị tuyệt đối lớn nhất có thể, mà không thay đổi tổng số, trong ví dụ xóa [-1, -4, 5] sẽ để lại [1] để tổng không thay đổi.

Tôi đã viết cách tiếp cận ngây thơ, tìm tất cả các kết hợp có thể không thay đổi tổng số và xem kết hợp nào loại bỏ giá trị tuyệt đối lớn nhất. Nhưng điều đó rất chậm vì danh sách thực tế sẽ lớn hơn rất nhiều.

Đây là mã kết hợp của tôi:

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

Nó corectly in (-1, -4, 5). Tuy nhiên tôi đang tìm kiếm một số giải pháp thông minh, hiệu quả hơn so với lặp trên tất cả các kết hợp mục có thể.

Bất kỳ ý tưởng nào?

Answer 1

nếu bạn xác định lại vấn đề như việc tìm kiếm một tập hợp con có tổng bằng với giá trị của bộ hoàn chỉnh, bạn sẽ nhận ra rằng đây là một vấn đề NP-cứng, (subset sum)

vì vậy không có giải pháp phức tạp đa thức cho vấn đề này .

Answer 2

Tôi không lập trình bằng Python nên xin lỗi vì không cung cấp mã. Nhưng tôi nghĩ rằng tôi có thể giúp đỡ với các thuật toán:

1. Tìm tổng
2. Thêm số với giá trị thấp nhất cho đến khi bạn nhận được để tổng cùng
3. Mọi thứ khác có thể bị xóa

tôi hy vọng điều này sẽ giúp

Answer 3

Yêu cầu của bạn không cho biết chức năng có được phép thay đổi thứ tự danh sách hay không. Đây là một khả năng:

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 

Sắp xếp danh sách này (các mục lớn sẽ ở cuối, nhỏ hơn sẽ bắt đầu) và tính tổng và loại bỏ một mục khỏi danh sách. Sau đó, nó tiếp tục xóa các mục cho đến khi tổng số mới bằng tổng số ban đầu. Một phiên bản thay thế mà giữ gìn trật tự có thể được viết như là một wrapper:

from copy import copy 

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

Mặc dù có lẽ bạn nên viết lại điều này với collections.deque nếu bạn thực sự muốn giữ gìn trật tự. Nếu bạn có thể đảm bảo tính duy nhất trong danh sách của mình, bạn có thể giành được một chiến thắng lớn bằng cách sử dụng một số set thay thế. Chúng tôi có lẽ có thể viết một phiên bản tốt hơn mà đi qua danh sách để tìm hai con số gần nhất với tổng số lần chạy và loại bỏ gần hơn của hai, nhưng sau đó chúng tôi có thể sẽ kết thúc với O (N^2) hiệu suất. Tôi tin rằng hiệu suất của mã này sẽ là O (N * log (N)) vì nó chỉ cần sắp xếp danh sách (tôi hy vọng sắp xếp danh sách của Python không phải là O (N^2)) và sau đó nhận được tổng.

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

Nó hoạt động tốt, và là nhiều hơn nhanh hơn cách tiếp cận đầu tiên của tôi.Nhờ Alon cho liên kết wikipedia và máy tính xách tay ivazquez trên kênh #python irc cho một gợi ý tốt đã đưa tôi vào giải pháp.

Tôi nghĩ rằng nó có thể được tối ưu hóa hơn nữa - Tôi muốn có cách dừng tính toán phần đắt tiền khi giải pháp đã được tìm thấy. Tôi sẽ tiếp tục cố gắng.

Answer 5

Điều này có thể được giải quyết bằng cách sử dụng lập trình số nguyên. Bạn có thể định nghĩa một biến nhị phân s_i cho mỗi phần tử danh sách của bạn x_i và giảm thiểu \ sum_i s_i, giới hạn bởi ràng buộc mà \ sum_i (x_i * s_i) bằng với tổng số tiền ban đầu của danh sách của bạn.

Dưới đây là một thực hiện bằng cách sử dụng gói lpSolve trong 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] 
} 

Bây giờ, chúng ta có thể thử nghiệm nó với một vài ví dụ:

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