How to divide an array of n length into k sub arrays that have approximately equal sizes (in C)?

Question

I have an array of size n, and want to divide into k number of sub arrays, and each array must have approximately the same size. I have been thinking for a while and know that you must use two for loops, but I am having a hard time implementing these for loop.

What I've Tried:

//Lets call the original integer array with size n: arr
// n is the size of arr
// k is the number of subarrays wanted

int size_of_subArray = n/k;
int left_over = n%k; // When n is not divisible by k
int list_of_subArrays[k][size_of_subArray + 1];

//Lets call the original integer array with size n: arr

for(int i = 0; i < k; i++){
   for(int j = 0; j < size_of_subArray; j++){
       list_of_subArrays[i][j] = arr[j];
   }
}

I am struggling with getting the correct indexes in the forloops.

Any Ideas?

Answer 1

I've refactored your code and annotated it.

The main points are:

1. When calculating the sub-array size, it must be rounded up
2. The index for arr needs to continue to increment from 0 (i.e. it is not reset to 0)

The following should work, but I didn't test it [please pardon the gratuitous style cleanup]:

// Lets call the original integer array with size n: arr
//  n is the size of arr
//  k is the number of subarrays wanted

// round up the size of the subarray
int subsize = (n + (k - 1)) / k;

int list_of_subArrays[k][subsize];

int arridx = 0;
int subno = 0;

// process all elements in original array
while (1) {
    // get number of remaining elements to process in arr
    int remain = n - arridx;

    // stop when done
    if (remain <= 0)
        break;

    // clip remaining count to amount per sub-array
    if (remain > subsize)
        remain = subsize;

    // fill next sub-array
    for (int subidx = 0; subidx < remain; ++subidx, ++arridx)
        list_of_subArrays[subno][subidx] = arr[arridx];

    // advance to next sub-array
    ++subno;
}

---

UPDATE:

Yes this divides the arrays into n subarrays, but it doesn't divide it evenly. Say there was an array of size 10, and wanted to divide it into 9 subarrays. Then 8 subarrays will have 1 of original array's element, but one subarray will need to have 2 elements.

Your original code had a few bugs [fixed in the above example]. Even if I were doing this for myself the above would have been the first step to get something working.

In your original question, you did say: "and each array must have approximately the same size". But, here, there is the physical size of the list sub-array [still a rounded up value].

But, I might have said something like "evenly distributed" or some such to further clarify your intent. That is, that you wanted the last sub-array/bucket to not be "short" [by a wide margin].

Given that, the code starts off somewhat the same, but needs a bit more sophistication. This is still a bit rough and might be optimized further:

#include <stdio.h>

#ifdef DEBUG
#define dbgprt(_fmt...)     printf(_fmt)
#else
#define dbgprt(_fmt...)     /**/
#endif

int arr[5000];

// Lets call the original integer array with size n: arr
//  n is the size of arr
//  k is the number of subarrays wanted

void
fnc2(int n,int k)
{
    // round up the size of the subarray
    int subsize = (n + (k - 1)) / k;

    int list_of_subArrays[k][subsize];

    dbgprt("n=%d k=%d subsize=%d\n",n,k,subsize);

    int arridx = 0;

    for (int subno = 0;  subno < k;  ++subno) {
        // get remaining number of sub-arrays
        int remsub = k - subno;

        // get remaining number of elements
        int remain = n - arridx;

        // get maximum bucket size
        int curcnt = subsize;

        // get projected remaining size for using this bucket size
        int curtot = remsub * curcnt;

        // if we're too low, up it
        if (curtot < remain)
            ++curcnt;

        // if we're too high, lower it
        if (curtot > remain)
            --curcnt;

        // each bucket must have at least one
        if (curcnt < 1)
            curcnt = 1;

        // each bucket can have no more than the maximum
        if (curcnt > subsize)
            curcnt = subsize;

        // last bucket is the remainder
        if (curcnt > remain)
            curcnt = remain;

        dbgprt("  list[%d][%d] --> arr[%d] remain=%d\n",
            subno,curcnt,arridx,remain);

        // fill next sub-array
        for (int subidx = 0; subidx < curcnt; ++subidx, ++arridx)
            list_of_subArrays[subno][subidx] = arr[arridx];
    }

    dbgprt("\n");
}