reduced stack

 avatar
user_8886827
python
a month ago
1.5 kB
1
Indexable
Never
def reduced_sets(arr):
    n = len(arr)
    result = []
    for i in range(n):
        for j in range(i + 1, n):
            sum_pair = arr[i] + arr[j]
            remaining = [num for k, num in enumerate(arr) if k != i and k != j]
            new_combination = remaining + [sum_pair]
            new_combination.sort()
            if new_combination not in result:
                result.append(new_combination)
    return result + [arr]

def powerset(comb):
    result = [[]]
    for element in comb:
        new_subsets = []
        for subset in result:
            new_subsets.append(subset + [element])
        result.extend(new_subsets)
    return result

def is_comb_valid(comb, n):
    nums = [i for i in range(5, n+5, 5)]
    for num in nums:
        flag = False
        for subset in powerset(comb):
            if sum(subset) == num:
                flag = True
                break
        if flag is False:
            return False
    return True

n = 40
result = [5]
for i in range(5, n+5, 5):
    if is_comb_valid(result, i) is True:
        continue
    result.append(5)
    possible_combs = reduced_sets(result)
    print(f"reduced stack for {i} is {possible_combs}")
    for comb in possible_combs:
        valid_combs = []
        if is_comb_valid(comb, i):
            valid_combs.append(comb)
            best_picks = sorted(valid_combs, key=lambda x: (len(x), x))
            print(f"best picks for {i} is {best_picks}")
            break    
    result = valid_combs[0]
Leave a Comment