reduced stack
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