Create a list of all possible combinations of elements into n-groups from a set of size k 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&lt;ArrayList&lt;ArrayList&lt;Integer&gt;&gt;&gt; participantGroups = new ArrayList&lt;ArrayList&lt;ArrayList&lt;Integer&gt;&gt;&gt;();

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

    buildParticipantGrouping(1, groupings);
}

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

            }

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

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

                    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.
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&lt; Long &gt; {
    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 &lt;&lt; iHowManyMax ) - 1L;
    }
    @Override public boolean hasNext() {
        return lCurrentOrder &lt; ( 1L &lt;&lt; iGroups );
    }
    @Override public Long next() {
        long lOut = lCurrentOrder;
        // Gosper's Hack
        long c = lCurrentOrder &amp; -lCurrentOrder;
        long r = lCurrentOrder + c;
        lCurrentOrder = ( ( ( r ^ lCurrentOrder ) &gt;&gt;&gt; 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&lt; Set&lt; Set&lt; Integer &gt; &gt; &gt; {
    @Override public boolean hasNext() {
        // left as exercise
    }
    @Override public Set&lt; Set&lt; Integer &gt; &gt; 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&lt; Set&lt; Set&lt; Integer &gt; &gt; &gt; {
    private final int iParticipants;
    private final Iterator&lt; Long &gt; ilLayout;
    private Iterator&lt; Set&lt; Set&lt; Integer &gt; &gt; 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&lt; Set&lt; Set&lt; Integer &gt; &gt; &gt;(); // left as exercise
    }
    @Override public boolean hasNext() {
        return issiGrouping.hasNext() || ilLayout.hasNext();
    }
    @Override public Set&lt; Set&lt; Integer &gt; &gt; 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();
    }
}