Rearrange int array, sort into groups with a sum maximum in Java

Question

I know most people don't like writing methods for people but i was hoping someone could help me convert my algorithm into Java code. I hope my algorithm is good and actually works.

Sort a given array of ints into ascending order. Set Group Limit to 15 (that means that the sum of the group is not greater than 15).
Take the first element of the sorted array and insert into a Group (new array/list) eg. Group A.
Take the second element of the sorted array and insert unless it will make it exceed the group limit. If it exceeds, create a new Group B and insert there.
Take third element and try to insert into next available group.
Repeat until all ints have been checked and grouped.

Input:

egArray = [1,3,4,6,6,9,12,14]

Output:

Group A: [1,3,4,6], Group B: [6,9], Group C: [12], Group D: [14]

I have tried to do this, but failed epically, not even worth me posting my code. :-(

This is an example data and an algorithm I've made up for self learning, so please keep the criticism to a minimum. I genuinely learn from a lot of Stackoverflow posts people have written over the last few months, unfortunately I couldn't find one like this example. Thanks.

Sure we would help, but we would like to see, if you are willing to help yourself or not. Please try it out first and post the code that you tried. Then probably we can help. — Rohit Jain, Dec 01 '12 at 19:19
could have written this in single line of code if it were `C#`..ahhh..but it's java — Anirudha, Dec 01 '12 at 19:41
@Anirudha I'm very curious about that line of [tag:C#]. Please share it! — MC Emperor, Feb 11 '16 at 11:07

MC Emperor · Accepted Answer · 2016-02-19T10:59:27.250

Try this:

public static void main(String[] arguments) {
    int limit = 15;
    int[] egArray = new int[] { 14, 1, 3, 4, 6, 6, 9, 12 };

    ArrayList<ArrayList<Integer>> a = grouping(limit, egArray);
    System.out.println(a);
}

public static ArrayList<ArrayList<Integer>> grouping(int limit, int[] array) {
    // Sort the input array.
    Arrays.sort(array);
    // Copy the int[] to an ArrayList<Integer>
    ArrayList<Integer> input = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {
        input.add(array[i]);
    }

    // Initialize the groups
    ArrayList<ArrayList<Integer>> groups = new ArrayList<>();
    groups.add(new ArrayList<Integer>());
    // Initialize the sums of the groups, to increase performance (I guess).
    ArrayList<Integer> sums = new ArrayList<>();
    sums.add(0);

    // Iterate through the input array until there is no number
    // left in it (that means we just added all the numbers
    // into our groups array).
    while (!input.isEmpty()) {
        int n = input.get(0); // Store the number to 'n', to shortcut.
        if (n > limit) {
            String msg = "number is greater than the limit; cannot add number";
            throw new IllegalArgumentException(msg);
            // Or whatever to do if the number is larger than the limit.
        }
        boolean match = false;
        // Search the next groups and check if our current
        // number ('n') fits.
        for (int i = 0; i < sums.size(); i++) {
            if (sums.get(i) + n <= limit) {
                // If it fits, then add the number to the group.
                sums.set(i, sums.get(i) + n);
                groups.get(i).add(n);
                match = true;
                break;
            }
        }
        // If 'n' doesn't fit in any group, create a new one.
        if (!match) {
            ArrayList<Integer> e = new ArrayList<>();
            e.add(n);
            groups.add(e);
            sums.add(n);
        }
        // Remove our number.
        input.remove(0);
    }
    return groups;
}

Notice that the method returns an ArrayList<ArrayList<Integer>> instead of an int[][], but the effect is the same. In order to check the values of the groups, just run the main(String).

This works perfectly. Thank you very much! Thanks also for commenting it. I really appreciate it when people take the time to help me learn. This is awesome. :) — binary101, Dec 01 '12 at 23:20

Yohanes Gultom · Answer 2 · 2012-12-02T03:11:21.457

1

How about this method?

public static ArrayList group(ArrayList<Integer> arr, Integer groupLimit) {
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    ArrayList<Integer> temp = new ArrayList<Integer>();
    for (Integer x : arr) {
        if (sumElements(temp) + x < groupLimit) { 
            temp.add(x);
        } else {
            result.add(temp);
            temp = new ArrayList<Integer>();
            temp.add(x);
        }
    }
    if (temp.size() > 0) {
        result.add(temp);
    }
    return result;
}

public static int sumElements(ArrayList<Integer> arr) {
    Integer result = 0;
    for(Integer x:arr) result += x;
    return result;
}

edited Dec 02 '12 at 03:11

answered Dec 01 '12 at 20:08

Yohanes Gultom

3,782
2
25
38

Should `sumElements(temp) < groupLimit` not be `sumElements(temp)+x <= groupLimit`? And how could `temp` ever become null? – jrtc27 Dec 01 '12 at 22:51
Im unsure how you are using sumElements... is this a separate method? – binary101 Dec 01 '12 at 23:14
This looks like really nice code... Please advise me on the sumElements method? – binary101 Dec 01 '12 at 23:25
@jrtc27 yes, you're right. `temp` can never be null and supposed to be `sumElements(temp)+x <= groupLimit`. Thanks – Yohanes Gultom Dec 02 '12 at 03:11

Rearrange int array, sort into groups with a sum maximum in Java

2 Answers2

Linked