# Partition integers into $M$ sets

Given a circular list of two numbers $-1,+1$.I have to partition them into $M$ sets each containing $K$ numbers. Each set has to consist of consecutive $K$ numbers from that list. The set can start from any point in the list.

1.A set is called positive if number of $+1$ are greater than $-1$.

2.A set is called negative if number of $-1$ are greater than $+1$.

Now I want to know if there's a way to partition them such that the number of positive sets are more than number of negative sets.

Take $K$ to be odd for simplicity so that a set can be either called positive or negative.

For eg- List $A$ = $(-1, -1, 1, 1, -1, 1, 1, -1, -1)$ and I have to partition it into $3$ sets with $3$ numbers in it. Then there are many ways : 1. {$A_3$,$A_4$,$A_5$}, {$A_6$,$A_7$,$A_8$} and {$A_9$,$A_1$,$A_2$}

1. {$A_2$,$A_3$,$A_4$}, {$A_5$,$A_6$,$A_7$} and {$A_8$,$A_9$,$A_1$}

Here $2$ positive sets and $1$ negative set. So I can partition it.

I can only think of making every possible combination. Is there a way to do it efficiently and optimally.

• There are only $K$ such divisions, which is not much to check. – Simon Marynissen Feb 17 '17 at 15:23
• @SimonMarynissen How do you check it ? Can you explain it ? – Buckster Feb 17 '17 at 16:21
• Just making every possible combination, I can't think of a better way at the moment. – Simon Marynissen Feb 17 '17 at 16:24
• @SimonMarynissen This would take quadratic time. Not efficient at all. – Buckster Feb 17 '17 at 16:36
• That depends on whether $K$ is much smaller than $|M|$. – Simon Marynissen Feb 17 '17 at 16:39

## 1 Answer

Let $N=KM$. Let $S_i = A_i+\ldots +A_{i+K-1}$, $A_{N+i}=A_{i}$. Obviously, $\{A_i,\ldots ,A_{i+K-1}\}$ is positive if $S_i$ is positive, and $\{A_i,\ldots ,A_{i+K-1}\}$ is negative if $S_i$ is negative.

The $S_i$ can be calculated recursively with little effort: $$S_{i+1} = S_i+A_{i+K}-A_{i}$$ For each $j\in \{0,\ldots ,K-1\}$, introduce a counter $p_j$ ("positive") and an counter $n_j$ ("negative").

Start with initializing your counters and calculating $S_1$. Then calculate each $S_i, \; i=1,\ldots, N$ with the recursive formula shown above. If $S_i >0$, increase the $p_j$ for which $j\equiv i\pmod{K}$. If $S_i<0$, increase the $n_j$ for which $j\equiv i\pmod{K}$. At the end, find an index $j$ for which $p_j$ is greater than $n_j$. This $j$ gives you the starting position in the list. Use the biggest $p_j$ if you want to have the optimum.

If we apply this method to the given example, we get (one after another) $$(S)_{i\in\{1,\ldots,9\}} = (-1,\,1,\,1,\,1,\,1,\,1,\,-1,\,-3,\,-3)$$ For the counters $p_0$ and $n_0$, we have taken the elements $S_3$, $S_6$ and $S_9$ into account (while we calculated the $S_i$). We find that two of them are positive and one is negative, therefore $p_0=2$ and $n_0=1$ in the end.

For the counters $p_1$ and $n_1$, we have taken the elements $S_1$, $S_4$ and $S_7$ into account. We find that one of them is positive and two are negative, therefore $p_1 = 1$ and $n_1=2$.

For the counters $p_2$ and $n_2$, we have taken the elements $S_2$, $S_5$ and $S_8$ into account. We find that two of them are positive and one is negative, therefore $p_2=2$ and $n_2=1$.

For $j=0$ and $j=2$, $p_j>n_j$ holds. Therefore we can split the list either in front of the elements with indices $\equiv 0\pmod{3}$ or in front of the elements with indices $\equiv 2\pmod{3}$.

• Can you explain it briefly with the given example? The explanation is little hard to follow. Also if $K,M$ both are odd, is there any more optimization possible ? – Buckster Feb 17 '17 at 16:58
• Is that $A_{N+i}$ in the $S_i$ a typo ? – Buckster Feb 17 '17 at 17:02
• Where is a $A_{N+i}$ in the $S_i$? – Reinhard Meier Feb 17 '17 at 17:05
• The definition $A_{N+i} = A_i$ is used to avoid distinction of cases. We extend the series of $A$s in order to make the description easier. The list is circular – Reinhard Meier Feb 17 '17 at 17:07
• Sorry, I got it now. Can you explain with example in the question or any small example,please ? It would be very helpful. It's a little difficult for me to understand the solution as of right now. – Buckster Feb 17 '17 at 17:10