1
\$\begingroup\$

I'm trying to write a Java program that, given a particular number of groups and number of total participants, creates a list of all possible ways to fill that number of groups evenly using all the participants. The group number/order doesn't matter. For instance, if {} denotes one possible way to create a set of groups, [] denotes a group, and each individual is represented by a number, the groupings {[1,2],[3,4,5]} and {[4,3,5],[1,2]} should be considered equivalent and are both valid groupings for an input of 5 participants and 2 groups.

So far I've written the following code, which works by recursively finding all possible permutations and removing any duplicates (like in the example above). This works fine for small input values, but becomes extremely slow quickly. Can anyone give my any ideas on how to either optimize this code or for a more efficient way to do this (and if the latter, pseudo or java code would be great)? I know that there might not be an extremely fast way to do this, but I'd like to at least be able to run it with some reasonably small numbers and have it finish in a relatively short time period and not take up more RAM than it has too.

Let me know if the above explanation is unclear! Thanks!

private int numParticipants, numGroups, maxParticipantsPerGroup;
private ArrayList<ArrayList<ArrayList<Integer>>> participantGroups = new ArrayList<ArrayList<ArrayList<Integer>>>();

private void generateParticipantGroupings() {
    ArrayList<ArrayList<Integer>> groupings = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < numGroups; i++)
            groupings.add(new ArrayList<Integer>());

    buildParticipantGrouping(1, groupings);
}

private void buildParticipantGrouping(int currentParticipant, ArrayList<ArrayList<Integer>> grouping) {
    if (currentParticipant > numParticipants) {
        boolean match = false;
        for (int j = 0; j < participantGroups.size(); j++) {
            int numMatches = 0;
            for (int k = 0; k < numGroups; k++) {
                for (int m = 0; m < numGroups; m++) {
                    if (grouping.get(k).equals(participantGroups.get(j).get(m))) {
                        numMatches++;
                        break;
                    }
                }

            }

            if (numMatches >= numGroups) {      
                match = true;
                break;
            }
        }

        if (!match)
            participantGroups.add(grouping);
    }
    else {
        for (int i = 0; i < numGroups; i++) {
            if (grouping.get(i).size()  < maxParticipantsPerGroup)  {
                ArrayList<ArrayList<Integer>> tempGroupings = new ArrayList<ArrayList<Integer>>();
                for (int a = 0; a < numGroups; a++) {
                    tempGroupings.add(new ArrayList<Integer>());

                    for (Integer x : grouping.get(a))
                        tempGroupings.get(a).add(x);
                }

                tempGroupings.get(i).add(currentParticipant);

                buildParticipantGrouping(currentParticipant + 1, tempGroupings);
            }
        }
    }
}

EDIT: Yes, I have searched to see if I can find a previous post that asks the same question. I have not found any. If you can find a previous post asking the same question (that has answers) then I'd love to see it, but otherwise please make sure that a question is actually the same as mine before suggesting it as a duplicate.

\$\endgroup\$
4
  • \$\begingroup\$ possible duplicate of All possible combinations of elements \$\endgroup\$ – Ted Hopp Jun 1 '12 at 3:33
  • \$\begingroup\$ @TedHopp no, in that question they're just getting ways to create a single group (and of varying length). I want combinations into multiple groups, of (basically) fixed size. \$\endgroup\$ – scae Jun 1 '12 at 3:46
  • \$\begingroup\$ possible duplicate: stackoverflow.com/questions/3931775/… \$\endgroup\$ – Ray Tayek Jun 1 '12 at 4:01
  • \$\begingroup\$ @RayTayek Again, that's looking for all ways to create ONE group. I'm trying to create multiple groups using all elements. \$\endgroup\$ – scae Jun 1 '12 at 4:05
1
\$\begingroup\$

First, determine the one or two group sizes that will apply, and how many of each you will have. Define m, the maximum capacity of any one group, as ceil( k / n ). Let i represent the number of groups of size m. Solving for i, we have

m == ceil( k / n )
( m * i ) + ( ( m - 1 ) * ( n - i ) ) == k
( m * i ) + ( m * ( n - i ) ) - ( n - i ) == k
( m * n ) - ( n - i ) == k
( m * n ) - k - n == -i
k + ( n * ( 1 - m ) ) == i

Thus, there will be i groups of size m and n - i groups of size m - 1.

Then, choose an ordering of the groups. This is like generating an integer with a given number of 1 bits. If k happens to be divisible by 'n', there's only one possible ordering. See Gosper's hack for a nifty way to get the next choice given the current choice, which is essential if you want to implement this as an iterator that yields the next grouping on each call to next().

class GosperIterator implements Iterator< Long > {
    private final int iParticipants, iGroups, iMaxCap, iHowManyMax;
    private long lCurrentOrder;
    public GosperIterator( int iParticipants, int iGroups ) {
        this.iParticipants = iParticipants;
        this.iGroups = iGroups;
        this.iMaxCap = Math.ceil( iParticipants / iGroups );
        this.iHowManyMax = iParticipants + ( iGroups * ( 1 - iMaxCap ) );
        // implemented only for maximum of 64 groups
        this.lCurrentOrder = ( 1L << iHowManyMax ) - 1L;
    }
    @Override public boolean hasNext() {
        return lCurrentOrder < ( 1L << iGroups );
    }
    @Override public Long next() {
        long lOut = lCurrentOrder;
        // Gosper's Hack
        long c = lCurrentOrder & -lCurrentOrder;
        long r = lCurrentOrder + c;
        lCurrentOrder = ( ( ( r ^ lCurrentOrder ) >>> 2 ) / c ) | r;
        return lOut;
    }
    // would be nice if there were a read-only iterator interface
    @Override public void remove() {
        throw new UnsupportedOperationException();
    }
}

Then, allocate each participant x to one of the not full groups which is between the first and the maximum empty group. That means, in particular, that participant 1 always ends up in the first group, participant 2 always ends up in the first or second group (if there are two groups), etc.

To do this one grouping per next() call, you will need to produce the first grouping (all the participants in order, say), then start removing participants in reverse order of participant number, looking for an alternative place to assign them which has a higher group number but no smaller empty group. If no such place exists, back out to a smaller participant number. If you get all the way to participant 1, it is time to call on Gosper again, and if there are no numbers left for Gosper, you're done.

class GroupingWithFixedLayoutIterator implements Iterator< Set< Set< Integer > > > {
    @Override public boolean hasNext() {
        // left as exercise
    }
    @Override public Set< Set< Integer > > next() {
        // left as exercise
    }
    // would be nice if there were a read-only iterator interface
    @Override public void remove() {
        throw new UnsupportedOperationException();
    }
}
class GroupingIterator implements Iterator< Set< Set< Integer > > > {
    private final int iParticipants;
    private final Iterator< Long > ilLayout;
    private Iterator< Set< Set< Integer > > issiGrouping = null;

    public GroupingIterator( int iParticipants, int iGroups ) {
        this.iParticipants = iParticipants;
        this.ilLayout = new GosperIterator( iParticipants, iGroups );
        initFixedLayoutIterator();
    }
    private final boolean initFixedLayoutIterator() {
        this.issiGrouping = ilLayout.hasNext()
            ? new GroupingWithFixedLayoutIterator( iParticipants, ilLayout.next() )
            : new EmptyIterator< Set< Set< Integer > > >(); // left as exercise
    }
    @Override public boolean hasNext() {
        return issiGrouping.hasNext() || ilLayout.hasNext();
    }
    @Override public Set< Set< Integer > > next() {
        if ( !issiGrouping.hasNext() )
            initFixedLayoutIterator();
        return issiGrouping.next();
    }
    // would be nice if there were a read-only iterator interface
    @Override public void remove() {
        throw new UnsupportedOperationException();
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ did you actually read my question fully? I need to get ALL possible unique groupings, not just any one grouping. \$\endgroup\$ – scae Jun 1 '12 at 5:41
  • \$\begingroup\$ Each time I say "choose", or "one of", I am implying that you will loop over all possible choices. There are a very large number of combinations. \$\endgroup\$ – Judge Mental Jun 1 '12 at 5:45
  • \$\begingroup\$ ok, sorry I misunderstood. could you be a little bit more concrete (or maybe give some pseudo code) as to how this would actually work (how you'd pick the groups/participants so that every combination was listed, in an efficient manner)? \$\endgroup\$ – scae Jun 1 '12 at 5:53
  • \$\begingroup\$ I'll try to answer this in parts. The fundamental principle is going to be that we need to yield one grouping at a time, because there are so many possibilities that they will never all fit into memory. \$\endgroup\$ – Judge Mental Jun 1 '12 at 6:49
0
\$\begingroup\$

An other (complementary) way to optimize if is rather than creating an ArrayList<ArrayList<ArrayList<Integer>>>, create an implmentation of Iterable<ArrayList<ArrayList<Integer>>> that would internaly store the variables of the outer loop in it's Iterator<ArrayList<ArrayList<Integer>> instances, and perform an iteration each time next() is called. This way, you will have only one instance of ArrayList<ArrayList<Integer>> in RAM at a time.

Then do what you have to do with this Iterable rather that the ArrayList. Implementing things this way would dramatically reduce your RAM usage, which means less allocations and less cache misses. This will not change the complexity of the algorithm, but that can still improve performance a lot. Also, your algorithm will be able to go much further before dying from out of memory.

Not: of course, if you use this solution, you must not use the iterator to store all the instances in an ArrayList or you loose all the benefit. The idea is to do all the processing in a "Stream mode".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.