2
$\begingroup$

I have a sequence ( n, n-1, n-2,...,1). I need to find numbers in this sequence in this order that somewhat approximately divide it into M parts- within each M subgroup the sum is somewhat the same. Is there a general way to do it?

For example, 5,4,3,2,1 - for M=3, it could be 5; 4; 3,2,1 where the sums are somewhat close (5,4,6). Or 8,7,6,5,4,3,2,1 - For M=3 maybe 8;7+6=13;(rest)15. 8;13;15 is good enough split(15;11;10 is also okay and arguably better than 8,13,15). I don't need it to be exactly equal but for a value of n, M is there a general way to approximately split it? In my case, n is very large( 1000s) and M is probably no greater than 8 at most.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This will be hard to answer, unless you tell us precisely what "somewhat the same", "somewhat close". "approximately split" mean. Arnold Ross used to ask, rhetorically, "What's an approximation to five?" and the correct answer was "any number but five". $\endgroup$
    – Gerry Myerson
    Commented Apr 25, 2020 at 23:09
  • $\begingroup$ So this is actually a programming thing where I have to split the jobs to processors. I don't know the value of n upfront and I am just trying to optimize the utilization of all processors. Somewhat same is me trying to make sure all the processors spend time and it doesn;t overload one processor while the other is sitting free. unfortunately that;s all i got. $\endgroup$
    – user1775614
    Commented Apr 26, 2020 at 20:56
  • $\begingroup$ For $M=4$ and n divisible by 8 such that $n+1$ is prime, it's an exercise to show that dividing $[1...n]$ into their quartic Jacobi symbols mod $p$ gives equal sums. Meaning, you can take the $(p-1)/4$-th power of each number mod $p$, and assign a processor for each of the four possible results. If $n$ doesn't satisfy the requirement, then find the largest prime less than $n$ that is $1\mod{8}$, apply the procedure, and you're left with $O(log(n)^2)$ terms of size $O(n)$ (assuming Cramer's hypothesis), which are negligible in comparison to the $O(n^2)$ work you have. $\endgroup$
    – Dror Speiser
    Commented Apr 29, 2020 at 1:44

1 Answer 1

Reset to default
2
$\begingroup$

You can solve the problem exactly as a shortest path problem in a layered network. The nodes are $(i,k)$, where $i\in\{n,\dots,1\}$ and $k\in\{1,\dots,M\}$. The (directed) arcs are from $(i,k)$ to $(j,k+1)$ with $j<i$. The idea is that traversing arc $(i,k)\to (j,k+1)$ means that $\{i,i-1,\dots,j+1\}$ comprise a part. The cost of this arc is the (absolute, or squared, or any type of) deviation from the target $n(n+1)/(2M)$. Because the network is acyclic, you can solve the problem in $O(M n^2)$ time, that is, linear in the number of arcs.

Alternatively, a greedy heuristic could be to start a new part $p+1$ whenever including the next number would make the cumulative sum exceed $pn(n+1)/(2M)$. For $n=5$ and $M=3$, this yields $5;4;3+2+1$. For $n=8$ and $M=3$, this yields $8;7+6;5+4+3+2+1$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The greedy heuristic makes sense to me - if I fixed M=4, is there a general formula for any n maybe? $\endgroup$
    – user1775614
    Commented Apr 26, 2020 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .