Найти сходство между двумя списками

Question

У меня есть два списка номеров (L1 и L2). И я должен выяснить, есть ли любая комбинация L1 в любой комбинации чисел L2.

Я пробовал двойной цикл с помощью функции powerset (). Однако это медленно.

генератор powerset (): technomancy.org/python/powerset-generator-python.

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

Дополнительная проблема: ListA может быть списком монстров с точки зрения длины и диапазона чисел

Answer 1

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

def all_sums (numbers):
    answer = {0: None}
    for n in numbers:
        next_answer = {}
        for s, path in answer.iteritems():
            next_answer[s] = path
            next_answer[round(s + n, 8)] = [n, path]
        answer = next_answer
    if answer[0] is None:
        answer.pop(0)
    return answer

def find_matching_sum (numbers1, numbers2):
    sums1 = all_sums(numbers1)
    sums2 = all_sums(numbers2)
    for s1, path1 in sums1.iteritems():
        if s1 in sums2:
            return [s1, path1, sums2[s1]]
    return None

listA = [455, 698, 756, 3.56, -9]

listB = [526,55,943,156,531,304,618,911,598,498,268,926,899,898,131,966,303,936,509,67,976,639,74,935,23,226,422,280,64,975,583,596,583]
print(find_matching_sum(listA, listB))

С плавающей запятой я бы предложил попробовать умножить наобщий знаменатель, чтобы добраться до целых чисел.Это связано с проблемой 0.1 + 0.2 != 0.3.Также имейте в виду, что с плавающей запятой легко получить очень и очень большое количество возможных сумм, и поэтому подход динамического программирования больше не является победой.Для крайнего примера рассмотрим [..., 8, 4, 2, 1, 0.5, 0.25, 0.125, ...], и теперь весь powerset выходит на игру ...

Answer 2

Чтобы получить общую сумму (не составляющие ее элементы), этот алгоритм очень быстро даст ответ, когда ваши числа выдают избыточные суммы:

def commonSum(A,B):
    commonSet = set(A).intersection(B) # common values are common sums
    if commonSet: return min(commonSet)   

    maxSumA = sum([a for a in A if a>0] or [max(A)])
    maxSumB = sum([b for b in B if b>0] or [max(B)])
    minSumA = sum([a for a in A if a<0] or [min(A)])
    minSumB = sum([b for b in B if b<0] or [min(B)])
    if maxSumA < minSumB: return None # no possible common sums
    if maxSumB < minSumA: return None

    sumsA,sumsB   = set(),set()                 # sets of cumulative sums
    diffA,diffB   = set([sum(A)]),set([sum(B)]) # sets of cumulative differences from total
    iterA,iterB   = iter(sorted(A,key=abs)),iter(sorted(B,key=abs))
    valueA,valueB = next(iterA,None), next(iterB,None)
    while valueA is not None or valueB is not None: # traverse the two lists in parallel until a sum if found or both are exhausted
        if valueA is not None:            
            newSums  = [valueA+s for s in sumsA \
                        if valueA+s <= maxSumB and valueA+s not in sumsA] + [valueA]
            sumsA.update(newSums) # new sums formed by combining element with all current ones
            newDiffs = [d-valueA for d in diffA \
                        if d-valueA >= minSumB and d-valueA not in diffA]
            diffA.update(newDiffs) # new differences formed by combining current element with existing ones
            valueA = next(iterA,None)
        if valueB is not None:
            newSums = [valueB+s for s in sumsB \
                       if valueB+s <= maxSumA and valueB+s not in sumsB] + [valueB]
            sumsB.update(newSums) # new sums formed by combining element with all current ones
            newDiffs = [d-valueB for d in diffB \
                        if d-valueB >= minSumA and d-valueB not in diffB]
            diffB.update(newDiffs) # new differences formed by combining current element with existing ones
            valueB = next(iterB,None)
        commonSet = (diffA & diffB) | (sumsA & sumsB) # detect common sums
        if commonSet: return min(commonSet)

Результаты с использованием приведенного примера и случайныенаборы значений всегда хороши.

listA = [455, 698, 756, 3.56, -9]
listB = [526,55,943,156,531,304,618,911,598,498,268,926,899,898,131,966,303,936,509,67,976,639,74,935,23,226,422,280,64,975,583,596,583]

commonSum(listA,listB) # 446,  1.1 millisecond

listA = [ random.randint(-1000,1000)*2-1 for _ in range(50) ] # only odd numbers
listB = [ random.randint(-500,1500)*2 for _ in range(50) ]    # only even numbers

commonSum(listA,listB) # 0.1 to 2 milliseconds

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

Способ, которым это работает, заключается в постепенном построении наборов возможных сумм без дубликатов (в sumsA,sumsB),Это минимизирует размер списков для сравнения.Это позволяет более прямо определять общие суммы (установить пересечение sumsA & sumsB).Списки обрабатываются в порядке возрастания величины значения (абсолютного значения), так что меньшие дельты учитываются на ранних этапах и максимизируют шансы на достижение заданной суммы.Параллельно с кумулятивными суммами алгоритм проверяет кумулятивные различия, используя два других набора (diffA,diffB).Это сумма всех элементов минус элементы, обработанные до сих пор.Пересечение этих двух наборов (diffA & diffB) также способствует быстрому нахождению общей суммы.

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

Чтобы получить действительные комбинации чисел, можно использовать функцию commonSum (), чтобы уменьшить проблему до поиска комбинации элементов, которыепроизводит известную сумму в списке (также известную как Subset sum).Поскольку мы знаем, что в списке есть решение для анализа, подмножество обычно находится очень быстро.

Вот функция, которая находит элементы списка, которые складываются в известную сумму:

from itertools import combinations,islice
def findSum(S,A,sumA=None,maxSumA=None,minSumA=None,lenA=None,pairs=None):
    if sumA is None: # sort and prepare accumulators (once)
        A,lenA  = sorted(A),len(A)
        pairs   = dict()
        for a,b in combinations(reversed(A),2):  # a+b pairs with lowest a where a >= b
            if a+b == S: return [b,a]
            pairs[a+b] = [a,b] 
        sumA    = sum(A)
        maxSumA = sum([a for a in A if a>0] or [max(A)])
        minSumA = sum([a for a in A if a<0] or [min(A)])
    # exit conditions
    if lenA == 0: return None                    # no more elements to sum
    if S < minSumA or S > maxSumA: return None   # sum unreachable
    if sumA == S: return A[:lenA]                # all values form the sum
    if S in islice(A,lenA): return [S]           # sum is one of the values (avoids creating temp list)
    if lenA == 1: return None                    # if only one, it must be the one
    if S in pairs \
    and all(p<=a for p,a in zip(pairs[S],A[lenA-2:])): # quick pairs
        return pairs[S]
    if lenA == 2 : return None                   # if only two, pairs would catch it
    for a in islice(A,lenA):
        if S-a not in pairs: continue            # quick triples
        triple = sorted([a]+pairs[S-a])
        if all(triple.count(n)==A[:lenA].count(n) for n in triple):
            return triple
    if lenA == 3: return None
    # isolate maximum value, update accumulators
    maxA     = A[lenA-1]
    sumA    -= maxA
    maxSumA -= maxA
    minSumA -= min(0,maxA)
    if maxSumA <= 0: maxSumA = maxA
    # include max in result and recurse
    usingMax = findSum(S-maxA,A,sumA,maxSumA,minSumA,lenA-1,pairs)  
    if usingMax : return usingMax + [maxA]
    # exclude max from result and recurse
    return findSum(S,A,sumA,maxSumA,minSumA,lenA-1,pairs) 

Вы можете использовать эту функцию в исходных списках с результатом commonSum ():

s = commonSum(listA,listB)  # 446
r1 = findSum(s,listA)       # [-9, 455]
r2 = findSum(s,listB)       # [23, 55, 64, 304]

Эта функция findSum () отвечает за миллисекунду в этих простых случаях, но она также может иметь некоторые худшиеслучаи, которые занимают значительно больше времени.

Вы можете объединить две функции в одну:

def commonSumItems(A,B):
    s = commonSum(A,B)
    if s is None: return None
    sA = findSum(s,A)
    sB = findSum(s,B)
    return (s,sA,sB)

commonSumItems(listA,listB) 

# (446, [-9, 455], [23, 55, 64, 304])

Два алгоритма все еще имеют много места для дальнейшей оптимизации, но я считаю, что они достаточно быстры для большинстваварианты использования.

Потенциальные оптимизации:

• В commonSum () прекратите проверять уменьшающиеся суммы (diffA, diffB), когда обрабатывается половина элементов в списке.
• В commonSum () вычислите наименьшую разницу с ближайшим соседом для элементов в каждом списке и выполните сортировку, используя ее в качестве ключа
• В commonSumItems () получитеподмножества listA и listB обработаны до сих пор и используют их вместо целых списков при вызове findSum ()

EDIT

Я пытался разгадать монстрасписок, который я нашел в другом сообщении, но findSum () делал это недостаточно быстро.Поэтому я создал функцию для упрощения задачи, исключив комбинации элементов, которые не могли бы вывести по модулю целевую сумму.Это действительно помогло и позволило мне решить этот список монстров:

Вот эта функция (после упрощения вызывает findSum):

from collections import defaultdict
def findSum2(S,A,modSize=None):
    eligibleA = A.copy()
    for modSize in range(2,len(A)*2): # modulo sum sizes
        sumD = defaultdict(set)       # eligible number per modulo of sum
        for a in eligibleA:
            newD = [(a%modSize,[a])]  # new modulo sum candidates
            for d,ad in sumD.items():
                m = (a+d) % modSize
                newD.append((m,ad | set([a])))
            for m,ad in newD:         # merge new candidates to target modulos
                sumD[m].update(ad)
        targetModList = sumD[S % modSize] # keep only eligibles
        eligibleA = [ a for a in eligibleA if a in targetModList ]
    return findSum(S,eligibleA) # call original algorithm with "cleaned" list

Вот список "монстров", который я пытался решитьwith findSum:

targetB = 262988806539946324131984661067039976436265064677212251086885351040000
B = [116883914017753921836437627140906656193895584300983222705282378240000,
 65747201634986581032996165266759994109066266169303062771721337760000,
 42078209046391411861117545770726396229802410348353960173901656166400,
 29220978504438480459109406785226664048473896075245805676320594560000,
 21468474003260924418937523352411426647858372626711204170357987840000,
 16436800408746645258249041316689998527266566542325765692930334440000,
 12987101557528213537381958571211850688210620477887024745031375360000,
 10519552261597852965279386442681599057450602587088490043475414041600,
 8693844844295746252297013588993057072273225278585528961549928960000,
 7305244626109620114777351696306666012118474018811451419080148640000,
 6224587137040149683597270084426981690799173128454727836375984640000,
 5367118500815231104734380838102856661964593156677801042589496960000,
 4675356560710156873457505085636266247755823372039328908211295129600,
 4109200102186661314562260329172499631816641635581441423232583610000,
 3639983481521748430892521260443459881470796742937193786669693440000,
 3246775389382053384345489642802962672052655119471756186257843840000,
 2914003396564502206448583502127866774917064428556368433095682560000,
 2629888065399463241319846610670399764362650646772122510868853510400,
 2385386000362324935437502594712380738650930291856800463373109760000,
 2173461211073936563074253397248264268068306319646382240387482240000,
 1988573206351200938616141104476672789688204647842814753019927040000,
 1826311156527405028694337924076666503029618504702862854770037160000,
 1683128361855656474444701830829055849192096413934158406956066246656,
 1556146784260037420899317521106745422699793282113681959093996160000,
 1443011284169801504153550952356872298690068941987447193892375040000,
 1341779625203807776183595209525714165491148289169450260647374240000,
 1250838556670374906691960338012080744048823137584838292922165760000,
 1168839140177539218364376271409066561938955843009832227052823782400,
 1094646437211014876720019400903392201607763016346356924399106560000,
 1027300025546665328640565082293124907954160408895360355808145902500,
 965982760477305139144112620999228563585913919842836551283325440000,
 909995870380437107723130315110864970367699185734298446667423360000,
 858738960130436976757500934096457065914334905068448166814319513600,
 811693847345513346086372410700740668013163779867939046564460960000,
 768411414287644482489363509326632509674989232073666182868912640000,
 728500849141125551612145875531966693729266107139092108273920640000,
 691620793004461075955252231602997965644352569828303092930664960000,
 657472016349865810329961652667599941090662661693030627717213377600,
 625791330255672395317036671188673352614551016483550865168079360000,
 596346500090581233859375648678095184662732572964200115843277440000,
 568931977371436071675467087219123799753953628290345594563299840000,
 543365302768484140768563349312066067017076579911595560096870560000,
 519484062301128541495278342848474027528424819115480989801255014400,
 497143301587800234654035276119168197422051161960703688254981760000,
 476213321032044045508347054897310957784092466595223632570186240000,
 456577789131851257173584481019166625757404626175715713692509290000,
 438132122515529069774235170457376054037925971973698044293020160000,
 420782090463914118611175457707263962298024103483539601739016561664,
 404442609057972047876946806715939986830088526993021531852188160000,
 389036696065009355224829380276686355674948320528420489773499040000,
 374494562534633427030238036407319297168052779889230688624970240000,
 360752821042450376038387738089218074672517235496861798473093760000,
 347753793771829850091880543559722282890929011143421158461997158400,
 335444906300951944045898802381428541372787072292362565161843560000,
 323778155173833578494287055791985197213007158728485381455075840000,
 312709639167593726672990084503020186012205784396209573230541440000,
 302199145693704480473409550206308504954053507241841138853071360000,
 292209785044384804591094067852266640484738960752458056763205945600,
 282707666261699891568916593460940582033071824431295083135592960000,
 273661609302753719180004850225848050401940754086589231099776640000,
 265042888929147215048611399412486748738992254650755607041456640000,
 256825006386666332160141270573281226988540102223840088952036475625,
 248983485481605987343890803377079267631966925138189113455039385600,
 241495690119326284786028155249807140896478479960709137820831360000,
 234340660761814501342824380545368657996226388663143017230461440000,
 227498967595109276930782578777716242591924796433574611666855840000,
 220952578483466770957349011608519198854244960871423861446658560000,
 214684740032609244189375233524114266478583726267112041703579878400,
 208679870295533683104133831435857945991878646837700655494453760000,
 202923461836378336521593102675185167003290944966984761641115240000,
 197401994025105141026072179446079922264038329650750423033879040000,
 192102853571911120622340877331658127418747308018416545717228160000,
 187014262428406274938300203425450649910232934881573156328451805184,
 182125212285281387903036468882991673432316526784773027068480160000,
 177425404985627474536673746714144021883127046501745489011223040000,
 172905198251115268988813057900749491411088142457075773232666240000,
 168555556186474170249629649778586749838977769381324948621621760000,
 164368004087466452582490413166899985272665665423257656929303344400]

Он находит решение менее чем за секунду:

 findSum2(targetB,B) # 0.3 second

 [202923461836378336521593102675185167003290944966984761641115240000,
  292209785044384804591094067852266640484738960752458056763205945600,
  335444906300951944045898802381428541372787072292362565161843560000,
  519484062301128541495278342848474027528424819115480989801255014400,
  657472016349865810329961652667599941090662661693030627717213377600,
  811693847345513346086372410700740668013163779867939046564460960000,
  858738960130436976757500934096457065914334905068448166814319513600,
  1168839140177539218364376271409066561938955843009832227052823782400,
  1826311156527405028694337924076666503029618504702862854770037160000,
  2385386000362324935437502594712380738650930291856800463373109760000, 
  29220978504438480459109406785226664048473896075245805676320594560000,
  42078209046391411861117545770726396229802410348353960173901656166400,
  65747201634986581032996165266759994109066266169303062771721337760000,
  116883914017753921836437627140906656193895584300983222705282378240000]     

EDIT2

Для некоторых данных полезно попробовать подмножества элементов списка, сгруппированных по общему gcd (наибольшему общему знаменателю), который они имеют с целевой суммой.Идея заключается в том, что элементы в списке, кратные некоторому значению K, всегда будут объединяться, чтобы сформировать кратное число K. Если целью является кратное K, все остальные элементы в списке (которые не являются кратными K) будет только мешать.Это позволяет реализовать стратегию, в которой мы сначала рассматриваем более простое решение, использующее меньше элементов и только два варианта, прежде чем переходить к большему числу комбинаций.Вот почему функция сначала пробует самые большие делители.

Мне удалось найти решение для вашего последнего списка, используя этот подход (в сочетании с предыдущей логикой): примечание: это заменяет findSum2 ()

from math import gcd
from itertools import combinations
def gcdSubSum(S,A):
    divs   = set( gcd(a,S) for a in A if isinstance(a,int)).difference([1])
    prevDivs = set()
    while prevDivs != divs:
        prevDivs = divs
        for a,b in combinations(divs,2):
            g = gcd(a,b)
            if g == 1 : continue
            divs.discard(a)
            divs.discard(b)
            divs.add(g)
    divs   = sorted(divs,reverse=True)
    combos = sorted(combinations(divs,2),key=lambda a:-min(a))
    for divCombo in combos:
        subA = [ a for a in A if any(a%d==0 for d in divCombo) ]
        result  = findSum(S,subA)
        if result is not None:return result
    return findSum(S,A)

C = [11000,11000,11000,1500,58272,76000,260669,2881,-3472,1591460,633959, 
 1298377,897946,1912536,35166,46888,46888,65190,16000,80000,-9175476,
 51950,-51950,428546,1693196,-18378,-9800,-18820,-3087,3087,30000,
 18378,18820,9800]
targetC = 290670

gcdSubSum(targetC,C) # 0.9 second

# [-51950, -9800, 11000, 11000, 11000, 16000, 18378, 18820, 51950, 58272, 76000, 80000]

Этот новый подход даже смог решить некоторые намеренно сложные контрольные примеры, которые я создал.

# Needs to combine 530 elements out of 1280 to reach the target:

targetD = 123456
D = [2**i for i in range(10)]*128 
gcdSubSum(targetD,D)                # 0.1 second


# must use several negatives to fill gap between a single 
# larger positive number an insufficient other positive 
# (52 out of 123).

targetE = 123456
E = [2**i for i in range(6,16)] + [1-2**i for i in range(1,15)]*8 + [2**18]
gcdSubSum(targetE,E)       # 10 seconds !!!

# [ -16383, -16383, -16383, -16383, -16383, -16383, -16383, -16383,
#   -4095, -4095, -4095, -4095, -4095, -4095, -4095, -4095, -1023,
#   -1023, -1023, -1023, -1023, -1023, -1023, -1023, -255, -255,
#   -255, -255, -255, -255, -255, -255, -63, -63, -63, -63, -63,
#   -63, -63, -15, -3, -3, -3, -3, -3, -3, -3, -3,
#   1024, 2048, 32768, 262144]

EDIT3 итерации по суммам ...

Поиск всех наборов подсумок не будет работать с этими алгоритмами, поскольку они оптимизированы для поиска ОДНОГО решения.Чтобы сгенерировать все подмножества, мне пришлось по-другому подойти к проблеме.Эта новая функция является генератором и иногда дает первое решение быстрее, чем gcdSubSum ().У него есть ограничение: он работает только с целочисленными значениями.Но вы можете обойти эту проблему, умножив все элементы и сумму на большое число, чтобы сделать их целыми, и разделите результат после этого:

def iSubSum(S,A,maxSize=None,sumA=None, oddCount=None):
    if maxSize is None: maxSize = len(A)
    if maxSize==0 or not A : return
    seen = set()        
    def newResult(result): # ensure distinct results
        result = sorted(result)
        return None if tuple(result) in seen else result            
    def addResult(result):
        if result: seen.add(tuple(result))

    if sumA     is None: sumA = sum(A)
    if oddCount is None: oddCount = sum(a&1 for a in A)
    if len(A) > maxSize:
        sA  = sorted(A)
        maxSumA  = sum([a for a in sA[-maxSize:] if a>0] or [max(A)])
        minSumA  = sum([a for a in sA[:maxSize]  if a<0] or [min(A)])
    else:
        maxSumA  = sum([a for a in A if a>0] or [max(A)])
        minSumA  = sum([a for a in A if a<0] or [min(A)])

    if S < minSumA or S > maxSumA: return      # sum unreachable
    if sumA == S and len(A)<=maxSize :
        yield A                                # all values form the sum
        addResult(sorted(A))
    elif  S in A  :
        yield [S]                              # one of the items is the sum
        addResult([S])
    if len(A) == 1 or maxSize==1: return       # if only one, we're done
    if S&1 and not oddCount: return            # need at least one odd for odd sum

    # remove elements that are beyond target range
    mA = [a for a in A if (minSumA<=a or minSumA+a<=S) and (a>=0 or maxSumA+a>=S)]
    if len(mA) < len(A):
        for result in iSubSum(S,mA,maxSize): yield result
        return        

    # even target: process even elements (divide problem by 2)
    if S&1 == 0:
        evens = [a//2 for a in A if a&1 == 0]
        for result in iSubSum(S//2,evens,maxSize):
            result = newResult([r*2 for r in result])
            if result: yield result
            addResult(result)
        if oddCount < 2 : return # need 2+ odd elements for even sum               

    #process odd elements (recursing until only evens remains)
    subA     = A.copy()
    for index,item in enumerate(reversed(A),1-len(A)):
        if not item&1: continue
        del subA[-index]
        oddCount -= 1
        sumA     -= item
        for result in iSubSum(S-item,subA,maxSize-1,sumA,oddCount):
            result = newResult(result + [item])
            if result: yield result
            addResult(result)

Чтобы получить первое решение, вызовите iSubSum в пределах next ()функция:

next(iSubSum(targetA,A),None) # 1.869 sec. (SLOWER than gcdSubSum 0.042)
next(iSubSum(targetB,B),None) # too long   (SLOWER than gcdSubSum 0.252)
next(iSubSum(targetC,C),None) # 0.003 sec. (FASTER than gcdSumSum 0.936)
next(iSubSum(targetD,D),None) # 0.006 sec. (FASTER than gcdSubSum 0.113)
next(iSubSum(targetE,E),None) # 0.003 sec. (FASTER than gcdSubSum 10.34)

К сожалению, iSubSum () не работает хорошо в списке монстров (targetB / B), поэтому он все еще может использовать больше работы.

Чтобы получить все решения, вы можетеиспользуйте цикл for или создайте список:

for solution in iSubSum(446,listB): 
    print(solution) 

[64, 156, 226]
[23, 55, 64, 304]

solutions = list(iSubSum(targetC,C)) # 1.8 seconds
print(solutions) 

[-9800, 11000, 11000, 11000, 16000, 18378, 18820, 58272, 76000, 80000]
[-51950, -9800, 11000, 11000, 11000, 16000, 18378, 18820, 51950, 58272, 76000, 80000]
[-51950, -9800, -3472, 1500, 11000, 11000, 16000, 18378, 18820, 35166, 46888, 51950, 65190, 80000]
[-51950, -18820, -9800, -3472, 1500, 9800, 11000, 11000, 11000, 18378, 18820, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -18820, -3472, 1500, 11000, 11000, 11000, 18378, 18820, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -9800, -3472, 1500, 9800, 11000, 11000, 11000, 18378, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -3472, 1500, 11000, 11000, 11000, 18378, 30000, 35166, 46888, 46888, 58272, 76000]
[-9800, -3472, 1500, 11000, 11000, 16000, 18378, 18820, 35166, 46888, 65190, 80000]
[-18820, -18378, -9800, -3472, 11000, 11000, 16000, 30000, 51950, 65190, 76000, 80000]
[-9800, -3087, 3087, 11000, 11000, 11000, 16000, 18378, 18820, 58272, 76000, 80000]
[-51950, -9800, -3087, 3087, 11000, 11000, 11000, 16000, 18378, 18820, 51950, 58272, 76000, 80000]
[-51950, -9800, -3472, -3087, 1500, 3087, 11000, 11000, 16000, 18378, 18820, 35166, 46888, 51950, 65190, 80000]
[-51950, -18820, -9800, -3472, -3087, 1500, 3087, 9800, 11000, 11000, 11000, 18378, 18820, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -18820, -3472, -3087, 1500, 3087, 11000, 11000, 11000, 18378, 18820, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -9800, -3472, -3087, 1500, 3087, 9800, 11000, 11000, 11000, 18378, 30000, 35166, 46888, 46888, 58272, 76000]
[-51950, -3472, -3087, 1500, 3087, 11000, 11000, 11000, 18378, 30000, 35166, 46888, 46888, 58272, 76000]
[-9800, -3472, -3087, 1500, 3087, 11000, 11000, 16000, 18378, 18820, 35166, 46888, 65190, 80000]
[-18820, -18378, -9800, -3472, -3087, 3087, 11000, 11000, 16000, 30000, 51950, 65190, 76000, 80000]
[-51950, -18820, -18378, -9800, -3087, 1500, 2881, 3087, 11000, 18378, 30000, 65190, 260669]
[-51950, -18820, -9800, -3087, 1500, 2881, 3087, 11000, 30000, 65190, 260669]
[-9800, -3472, 2881, 3087, 11000, 18378, 18820, 46888, 46888, 76000, 80000]
[-51950, -18378, -9800, 1500, 2881, 3087, 11000, 11000, 18378, 18820, 30000, 35166, 46888, 46888, 65190, 80000]
[-18820, -18378, -3472, 2881, 3087, 9800, 11000, 11000, 18378, 35166, 46888, 51950, 65190, 76000]
[-51950, -9800, -3472, 2881, 3087, 11000, 18378, 18820, 46888, 46888, 51950, 76000, 80000]
[-51950, -18820, -18378, -9800, 1500, 2881, 3087, 9800, 16000, 30000, 46888, 58272, 65190, 76000, 80000]
[-51950, -18820, -18378, 1500, 2881, 3087, 16000, 30000, 46888, 58272, 65190, 76000, 80000]
[-51950, -9800, 1500, 2881, 3087, 11000, 11000, 18820, 30000, 35166, 46888, 46888, 65190, 80000]
[-18820, -3472, 2881, 3087, 9800, 11000, 11000, 35166, 46888, 51950, 65190, 76000]
[-18378, -9800, -3472, -3087, 1500, 2881, 9800, 18378, 18820, 30000, 46888, 51950, 65190, 80000]
[-18378, -3472, -3087, 1500, 2881, 18378, 18820, 30000, 46888, 51950, 65190, 80000]
[-18378, -9800, -3472, -3087, 2881, 9800, 11000, 46888, 46888, 51950, 76000, 80000]
[-18378, -3472, -3087, 2881, 11000, 46888, 46888, 51950, 76000, 80000]
[-18820, -18378, -9800, -3472, -3087, 2881, 9800, 11000, 18820, 46888, 46888, 51950, 76000, 80000]
[-18820, -18378, -3472, -3087, 2881, 11000, 18820, 46888, 46888, 51950, 76000, 80000]
[-9800, -3472, -3087, 1500, 2881, 9800, 18820, 30000, 46888, 51950, 65190, 80000]
[-3472, -3087, 1500, 2881, 18820, 30000, 46888, 51950, 65190, 80000]
[-51950, -18820, -18378, -9800, 1500, 2881, 11000, 18378, 30000, 65190, 260669]
[-51950, -18820, -9800, 1500, 2881, 11000, 30000, 65190, 260669]

EDIT4 дубликаты и индексы

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

from itertools import product
from collections import defaultdict
def comboIndexes(A,R): # return indexes conbinations in A matching values in R
    idx = defaultdict(list)
    for i,a in enumerate(A): idx[a].append(i)
    return set(tuple(sorted(combo)) for combo in product(*[idx[r] for r in R]) if len(combo)==len(set(combo)))

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

Например:

listC = [10,10,40,40,40,50]
for solution in iSubSum(100,listC):
    for indexes in comboIndexes(listC,solution):
        print(indexes,solution)

(0, 4, 5) [10, 40, 50]
(0, 3, 5) [10, 40, 50]
(1, 4, 5) [10, 40, 50]
(1, 3, 5) [10, 40, 50]
(0, 2, 5) [10, 40, 50]
(1, 2, 5) [10, 40, 50]
(0, 1, 2, 4) [10, 10, 40, 40]
(0, 1, 3, 4) [10, 10, 40, 40]
(0, 1, 2, 3) [10, 10, 40, 40]

EDIT5 с использованием iSubSum для вычисления общей суммы между двумя списками

В большинстве ситуаций было бы возможно использовать iSubSum в качестве механизмаполучить общие суммы между двумя списками (оригинальный вопрос).Подход состоит в том, чтобы сделать один список из двух списков, но инвертировать один из двух списков.Если есть общие суммы, то объединенный список должен быть в состоянии сформировать сумму нуля.

Вот пример:

def iCommonSum(A,B):
    if any( -a in B for a in A):
        return None # value conflict (algorithm TBD)
    for solution in iSubSum(0,[-a for a in A]+B):
        sA = [-a for a in solution if -a in A]
        sB = [b for b in solution if b in B]
        yield sA,sB

listA = [455, 698, 756, 3,56, -9]
listB = [526,55,943,156,531,304,618,911,598,498,268,926,899,898,131,966,303,936,509,67,976,639,74,935,23,226,422,280,64,975,583,596,583]

for sA,sB in iCommonSum(listA,listB):
    print(sum(sA),sA,sB)

1454 [756, 698] [226, 280, 422, 526]
1454 [756, 698] [74, 156, 304, 422, 498]
1510 [756, 698, 56] [64, 74, 156, 268, 422, 526]
1510 [756, 698, 56] [64, 422, 498, 526]
1454 [756, 698] [156, 280, 422, 596]
754 [698, 56] [64, 268, 422]
1510 [756, 698, 56] [64, 74, 226, 268, 280, 598]
...

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

Создание версии iSubSum, которая возвращает индексы вместо значений, позволит устранить неоднозначность этой ситуации (продолжение следует в новом ответе).

Answer 3

Если вы все еще находитесь в регионе, где возможно создать полные наборы мощности (и нам не нужно пытаться обойти это), то вы можете просто отсортировать наборы электропитания (по значению их суммы) и сравнить их впорядок, так же, как в случае слияния.Это сократит время выполнения с O(2^N * 2*M) до O(2^N + 2^M), но это не очень удобно, но уменьшит эффективный размер проблемы с O(N+M) до O(max(N,M).

Answer 4

Основываясь на работе, проделанной в моем предыдущем ответе, это окончательное решение использует вариант функции суммы подмножеств (iSubSum), которая возвращает индексы, а не значения.Подход работает путем слияния двух списков после инвертирования элементов одного из них.Затем поиск нулевой суммы в объединенном списке приведет к созданию объединенного набора элементов, которые образуют общую сумму.Элементы, которые формируют эту нулевую сумму, могут затем быть разделены на основе их списка или происхождения.

Вот модифицированная версия iSubSum (), которая возвращает индексы (обратите внимание, что она обрабатывает только целые числа, но поддерживает и должна поддерживатьотрицательные числа):

def iSubSumIndexes(S,A,sumA=None, oddCount=None):
    if not A : return
    if not isinstance(A[0],tuple):
        A = [(a,i) for i,a in enumerate(A)]
    seen = set()        
    def newResult(result): # ensure distinct results
        result = sorted(result)
        return None if tuple(result) in seen else result            
    def addResult(result):
        if result: seen.add(tuple(result))

    if sumA     is None: sumA = sum(a for a,i in A)
    if oddCount is None: oddCount = sum(a&1 for a,i in A)
    maxSumA  = sum([a for a,i in A if a>0] or [max(A)[0]])
    minSumA  = sum([a for a,i in A if a<0] or [min(A)[0]])

    if S < minSumA or S > maxSumA: return      # sum unreachable
    if sumA == S:
        result = newResult([i for a,i in A])
        yield result                           # all values form the sum
        addResult(result)
    else:
        for a,i in A:
            if a != S: continue
            yield [i]                          # one of the items is the sum
            addResult([i])
    if len(A) == 1: return                     # if only one, we're done
    if S&1 and not oddCount: return            # need at least one odd for odd sum

    # remove elements that are beyond target range
    mA = [(a,i) for a,i in A if (minSumA<=a or minSumA+a<=S) and (a>=0 or maxSumA+a>=S)]
    if len(mA) < len(A):
        for result in iSubSumIndexes(S,mA): yield result
        return        

    # even target: process even elements (divide problem by 2)
    if S&1 == 0:
        evens = [(a//2,i) for a,i in A if not a&1]
        for result in iSubSumIndexes(S//2,evens):
            result = newResult(result)
            if result: yield result
            addResult(result)
        if oddCount < 2 : return # need 2+ odd elements for even sum               

    #process odd elements (recursing until only evens remains)
    subA     = A.copy()
    for index,(odd,oddIndex) in enumerate(reversed(A),1-len(A)):
        if not odd&1: continue
        del subA[-index]
        oddCount -= 1
        sumA     -= odd
        for result in iSubSumIndexes(S-odd,subA,sumA,oddCount):
            result = newResult(result + [oddIndex])
            if result: yield result
            addResult(result)

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

def iCommonSumIndexes(A,B):
    for solution in iSubSumIndexes(0,[-a for a in A]+B):
        iA = [i for i in solution if i < len(A)]
        iB = [i-len(A) for i in solution if i >= len(A)]
        yield iA,iB

Чтобы использовать это, вам нужно будет обрабатывать индексы из выходных данных, а не фактические значения, но этопростое косвенное обращение легко сделать в понимании списка.Дополнительным преимуществом является то, что вы можете использовать индексы для отображения более сложных объектов, которые содержат значения (например, учетные транзакции):

listA = [455, 698, 756, 3,56, -9]
listB = [526,55,943,156,531,304,618,911,598,498,268,926,899,898,131,966,303,936,509,67,976,639,74,935,23,226,422,280,64,975,583,596,583]

for iA,iB in iCommonSumIndexes(listA,listB):
    sA = [listA[i] for i in iA]
    sB = [listB[i] for i in iB]
    print(sum(sA),sA,sB)

1454 [698, 756] [526, 226, 422, 280]
1454 [698, 756] [156, 304, 498, 74, 422]
1510 [698, 756, 56] [526, 156, 268, 74, 422, 64]
1510 [698, 756, 56] [526, 498, 422, 64]
1454 [698, 756] [156, 422, 280, 596]
754 [698, 56] [268, 422, 64]
1510 [698, 756, 56] [598, 268, 74, 226, 280, 64]
1510 [698, 756, 56] [156, 618, 598, 74, 64]
756 [756] [618, 74, 64]
...

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

Вы можете отфильтровать выходные данные, если хотите только:

• уникальные комбинации значений
• различные левые / правые шаблоны
• непустые подмножества.

Производительность определяется алгоритмом iSubSumIndexes, который, как правило, довольно быстрый, но имеет своиограничения.

Если вы найдете лучший алгоритм подмножества сумм, который можно адаптировать для возврата индексов, тот же подход также сработает (заменив iSubSumIndexes в iCommonSumIndexes лучшей функцией).Другими словами, проблема общей суммы может быть сведена к более общей проблеме подмножества.

РЕДАКТИРОВАТЬ Улучшенная версия iSubSumIndexes

Вот улучшенная версия функцииэто расширяет его четное / нечетное понятие на простые факторы.В этом расширенном представлении понятие «четный» соответствует числу, кратному основному простому числу.Понятие "нечетный" - это любое не кратное этому основному простому числу.Как и в случае четных / нечетных вычислений, добавление «четных» значений всегда приводит к «четным» результатам.Кроме того, как минимум два «нечетных» значения должны быть добавлены вместе, чтобы получить «четный» результат.В случае этих «шансов» на основе простых чисел может потребоваться более двух, но это не относится к алгоритму.

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

def iSubSumIndexes(S,A):

    if not A : return
    if not isinstance(A[0],tuple):
        A = [(a,i) for i,a in enumerate(A)]
    seen = set()        
    def newResult(result): # ensure distinct results
        result = sorted(result)
        return None if tuple(result) in seen else result            
    def addResult(result):
        if result: seen.add(tuple(result))

    sumA     = sum(a for a,i in A)
    maxSumA  = sum([a for a,i in A if a>0] or [max(A)[0]])
    minSumA  = sum([a for a,i in A if a<0] or [min(A)[0]])

    if S < minSumA or S > maxSumA: return      # sum unreachable
    if sumA == S:
        result = sorted(i for a,i in A)
        yield result                           # all values form the sum
        addResult(result)
    else:
        for a,i in A:
            if a == S: 
               yield [i]                       # one of the items is the sum
               addResult([i])
    if len(A) == 1: return                     # if only one, we're done

    # remove elements that are beyond target range
    mA = [(a,i) for a,i in A if (minSumA<=a or minSumA+a<=S) and (a>=0 or maxSumA+a>=S)]
    if len(mA) < len(A):
        for result in iSubSumIndexes(S,mA): yield result
        return

    # Apply even/odd concept to prime factors       
    for f in [19,17,13,11,7,5,3,2]:
        oddCount = sum(a%f != 0 for a,i in A)
        if S%f and not oddCount: return # need at least one odd for odd sum
        if f > 2 and oddCount > 1:
           if oddCount > len(A)//2: continue

        # even target: process even elements (divide problem by f)
        if S%f == 0:
            evens = [(a//f,i) for a,i in A if  a%f == 0]
            for result in iSubSumIndexes(S//f,evens):
                result = newResult(result)
                if result: yield result
                addResult(result)
            if oddCount < 2 : return # need 2+ odd elements for even sum               

        #process odd elements (recursing until only evens remains)
        subA     = A.copy()
        for index,(item,ii) in enumerate(reversed(A),1-len(A)):
            if item%f == 0: continue
            del subA[-index]
            for result in iSubSumIndexes(S-item,subA):
                result = newResult(result + [ii])
                if result: yield result
                addResult(result)
        break

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

Answer 5

Не уверен, что вы все еще ищете ответ, но вы действительно можете расширить подход к замене монет, который вы применили для своих вариантов 2 и 3, упомянутых в ОП. Идея здесь состоит в том, чтобы использовать таблицу памятки, которую вы создаете в подходе динамического программирования. Обратите внимание, что вам нужно иметь положительные числа (могут быть числами с плавающей точкой) в обоих массивах, чтобы получить здесь наилучшее возможное решение.

Рассмотрим два массива: [4,3,5,1] и [2,6,4,3]

Позволяет создать таблицу напоминаний для первого массива, используя подход с изменением монеты, где максимальная сумма, которую вы хотите, представляет собой сумму всех элементов массива, которая в данном случае равна 13. Таблица памятки выглядит следующим образом:

    0   1   2   3   4   5   6   7   8   9   10  11  12  13
4   T   F   F   F   T   F   F   F   F   F   F   F   F   F
3   T   F   F   T   T   F   F   T   F   F   F   F   F   F
5   T   F   F   T   T   T   F   T   T   T   F   F   T   F
1   T   T   F   T   T   T   T   T   T   T   T   F   T   T

Для второго массива общая сумма равна 15, и таблица выглядит так:

    0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
2   T   F   T   F   F   F   F   F   F   F   F   F   F   F   F   F
6   T   F   T   F   F   F   T   F   T   F   F   F   F   F   F   F
4   T   F   T   F   T   F   T   F   T   F   T   F   T   F   F   F
3   T   F   T   T   T   T   T   T   T   T   T   T   T   T   F   T

Если вы видите последнюю строку обеих таблиц, вы можете легко заключить, что какой бы столбец не имел значения как T, этот конкретный номер столбца может быть выражен как сумма некоторых элементов в данном массиве. И как вы находите эти элементы? Вы просто возвращаетесь в существующую таблицу напоминаний для всех возможных способов получить конкретную сумму столбца. Начните с последней строки для любого столбца, значение ячейки которого равно T. Затем вы можете вернуться, используя для всех значений T для этого конкретного столбца и соответствующим образом корректируя свою сумму.

Теперь перейдем к основной части, чтобы узнать, какая подпоследовательность дает вам такую ​​же сумму. Случай 4 из ОП. Итак, после того, как вы сформировали вышеуказанные подпоследовательности для всех возможных сумм с использованием последней строки, вы можете просто сравнить последнюю строку обеих таблиц запоминания, столбец за столбцом, чтобы найти, какие суммы фактически сформированы в обоих массивах, и вернуть соответствующие подпоследовательности. хранится против этих сумм. Например, в этом случае для данных двух массивов общие суммы, образованные двумя вышеупомянутыми элементами массива, будут [3,4,5,6,7,8,9,10,12,13], и, используя подход, описанный выше, вы можете сопоставить эти суммы со списком массивов, дающих эти суммы, и, следовательно, вернуть эти массивы как результат .

Сложность времени в этом будет O(n1*s1 + n2*s2) где ni и si - это число и сумма элементов в массиве ai, так как я думаю, что вы можете расширить этот подход и для k заданных массивов.

Пожалуйста, дайте мне знать, если кто-нибудь найдет здесь какой-либо недостаток.