कुल योग

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

यह corectly प्रिंट (-1, -4, 5):

यहाँ मेरी संयोजन कोड है। हालांकि मैं सभी संभावित आइटम संयोजनों पर लूपिंग से कुछ चालाक, अधिक कुशल समाधान की तलाश में हूं।

कोई विचार?

Answer 1

यदि आप एक सबसेट जिसका योग पूरा सेट के मूल्य के बराबर की खोज के रूप में समस्या को फिर से परिभाषित, आपको एहसास होगा कि यह एक एनपी हार्ड समस्या है, (subset sum)

तो वहाँ के लिए कोई बहुपद जटिलता समाधान है यह समस्या ।

Answer 2

मैं पायथन में प्रोग्राम नहीं करता हूं इसलिए कोड की पेशकश न करने के लिए मेरी माफ़ी। लेकिन मुझे लगता है मैं एल्गोरिथ्म के साथ मदद कर सकते हैं: जब तक आप एक ही राशि

बाकी सब कुछ नष्ट कर दिया जा सकता है

मैं करने के लिए मिल

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 का उपयोग करके बड़ी जीत प्राप्त कर सकते हैं।

हम शायद एक बेहतर संस्करण लिख सकते हैं जो प्रत्येक बार चलने वाले कुल के निकट दो नंबरों को खोजने के लिए सूची को पार करता है और दोनों के करीब को हटा देता है, लेकिन फिर हम शायद ओ (एन^2) के साथ समाप्त हो जाएंगे। प्रदर्शन। मेरा मानना ​​है कि इस कोड का प्रदर्शन ओ (एन * लॉग (एन) होगा क्योंकि इसे सिर्फ सूची को सॉर्ट करना है (मुझे उम्मीद है कि पायथन की सूची सॉर्टिंग ओ (एन^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]) 

यह ठीक काम करता है, और एक बहुत मेरा पहला दृष्टिकोण की तुलना में तेजी है।विकिपीडिया लिंक और ivazquez | लैपटॉप के लिए एलोन के लिए धन्यवाद, एक अच्छा संकेत के लिए #python आईआरसी चैनल पर लैपटॉप जो मुझे समाधान में ले गया।

मुझे लगता है कि इसे और अनुकूलित किया जा सकता है - समाधान मिलने के बाद मैं महंगी हिस्से की गणना करना बंद करना चाहता हूं। मैं कोशिश जारी रखूंगा।

Answer 5

इसे पूर्णांक प्रोग्रामिंग का उपयोग करके हल किया जा सकता है। आप अपनी प्रत्येक सूची तत्व x_i के लिए एक बाइनरी चर s_i परिभाषित कर सकते हैं और \ sum_i s_i को कम से कम सीमित कर सकते हैं, जो कि \ sum_i (x_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] 
} 

अब हम कुछ उदाहरणों के साथ यह परीक्षण कर सकते हैं:

यहाँ एक कार्यान्वयन आर में lpSolve पैकेज का उपयोग अगर हम चाहते हैं कि निरीक्षण

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