Recursively partitioning an array into N equal parts of size <= N?

Question

I have an array of roughly one million sorted integers.

I need to implement a program that works similar to the following:

Input:

partition ( array, N )

Output:

The list gets partitioned into N equal parts. Each partition then gets partitioned into N equal parts. Continue until the number of elements in each partition <= N.

I do not wish to modify the list itself to do this--I just somehow need to return the partition indices at various recursion depths so I can eventually print a final output of a bunch of nested ranges that would look something like:

> partition arr 10
0..99999
 0..9999
 0..999
 ..
 0..9 --lowest depth
 10..19
 20..29
 ...
 90..99
 ..
 10000..19999
 ...
 90000..99999
 ...
100000..199999
 100000..109999
 ...
 110000..190000
 ...
 90000..99999
 ...
200000..299999
 ...
300000..399999
 ...
400000..499999
 ...
500000..599999
 ...
600000..699999
 ...
700000..799999
 ...
800000..899999
 ...
900000..999997
 ...

I could possibly figure it out if I had pseudocode for how I could do this in any sort of procedural language; for the time being, I do not know how to start.

Answer 1

To subdivide an array A[i..j[ (j excluded) in n subarrays of equal size (to 1 element), use A[ii..jj[ with

ii= i + k * (j - i) / n
jj= i + (k+1) * (j - i) / n

and k in [0..n[.

Answer 2

I figured this out. Here is the code to generate the desired output, in Python3:

def npart(ls, n):
 p = len(ls) // n
 if len(ls)-p > 0:
 return [ls[:p]] + npart(ls[p:], n-1)
 else:
 return [ls]
def part(ls, n, i):
 ls = npart(ls, n)
 for l in ls:
 print(" " * i + "[" + str(l[0]) + ".." + str(l[len(l)-1]) + "] (" + str(len(l)) + ")")
 if len(l) > n * 2:
 part(l, n, i + 1)
part(arr, 16, 0)

For one of the arrays I passed it, it yields:

[0..327679] (66560)
 [0..6655] (4160)
 [0..403] (260)
 [0..15] (16)
 [16..31] (16)
 [50..71] (16)
 [72..87] (16)
 [88..127] (16)
 [128..143] (16)
 [144..159] (16)
 [178..199] (16)
 [200..215] (16)
 [216..255] (16)
 [256..271] (16)
 [272..287] (16)
 [306..328] (17)
 [329..345] (17)
 [346..386] (17)
 [387..403] (17)
 [404..831] (260)
 [404..439] (16)
 [442..459] (16)
 [460..475] (16)
 [476..515] (16)
 [516..531] (16)
 [532..567] (16)
 [570..587] (16)
 [588..603] (16)
 [604..643] (16)
 [644..659] (16)
 [660..695] (16)
 [698..715] (16)
 [716..732] (17)
 [733..773] (17)
 [774..790] (17)
 [791..831] (17)
 [832..1235] (260)
 [832..847] (16)
 [848..863] (16)
 [882..903] (16)
 [904..919] (16)
 [920..959] (16)
 [960..975] (16)
 [976..991] (16)
...
...
...
 [8384454..8385823] (260)
 [8384454..8384527] (16)
 [8384534..8384607] (16)
 [8384630..8384703] (16)
 [8384710..8384783] (16)
 [8384790..8384863] (16)
 [8384886..8384959] (16)
 [8384966..8385039] (16)
 [8385046..8385119] (16)
 [8385142..8385215] (16)
 [8385222..8385295] (16)
 [8385302..8385375] (16)
 [8385398..8385471] (16)
 [8385478..8385558] (17)
 [8385559..8385655] (17)
 [8385662..8385742] (17)
 [8385743..8385823] (17)
 [8385846..8387215] (260)
 [8385846..8385919] (16)
 [8385926..8385999] (16)
 [8386006..8386079] (16)
 [8386102..8386175] (16)
 [8386182..8386255] (16)
 [8386262..8386335] (16)
 [8386358..8386431] (16)
 [8386438..8386511] (16)
 [8386518..8386591] (16)
 [8386614..8386687] (16)
 [8386694..8386767] (16)
 [8386774..8386847] (16)
 [8386870..8386950] (17)
 [8386951..8387031] (17)
 [8387038..8387134] (17)
 [8387135..8387215] (17)
 [8387222..8388607] (260)
 [8387222..8387295] (16)
 [8387318..8387391] (16)
 [8387398..8387471] (16)
 [8387478..8387551] (16)
 [8387574..8387647] (16)
 [8387654..8387727] (16)
 [8387734..8387807] (16)
 [8387830..8387903] (16)
 [8387910..8387983] (16)
 [8387990..8388063] (16)
 [8388086..8388159] (16)
 [8388166..8388239] (16)
 [8388246..8388342] (17)
 [8388343..8388423] (17)
 [8388430..8388510] (17)
 [8388511..8388607] (17)