3. Combinations

The Combinations method works much like the Permutations method did in the preceding section. The main Combinations method calls the FindCombinations helper method to do most of the work recursively. That method loops through the values, adds them to the growing current solution, and calls itself recursively to build longer combinations.

The following code shows the Combinations method:

// Find combinations containing the desired number of items.
public static List<List<T>> Combinations<T>(this T[] values,
    int numPerGroup)
{
    int numValues = values.Count();
    bool[] used = new bool[numValues];
    List<T> currentSolution = new List<T>();
    return FindCombinations(values, numPerGroup, currentSolution,
        used, 0, numValues);
}

See the description of the Permutations method in the preceding section for details about how this method works.

The following code shows the FindCombinations method:

// Find Combinations that include the current solution.
private static List<List<T>> FindCombinations<T>(T[] values,
    int numPerGroup, List<T> currentSolution, bool[] used,
    int firstIndex, int numValues)
{
    List<List<T>> results = new List<List<T>>();

    // If this solution has the desired length, return it.
    if (currentSolution.Count() == numPerGroup)
    {
        // Make a copy because currentSolution will change over time.
        List<T> copy = new List<T>(currentSolution);
        results.Add(copy);
        return results;
    }

    // Try adding other values to the solution.
    for (int i = firstIndex; i < numValues; i++)
    {
        // See if value[i] is in the solution yet.
        if (!used[i])
        {
            // Try adding this value.
            used[i] = true;
            currentSolution.Add(values[i]);

            // Recursively look for solutions that have values[i] 
            // added.
            List<List<T>> newResults =
                FindCombinations(values, numPerGroup, currentSolution,
                    used, i + 1, numValues);
            results.AddRange(newResults);

            // Remove values[i].
            used[i] = false;
            currentSolution.RemoveAt(currentSolution.Count() - 1);
        }
    }
    return results;
}

This method is somewhat similar to the FindPermutations method described in the preceding section, with the major exception that it takes a parameter that gives the index of the first item that the method should consider adding to the solution. When the method loops through the values, it only considers the items that have this index or later.

This prevents the method from adding items in orders other than the one in which they appear in the values array. For example, suppose i and j are indices of items in the array and that i < j. Then this method would consider adding values[i] and then later adding values[j], but it would not consider adding values[j] before adding values[i] because i < j.

By keeping the values in their sorted order, the method produces combinations rather than permutations.

The following code shows the overloaded version of the Combinations method that returns combinations of any length:

// Find combinations containing any number of items.
public static List<List<T>> Combinations<T>(this T[] values)
{
    List<List<T>> results = new List<List<T>>();

    // Get combinations of all lengths.
    for (int i = 1; i <= values.Count(); i++)
        results.AddRange(values.Combinations(i));
    return results;
}

This method loops through the possible combination sizes, calls the earlier version of the Combinations method to get combinations of those lengths, combines them, and returns the result.

The solution's main program is similar to the one for the preceding problem. See the preceding section for more information and download the Combinations example solution to see additional details.