Mat - 7 months ago 42

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

I've refactored your code and annotated it.

The main points are:

- When calculating the sub-array size, it must be rounded up
- 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");
}
```

Source (Stackoverflow)