Algorithm to split an array into N groups based on item index (should be something simple)

Question

I feel that it should be something very simple and obvious but just stuck on this for the last half an hour and can't move on.

All I need is to split an array of elements into N groups based on element index.

For example we have an array of 30 elements [e1,e2,...e30], that has to be divided into N=3 groups like this:

group1: [e1, ..., e10]
group2: [e11, ..., e20]
group3: [e21, ..., e30]

I came up with nasty mess like this for N=3 (pseudo language, I left multiplication on 0 and 1 just for clarification):

for(i=0;i<array_size;i++) {
   if(i>=0*(array_size/3) && i<1*(array_size/3) {
      print "group1";
   } else if(i>=1*(array_size/3) && i<2*(array_size/3) {
      print "group2";
   } else if(i>=2*(array_size/3) && i<3*(array_size/3)
      print "group3";
   }
}

But what would be the proper general solution?

Thanks.

Answer 1

 const int g = 3;                      // number of groups
 const int n = (array_size + g - 1)/g; // elements per group

 for (i=0,j=1; i<array_size; ++i) {
    if (i > j*n)
        ++j;
     printf("Group %d\n", j);
 }

Answer 2

int group[3][10];
int groupIndex = 0;
int itemIndex = 0;
for(i = 0; i < array_size; i++)
{
    group[groupIndex][itemIndex] = big_array[i];
    itemIndex++;
    if (itemIndex == 10)
    {
        itemIndex = 0;
        groupIndex++;   
    }
}

Answer 3

What about something like this?

for(i=0;i<array_size;i++) {
  print "group" + (Math.floor(i/(array_size/N)) + 1)
}

Answer 4

There's probably an infinite number of ways of do this. I'd suggest: for each group, create a base pointer and count.

struct group {foo * ptr; size_t count };
group * pgroups = new group [ngroups];
size_t objects_per_group = array_size / ngroups;
for (unsigned u = 0; u < ngroups; ++u ) {
   group & g =  pgroups[u];
   size_t index = u * objects_per_group;
   g.ptr = & array [index];
   g.count = min (objects_per_group, array_size - index);  // last group may have less!
}
...`
for (unsigned u = 0; u < ngroups; ++u) {
   // group "g" is an array at pgroups[g].ptr, dimension pgroups[g].count
   group & g =  pgroups[u];
   // enumerate the group:
   for (unsigned v = 0; v < g.count; ++v) {
      fprintf (stdout, "group %u, item %u, %s\n",
         (unsigned) u, (unsigned) v, (const char *) g.ptr[v]->somestring);
}  }

delete[] pgroups;

Answer 5

Using a vector language makes this task simple, right tool and all that. Just thought I'd throw this out there to let folks check out an alternative methodology.

The explained version in K (an APL descendent):

split:{[values;n]    / define function split with two parameters
  enum:!n            / ! does enumerate from 0 through n exclusive, : is assign
  floor:_(#values)%n / 33 for this sample, % is divide, _ floor, # count
  cut:floor*enum     / 0 33 66 for this sample data, * multiplies atom * vector
  :cut _ values      / cut the values at the given cutpoints, yielding #cut lists
  }

values:1+!30           / generate values 1 through 30
n:3                    / how many groups to split into
groups:split[values;n] / set the groups

yields the expected output:

(1 2 3 4 5 6 7 8 9 10
 11 12 13 14 15 16 17 18 19 20
 21 22 23 24 25 26 27 28 29 30)

The short version in K :

split:{((_(#x)%y)*!y)_ x}
groups:split[1+!30;3]

yields the same output:

(1 2 3 4 5 6 7 8 9 10
 11 12 13 14 15 16 17 18 19 20
 21 22 23 24 25 26 27 28 29 30)

Answer 6

http://mathworld.wolfram.com/Permutation.html

To Add to what I was saying; here is the Equation to represent permutations of grouping orders.

Answer 7

Here's a little function which will do what you want - it presumes you know the number of groups you want to make:

function arrayToGroups(source, groups) {  

                     //This is the array of groups to return:
                     var grouped = [];

                     //work out the size of the group
                     groupSize = Math.ceil(source.length/groups);

                     //clone the source array so we can safely splice it
                     var queue = source;

                     for (var r=0;r<groups;r++) {
                       //Grab the next groupful from the queue, and append it to the array of groups
                       grouped.push(queue.splice(0, groupSize));      
                     }       
             return grouped;
}

And you use it like:

var herbs = ['basil', 'marjoram', 'aniseed', 'parsely', 'chives', 'sage', 'fennel', 'oregano', 'thyme', 'tarragon', 'rosemary'];

var herbGroups = arrayToGroups(herbs, 3);

which returns:

herbGroups[0] = ['basil', 'marjoram', 'aniseed', 'parsely']
herbGroups[1] = ['chives', 'sage', 'fennel', 'oregano']
herbGroups[2] = ['thyme', 'tarragon', 'rosemary']

It doesn't do any sanity checking to make sure you pass in an array and a number, but you could add that easily enough. You could probably prototype it into the Javascript's object type, too, which would give you a handy 'toGroups' method on Arrays.