给定列表的最大组合

Question

我需要助手用Python实现以下问题； 有一个给定的列表：

nums = [1, 1, 4, 2, 3, 3, 2, 5]

要求是编写一段 Python 代码，获取总和为 6 的最大组数。

这些是可能的组合：

[[[1, 1, 2, 2], [3, 3]], [[1, 1, 4], [3, 3]], [[1, 2, 3], [1, 5], [2, 4]], [[1, 5], [2, 4], [3, 3]], [[2, 4], [3, 3]], [[3, 3]]] 

最大组合数为 3。 如果一个号码在一组组合中使用过，则不能再次使用。 例如数字“4”如果在

[1, 1, 4]

中使用，则不能在其他组合中再次使用

[4, 2]

（除非它在输入列表中出现两次）。

如果可能的话，我很高兴知道如何解决它以获得组合本身（以及最大计数）。 我写了一些东西，但在时间复杂度方面效率极低。

def get_combination_groups(array: list, total_size: int) -> list:
    out = []
    array.sort()

    def dfs(arr, total, cur, have):
        if total == 0:
            out.append(cur.copy())
            return
        if total < 0 or len(arr) == 0:
            return
        prev = -1
        for i in range(len(arr)):
            n = arr[i]
            if prev == n:
                continue
            reminder = total - n
            cur.append(n)
            dfs(arr[i + 1:], reminder, cur, have)
            prev = n
            cur.pop()
    dfs(array, total_size, [], {})
    return out

def is_valid(remain: dict, count_b: dict) -> bool:
    for key in count_b:
        if not remain.get(key) >= count_b[key]:
            return False
    return True

def filter_result(result: list, arr: list) -> list:
    output = []
    start_count = Counter(arr)
    for i in range(len(result)):
        remain = start_count.copy()
        i_count = Counter(result[i])
        remain.subtract(i_count)
        out_tmp = [result[i]]
        for j in range(i + 1, len(result)):
            j_count = Counter(result[j])
            if is_valid(remain, j_count):
                out_tmp.extend([result[j]])
                remain.subtract(j_count)
        output.append(out_tmp)
    return output


nums = [1, 1, 4, 2, 3, 3, 2, 5]
total_sum = 6
res = get_combination_groups(nums, total_sum)
print(filter_result(res, nums))`  

Answer 1

一分钟解释...

import numpy as np
import itertools

###############################################################################

def combinationsWithGivenSum( L, s ):
    '''
    Returns a list of tuples, each containing the INDICES of
    elements of L that add up to s
    '''
    output = []
    n = len( L )
    iota = tuple( range( n ) )
    for length in range( 1, n + 1 ):
        for indices in itertools.combinations( iota, length ):
            if L[np.array(indices)].sum() == s: output.append( indices )
    return output

###############################################################################

def noIntersection( C, indices, nvals ):
    '''
    Function returns true if C[i] for i in indices gives no intersections
    where each C[i] contains a tuple of numbers
    '''
    taken = np.zeros( nvals )
    for i in indices:
        for x in C[i]:
            if taken[x] > 0: return False
            taken[x] = 1
    return True

###############################################################################
                   
def noOverlaps( C, nlist ):
    '''
    Find the longest collection in C with no overlaps over elements
    '''
    n = len( C )
    iota = tuple( range( n ) )
    for length in range( n-1, -1, -1 ):      # Efficiency - start with longest possible and work back
        for indices in itertools.combinations( iota, length ):
            if noIntersection( C, indices, nlist ):
                collections = []              
                for i in indices: collections.append( C[i] )
                return collections
    return []

###############################################################################

def best( A, s ):
    C = combinationsWithGivenSum( A, s )         # Get tuples with given sum
#   print( "C=", C )

    collections = noOverlaps( C, len( A ) )      # Longest collection of indices of C with no overlaps

    result = []
    for t in collections: result.append( [ int( A[x] ) for x in t ] )

    return result

###############################################################################

A = np.array( [1, 1, 4, 2, 3, 3, 2, 5] )
B = best( A, 6 )
print( "Maximum number of subpartitions = ", len( B ) )
print( "Example is ", B )

输出：

Maximum number of subpartitions =  3
Example is  [[1, 5], [4, 2], [3, 3]]