2. Permutations

This example defines extension methods in the static ArrangingExtensions class. The following code shows the main Permutations method:

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

This method gets the number of values in the array and then creates an array of bool with the same size. The program will use that array to keep track of which values are in the solution as the code works on it.

The code then creates a List<T> to hold the current solution. It passes the values, the desired number of items in each permutation, the current solution (initially empty), the used array (initially all false), and the number of values into the following FindPermutations helper method:

// Find permutations that include the current solution.
private static List<List<T>> FindPermutations<T>(T[] values,
    int numPerGroup, List<T> currentSolution, bool[] used,
    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 = 0; 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 =
                FindPermutations(values, numPerGroup, currentSolution,
                    used, numValues);
            results.AddRange(newResults);

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

Before I describe the FindPermutations method in detail, it's worth giving you a short overview. The method calls itself recursively to build the permutations. When it is called, the currentSolution list holds the beginning of a permutation. The method examines the other items that are not already in the permutation (as determined by their used values being false) and adds some to the current solution.

Now, on to the method's details. The method begins by checking the number of items in the current solution. If that solution contains the desired number of items, then it is a valid solution so the method returns it.

However, the currentSolution list will be changed later as instances of the FindPermutations method pass the currentSolution variable back and forth. If the method simply returned currentSolution, its value would change later and that would destroy the current solution.

In order to preserve the current solution, the method makes a copy of it and returns the copy.

If the current solution isn't long enough, the method loops through all of the items trying to extend the solution. If an item's used flag indicates that it is not yet in the solution, the method tries adding it.

The method sets the item's used value to true, adds it to the current solution, and then recursively calls itself to continue building the solution. Other recursive calls to FindPermutations will add more items to the solution until it has the desired length.

After the recursive call returns, the method adds any results returned by that call to the results list.

The method then removes the most recently added item from the current solution by setting its used value to false and removing it from the currentSolution list. The method does that so it can consider other items for the next position in the solution.

After it has considered adding all of the items to the solution, the method returns whatever results it has found.

Notice that the method considers all of the items that are not yet part of the solution. For example, suppose the current solution contains three items. The method could place any of the remaining items in the fourth position.

If an item is not used in the fourth position, it might be added later by another recursive call to FindPermutations.

In particular, consider the items in positions i and j in the original array of values. The FindPermutations method could add item i and then later add item j, or it could add item j and then later add item i. The values could appear in any positions and in any order. This flexibility of ordering is what makes the result a permutation. You should contrast this with the combinations produced by the next solution.

One special case that is not handled is by the previous Permutations method, that is, when the numPerGroup parameter is omitted. In that case, the Permutations method should return permutations of every possible length. The following overloaded version of the method does just that:

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

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

This version of the Permutations method loops through all of the possible permutation lengths between 1 and the number of values present. It calls the previous version of the method to find permutations of those lengths, combines the results into a single list, and returns it.

The solution's main program uses the Permutations extension methods to display permutations. The heart of the program is shown in the following code snippet:

// Get the inputs.
char[] separators = { ' ' };
string[] values = valuesTextBox.Text.Split(separators, StringSplitOptions.RemoveEmptyEntries);
int numPerGroup = int.Parse(numPerGroupTextBox.Text);

// Get the permutations.
List<List<string>> permutations;
if (numPerGroup == 0)
    permutations = values.Permutations();
else
    permutations = values.Permutations(numPerGroup);

// Display the results.
foreach (List<string> permutation in permutations)
    resultsListBox.Items.Add(string.Join(" ", permutation.ToArray()));

This code gets the values and the number of items that should be in each permutation. Next, the method calls the Permutations extension method on the values array. It finishes by looping through the permutations, adding each to the result list box. It uses the technique described in the preceding solution to convert the permutation list into a string containing values separated by spaces.

Download the Permutations example solution to see additional details.