Find all ways to partition a set into given-sized subsets

Question

It isn't really complicated, but I just can't figure out how to do it.
I have one set with objects, let's say they are numbers. I need to check all the possibilities of N groups (we can assume there are 3 groups, 9 objects in set), where order inside group doesn't matter ({1,2,3}, {2,1,3}, {3,2,1}, etc. are the same) and order of groups doesn't matter ([{1,2,3},{4,5,6}] is the same as [{5,4,6},{2,1,3}]). I'm writing code in C#, but there really isn't anything I could show. The closest idea I had contained a lot of fors and ifs

Answer 1

The solution I've used places the elements in order; this avoids any problems of duplication. It uses recursion and backtracking to find all solutions.

The critical restriction to keep from duplicating a solution is that you may not place an element into the nth partition unless all lower-numbered partitions are non-empty.

Consider your problem, 9 students in 3 partitions. We start with three empty sets

{} {} {}

We now need to place students [1, 2, 3, 4, 5, 6, 7, 8, 9] into this partition set. Call our function

place({ {}, {}, {} }, [1, 2, 3, 4, 5, 6, 7, 8, 9])

We place the students in order. Student 1 has only one place to go: the first partition. Otherwise, we would violate the restriction.

place({ {1}, {}, {} }, [2, 3, 4, 5, 6, 7, 8, 9])

Student 2 can go into either of the first two partitions (i.e. you'll need an iteration loop to cover the legal possibilities). From here, you'll cycle through two recursive calls:

place({ {1, 2}, {}, {} }, [3, 4, 5, 6, 7, 8, 9])
place({  {1},  {2}, {} }, [3, 4, 5, 6, 7, 8, 9])

In the first call, 3 cannot yet go into the 3rd partition; in the second call, it can go anywhere.

Do you see how this works? As the partitions fill up (I infer a limit of 3 students in each group), you'll need to check for a full group, as well. At the end, each time you place the final student, you have a valid, unique arrangement.

Coding is left as an exercise for the reader. :-)

Answer 2

Well I wrote this yesterday. It takes a lot of time to generate all solutions, but it works. I suppose I can make it faster if I use some tree to store elements (now every new group is compared with all existing groups).

Edit: Actualy now when I think about it, I'm not sure if there are possible duplicats. I wrote that when I had for loop through all elements. Maybe I can remove that "if" to make it faster. I'll check that when I'll have access to my laptop.
There were no dups. Now it's fast and result seems to be okay.

public class Group<T> : IComparable<Group<int>>
{
    public Group(IEnumerable<T> elements)
    {
        Elements = elements.OrderBy(n => n).ToArray();
    }
    public T[] Elements { get; }

    public bool Equals(Group<T> other)
    {
        if (object.ReferenceEquals(this, other))
            return true;
        //assume number of elements in groups are equal
        for (int i = 0; i < Elements.Length; i++)
            if (!Elements[i].Equals(other.Elements[i]))
                return false;
        return true;
    }


    public int CompareTo(Group<int> other)
    {
        int[] elements = Elements as int[];
        for (int i = 0; i < Elements.Length; i++)
        {
            if (elements[i] < other.Elements[i])
                return -1;
            else if (elements[i] > other.Elements[i])
                return 1;
        }

        return 0;
    }

    public override string ToString()
    {
        string result = "{";
        for (int i = 0; i < Elements.Length; i++)
            result += Elements[i] + (i == Elements.Length - 1 ? "" : ", ");
        result += "}";
        return result;
    }
}
class Program
{
    static void Main(string[] args)
    {
        int[] allElements = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        List<Group<int>> singleGroupCombinations = new List<Group<int>>();
        for (int i = 0; i < allElements.Length; i++)
        {
            for (int j = i + 1; j < allElements.Length; j++)
            {
                for (int k = j + 1; k < allElements.Length; k++)
                {
                    Group<int> newGroup = new Group<int>(new[]
                    {
                        allElements[i], allElements[j], allElements[k]
                    });
                    singleGroupCombinations.Add(newGroup);
                }
            }
        }


        List<Group<Group<int>>> groupsCombinations = new List<Group<Group<int>>>();
        for (int i = 0; i < singleGroupCombinations.Count; i++)
        {
            for (int j = i+1; j < singleGroupCombinations.Count; j++)
            {
                for (int k = j+1; k < singleGroupCombinations.Count; k++)
                {
                    Group<Group<int>> newGroup = new Group<Group<int>>(new[]
                    {
                        singleGroupCombinations[i], singleGroupCombinations[j], singleGroupCombinations[k]
                    });
                    groupsCombinations.Add(newGroup);
                }
            }
        }
        //all groups combinations in groupCombinations variable
    }
}