# Minimizing cost of a given sequence by creating partitons.

Given a sequence of positive integers of size N(let) divide it into at most K(K > N/C) disjoint parts/subsequences in order to minimize the "cost" of the entire sequence.

Partitions cannot overlap, for example [1,2,3,4,5] can be divided into [1,2], [3,4] and [5] but not [1,3] and [2,4,5].

The cost of a subsequence is computed as the number of repeated integers in it. The cost of the entire sequence is computed as the sum of costs of all the subsequences and a fixed positive integer cost C times the number of partitions/divisions of the original sequence.

How should I go about determining the position and number of partitions to minimize the total cost?

Some more examples:

The given list = [1,2,3,1] Without any partitions, its cost will be 2 + C, as 1 occurs two times and the original sequence is counted as one partition.

[1,1,2,1,2] Without any partitions, its cost will be 5, as 1 occurs three times and 2 occurs two times. If we divided the subsequence like so [1,1,2],[1,2] then the cost becomes 2 + 2*C, where C is the cost of partitioning.

I have actually solved the problem for the case of C = 1, but am having problems generalizing it to higher values of C.

For C = 1 it makes sense to partition the sequence while traversing it from one direction as soon as a repetition occurs as the cost of a single repetition is 2 whereas the cost of partitioning is 1.

• – D.W.
Commented Aug 12, 2020 at 6:20
• Can you credit the original source or context where you encountered this task?
– D.W.
Commented Aug 12, 2020 at 6:21

Let $$f(x_1, x_2, \dots, x_N)$$ denote the minimum cost of any partition of $$x_1, \dots, x_N$$; let $$f(x_1, x_2, \dots, x_N; \ell)$$ denote the minimum cost of a partition in which the last part has length $$\ell$$ (in other words, in which the last part is $$[x_{N-\ell+1}, \dots, x_N]$$.)
If we can compute $$f(x_1, x_2, \dots, x_N; \ell)$$ for all $$\ell=1,\dots,N$$, then $$f(x_1, x_2, \dots, x_N)$$ is just the minimum of those.
We can compute $$f(x_1, x_2, \dots, x_N; \ell)$$ for all $$\ell=1, \dots, N$$ at the same time recursively, in terms of $$f(x_1, x_2, \dots, x_{N-1}; \ell)$$. We have:
• $$f(x_1, x_2, \dots, x_N; 1) = f(x_1, x_2, \dots, x_{N-1}) + C$$.
• for $$\ell>1$$, $$f(x_1, x_2, \dots, x_N; \ell) = f(x_1, x_2, \dots, x_{N-1}; \ell-1)$$ if $$x_N \notin \{x_{N-\ell+1}, \dots, x_{N-1}\}$$.
• for $$\ell>1$$, $$f(x_1, x_2, \dots, x_N; \ell) = f(x_1, x_2, \dots, x_{N-1}; \ell-1) + 1$$ if $$x_N \in \{x_{N-\ell+1}, \dots, x_{N-1}\}$$.
If there is a limit $$K$$ to the number of parts, we would want to refine this function further; we could write $$f(x_1, x_2, \dots, x_N; \ell, k)$$ for the minimum cost of a partition in which the last part has length $$\ell$$ and there are $$k$$ parts total. The recurrence is similar, except with more values to keep track of and compute. But in your case, provided $$K > N/C$$, we don't need to do that; a solution with more than $$K$$ parts will have cost more than $$N$$, so it will never be optimal.