Sage codes

Before pruning - Initial algorithm

(Scroll down for iprovised code)

---

from itertools import combinations


numbers = [1245, 1675, 2345, 2879, 3456, 6578, 9987, 1092, 665, 
          4567, 7892, 4567]
k = int(input("Enter the number of parts"))

n = len(numbers)


def partitions_of_n(n, k, min_part=1):
    if k == 1:
        if n >= min_part:
            yield (n,)
        return
    for i in range(min_part, n - k + 2):
        for tail in partitions_of_n(n - i, k - 1, i):
            yield (i,) + tail


size_patterns = list(partitions_of_n(n, k))

best_diff = float('inf')
best_partition = None


def generate_groups(remaining, sizes):
    if len(sizes) == 1:
        yield [tuple(remaining)]
        return

    first_size = sizes[0]
    for group in combinations(remaining, first_size):
        new_remaining = list(remaining)
        for x in group:
            new_remaining.remove(x)
        for rest in generate_groups(new_remaining, sizes[1:]):
            yield [group] + rest


for pattern in size_patterns:
    for groups in generate_groups(numbers, pattern):
        sums = [sum(g) for g in groups]
        diff = max(sums) - min(sums)

        if diff < best_diff:
            best_diff = diff
            best_partition = groups


print("Optimal Partition:")
for i, group in enumerate(best_partition, 1):
    print(f"Group {i}: {group}, sum = {sum(group)}")

print("Minimal difference (max-min sum):", best_diff)

---

Improvised code

from itertools import combinations

numbers = [1245, 1675, 2345, 2879, 3456, 6578, 9987,
           1092, 665, 4567, 7892, 4567]
k = int(input("Enter the number of parts: "))

numbers = sorted(numbers, reverse=True)
n = len(numbers)

best_diff = float('inf')
best_partition = None


def partitions_of_n(n, k, min_part=1):
    if k == 1:
        if n >= min_part:
            yield (n,)
        return
    for i in range(min_part, n - k + 2):
        for tail in partitions_of_n(n - i, k - 1, i):
            yield (i,) + tail


size_patterns = list(partitions_of_n(n, k))


def generate_groups_bb(remaining, sizes, groups, sums, prev_group=None):
    global best_diff, best_partition

    if len(sizes) == 1:
        group = tuple(sorted(remaining))
        groups.append(group)
        sums.append(sum(group))

        diff = max(sums) - min(sums)
        if diff < best_diff:
            best_diff = diff
            best_partition = list(groups)

        groups.pop()
        sums.pop()
        return

    first_size = sizes[0]

    for group in combinations(remaining, first_size):
        group = tuple(sorted(group))

        # Symmetry pruning
        if prev_group is not None and first_size == len(prev_group):
            if group <= prev_group:
                continue

        group_sum = sum(group)

        # Branch-and-bound pruning
        new_sums = sums + [group_sum]
        if len(new_sums) > 1:
            if max(new_sums) - min(new_sums) >= best_diff:
                continue

        new_remaining = list(remaining)
        for x in group:
            new_remaining.remove(x)

        groups.append(group)
        sums.append(group_sum)

        generate_groups_bb(
            new_remaining,
            sizes[1:],
            groups,
            sums,
            group
        )

        groups.pop()
        sums.pop()


for pattern in size_patterns:
    generate_groups_bb(numbers, pattern, [], [], None)


print("\nOptimal Partition:")
for i, group in enumerate(best_partition, 1):
    print(f"Group {i}: {group}, sum = {sum(group)}")

print("Minimal difference (max-min sum):", best_diff)