Maximale Kombination für eine bestimmte Liste
Posted: 03 Jan 2025, 18:43
Ich brauche einen Assistenten, der die folgende Frage in Python implementiert.
Es gibt eine vorgegebene Liste:
Die Anforderung besteht darin, einen Python-Code zu schreiben, der die maximale Anzahl von Gruppen mit der Summe von 6 erhält.
Dies sind die möglichen Kombinationen:
Die maximale Anzahl an Kombinationen beträgt 3.
Wenn eine Zahl in einer Kombinationsgruppe verwendet wurde, kann sie nicht noch einmal verwendet werden.
z.B. Wenn die Zahl „4“ in [1, 1, 4] verwendet wird, kann sie nicht erneut in einer anderen Kombination [4, 2] verwendet werden (es sei denn, sie erscheint zweimal in der Eingabeliste).
Wenn möglich, würde ich gerne wissen, wie ich es lösen kann, um die Kombinationen selbst zu erhalten (auch bis zur maximalen Anzahl).
Ich habe etwas geschrieben, aber ist im Hinblick auf die zeitliche Komplexität äußerst ineffizient.
Es gibt eine vorgegebene Liste:
Code: Select all
nums = [1, 1, 4, 2, 3, 3, 2, 5]Dies sind die möglichen Kombinationen:
Code: Select all
[[[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]]] Wenn eine Zahl in einer Kombinationsgruppe verwendet wurde, kann sie nicht noch einmal verwendet werden.
z.B. Wenn die Zahl „4“ in [1, 1, 4] verwendet wird, kann sie nicht erneut in einer anderen Kombination [4, 2] verwendet werden (es sei denn, sie erscheint zweimal in der Eingabeliste).
Wenn möglich, würde ich gerne wissen, wie ich es lösen kann, um die Kombinationen selbst zu erhalten (auch bis zur maximalen Anzahl).
Ich habe etwas geschrieben, aber ist im Hinblick auf die zeitliche Komplexität äußerst ineffizient.
Code: Select all
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))`