Divide an array into k parts to minimize the difference between (max of each part * num of elements)

userBMSg1 0
Viewed 32

Given an array arr and a partition value k, I need to divide it into k parts such that the difference between the product of maximum value of each part times number of values in each part is minimized.

For example:

arr = [5,6,7,8,9,1,2,3,4]

k = 3

Dividing the above array into 3 parts producing the desired result is:

[[1,2,3,4],[5,6,7],[8,9]]

[1,2,3,4] = max([[1,2,3,4]) * 4 = 16

[5,6,7] = max([5,6,7]) * 3 = 21

[8,9] = max([8,9]) * 2 = 18

The max difference in this partition is 21-16 = 5. This is the "least" difference I can get partitioning them.

data-structures dynamic-programming arrays algorithm python
1 Answers

First thing we need to do is figure out how to split the list into partitions.

To get all of the ways we can split the list into k sections, we can start by determine all of the ways k numbers can add up to len(arr), where each number is greater than 1.

To do so we can take advantage of itertools.

def partition_index(a, k):
    for indices in product(range(1, len(a)), repeat=k):
        if sum(indices) == len(a):
            yield indices

for s in partition_index([9, 1, 2, 3, 4], 3):
    print(s)

(1, 1, 3)
(1, 2, 2)
(1, 3, 1)
(2, 1, 2)
(2, 2, 1)
(3, 1, 1)

Perfect! Now if we want to split our array based on these values, it'll be easier if we turn them into tuples for the start and end of where to split. For this we can use itertools again!

def partition_index(a, k):
    for indices in product(range(1, len(a)), repeat=k):
        if sum(indices) == len(a):
            yield list(pairwise([0, *accumulate(indices)]))

[(0, 1), (1, 2), (2, 5)]
[(0, 1), (1, 3), (3, 5)]
[(0, 1), (1, 4), (4, 5)]
[(0, 2), (2, 3), (3, 5)]
[(0, 2), (2, 4), (4, 5)]
[(0, 3), (3, 4), (4, 5)]

Now that we have this grouping, creating a method to do the partition is pretty straight forward:

def partition(a, k):
    for indices in partition_index(a, k):
        yield [a[i:j] for i, j in indices]

[[9], [1], [2, 3, 4]]
[[9], [1, 2], [3, 4]]
[[9], [1, 2, 3], [4]]
[[9, 1], [2], [3, 4]]
[[9, 1], [2, 3], [4]]
[[9, 1, 2], [3], [4]]

And finally we can use this output to get your desired results.

def minimized_difference(a, k):
    final_diff, final_result = None, None

    for result in partition(a, k):
        result_max = [max(r) * len(r) for r in result]
        diff = max(result_max) - min(result_max)

        if final_diff is None or diff < final_diff:
            final_diff, final_result = diff, result

    return final_result


print(minimized_difference([5, 6, 7, 8, 9, 1, 2, 3, 4], 3))

[[5, 6, 7], [8, 9], [1, 2, 3, 4]]

Final code with some refactoring and covering corner cases:

from itertools import pairwise, product, accumulate
from typing import TypeVar, Iterable, Optional

T = TypeVar('T')


def partition_index(size: int, k: int) -> Iterable[list[tuple[int, int]]]:
    for indices in product(range(1, size - k + 2), repeat=k):
        if sum(indices) == size:
            yield list(pairwise([0, *accumulate(indices)]))


def partition(data: list[T], k: int) -> Iterable[list[list[T]]]:
    if len(data) < k or k <= 0:
        return
    for indices in partition_index(len(data), k):
        yield [data[i:j] for i, j in indices]


def evaluate_result(result: list[list[T]]) -> int:
    result_max = [max(r) * len(r) for r in result]
    return max(result_max) - min(result_max)


def minimized_difference(data: list[int], k: int) -> Optional[list[list[int]]]:
    return min(partition(data, k), default=None, key=evaluate_result)


print(minimized_difference([5, 6, 7, 8, 9, 1, 2, 3, 4], 3))
flakes0
Related