exploding List into multiple groups

Question

I have an extension that explodes List into groups, which makes displaying content easy. Here is the extension code

public static List<List<T>> GroupItems<T>(this List<T> items, int totalGroups)
{
    List<List<T>> groups = null;
    if (items != null)
    {
        groups = new List<List<T>>();
        int itemsPerGroup = (int)Math.Ceiling((double)items.Count / totalGroups);
        if (itemsPerGroup > items.Count)
        {
            List<T> group = new List<T>(items);
            groups.Add(group);
        }
        else
        {

            for (int i = 0; i < totalGroups; i++)
            {
                List<T> group = items.Skip(i * itemsPerGroup).Take(itemsPerGroup).ToList();
                groups.Add(group);
            }
        }
    }

    return groups;
}

Here is the scenario:

I have a List and it has 13 items (items may vary).

In this particular instance, since i am exploding the list into 4 groups, i am getting

• group 1: 4 items

• group 2: 4 items

• group 3: 4 items

• group 4: 1 item

The 4 items per group is coming from

int itemsPerGroup = (int)Math.Ceiling((double)items.Count / totalGroups);

Now this is wrong, ideally i should have

• group 1: 4 items
• group 2: 3 items
• group 3: 3 items
• group 4: 3 items

Same way, when i try to explode this into 6 groups, i get

• group 1: 3 items
• group 2: 3 items
• group 3: 3 items
• group 4: 3 items
• group 5: 1 item
• group 6: 0 items

you can see this in the attached pic here as well

Ideally this should have

• group 1: 3 items
• group 2: 2 items
• group 3: 2 items
• group 4: 2 items
• group 5: 2 items
• group 6: 2 items

What am i missing here? How can i fix this issue?

Answer 1

Because you want the average in each group and the earliest rounded up for as long as it's needed I can suggest this algorithm.

public static List<List<T>> GroupItems<T>(this List<T> items, int totalGroups)
    {
        if (items == null || totalGroups == 0) return null;
        var ret = new List<List<T>>();

        var avg = items.Count / totalGroups; //int  rounds towards 0
        var extras = items.Count - (avg * totalGroups);
        for (var i = 0; i < totalGroups; ++i)
            ret.Add(items.Skip((avg * i) + (i < extras ? i : extras)).Take(avg + (i >= extras ? 0 : 1)).ToList());
        return ret;
    }

The advantage is, it's short and conside and scales with O(n^2) just like any two-dimensional algorithm should. The design ideas are: Find the average, find N=Missing elements after average and let the first N elements get one extra element to fill up the gap.

Answer 2

i would calculate items per group each time.

 int itemsPerGroupCount = 0;
 for (int i = 0; i < totalGroups; i++)
        {
            int itemsPerGroup = (int)Math.Ceiling(
                 ((double)items.Count - itemsPerGroupCount) / (totalGroups - i));

            itemsPerGroupCount += itemsPerGroup;

            List<T> group = items.Skip(itemsPerGroupCount).Take(itemsPerGroup).ToList();
            groups.Add(group);
        }

Answer 3

I would calculate the items per group as such (floor instead of ceiling):

int itemsPerGroup = (int)Math.Floor((double)items.Count / totalGroups);

Then I would figure out the number of remaining items:

int remainingItems = items.Count % totalGroups

And then in your loop:

int itemsToSkip = 0;
for (int i = 0; i < totalGroups; i++)
{
    int itemsPerGroupTemp = itemsPerGroup;
    if (remainingItems != 0) {
        itemsPerGroupTemp++;
        remainingitems--;
    }
    List<T> group = items.Skip(itemsToSkip ).Take(itemsPerGroupTemp).ToList();
    groups.Add(group);
    itemsToSkip += itemsPerGroupTemp;
}

Answer 4

How about going about it the other way, say you have 13 items you want 6 groups so take (as int) (13/6) and floor it, this will give you 2. Now with the same number of groups (6) multiply that by group size (2) gives you 12. you had 13 items so you have one left, add that to the first group. Should give you a nizer set of groups.

Answer 5

If you adjust your for loop to something like this

 for (int i = 0; i < totalGroups; i++)
                {
                    List<T> group = items.Skip(i * itemsPerGroup).Take(itemsPerGroup).ToList();
                    groups.Add(group);
                    if(i==0)
                        itemsPerGroup = (int)Math.Ceiling((double)(items.Count - itemsPerGroup  )/ (totalGroups - 1) );
                }

Answer 6

If the order of the items across the groups is not relevant then you can simply do this with Linq by grouping by the index modulo the number of groups.

var result = list.Select((v,i)=>new{Value=v,Index=i})
                 .GroupBy(x => x.Index % numberOfGroups)
                 .Select(grp => grp.Select(x => x.Value).ToList())
                 .ToList();

So the following

List<int> list = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };
var result =
    list.Select((v, i) => new { Value = v, Index = i })
        .GroupBy(x => x.Index % 6)
        .Select(grp => grp.Select(x => x.Value).ToList())
        .ToList();

int groupNumber = 1;
foreach (var l in result)
{
    Console.WriteLine("Group {0} : {1}", groupNumber++, string.Join(", ", l));
}

Will have these results

Group 1 : 1, 7, 13

Group 2 : 2, 8

Group 3 : 3, 9

Group 4 : 4, 10

Group 5 : 5, 11

Group 6 : 6, 12

Answer 7

What I suppose you should do is calculate the average amount of items per bucket(aka List) and then insert that much into each bucket and then insert the remainder objects.

Note: Keeps order, and <int> can be replaced with <T>

for example:

public static List<List<int>> ExpandIntoGroups(this List<int> items, int totalGroups)
{
    List<List<int>> expandedList = null;
    if (items != null)
    {
        expandedList = new List<List<int>>();

        // Get amount of items to insert per list (for example: for 14 items, 4 groups, returns {4, 4, 3, 3}
        int[] itemsToInsertPerGroup = GetItemsToInsertPerGroup(items, totalGroups);

        // Go over each group
        for (int currGroup = 0, itemCount = 0;
             currGroup < itemsToInsertPerGroup.Length;
             currGroup++)
        {
            // add the list for the group
            expandedList.Add(new List<int>());

            // Add as much items as needed 
            for (int i = 0;
                 i < itemsToInsertPerGroup[currGroup] && 
                 itemCount < items.Count;
                 i++, itemCount++)
            {
                expandedList[currGroup].Add(items[itemCount]);
            }
        }
    }

    return expandedList;
}

private static int[] GetItemsToInsertPerGroup(List<int> items, int totalGroups)
{
    // Get average amount of items per list
    int avgItemsPerGroup = (int)(items.Count / totalGroups);

    int[] itemsToInsert = new int[totalGroups];

    // Set each cell to be the average
    for (int i = 0; i < itemsToInsert.Length; i++)
    {
        itemsToInsert[i] = avgItemsPerGroup;
    }

    // get how many items remain after inserting average amount
    int remainingItems = items.Count - avgItemsPerGroup * totalGroups;

    // Increase the amount needed per cell for each remaining item
    for (int i = 0, j = 0;
         i < remainingItems;
         ++i, ++j)
    {
        itemsToInsert[j]++;
    }

    return itemsToInsert;
}

Of course this is an ugly way of doing it, but it does the job.

Some test output:

Total items : 14
Total groups : 4

List 1 has 4 items
List 2 has 4 items
List 3 has 3 items
List 4 has 3 items

List 1 : 1 2 3 4 
List 2 : 5 6 7 8 
List 3 : 9 10 11 
List 4 : 12 13 14