Mat - 1 year ago 85
C Question

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

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?

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];

++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");
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download