The basic idea is to use a recursive routine to assign the next item in a permutation. The first call to the routine assigns the permutation's first item, the next call assigns the second item, and so forth.

To assign an item, the routine loops through all of the objects looking for those that have not already been assigned. When it finds such an item, the routine:

• Adds the item to the current permutation.
• Marks the item as used in the current permutation.
• Recursively calls itself to assign the next item in the current permutation.
• When the recursive call returns, the routine unmarks the item so it is not used and can be used again later.

The functions used by this program are generic. In this example they use strings because that's what you can easily enter on the form but you can use the same routines to permute other objects.

The following code shows how the program generates permutations when you click the Go button.

// Generate the combinations.
private void btnGo_Click(object sender, EventArgs e)
{
    // Get the items.
    string[] items = txtItems.Text.Split(' ');

    // Generate the permutations.
    List> results =
        GeneratePermutations(items.ToList());

    // Display the results.
    lstPermutations.Items.Clear();
    foreach (List combination in results)
    {
        lstPermutations.Items.Add(string.Join(" ", combination.ToArray()));
    }

    // Calculate the number of permutations.
    long num_permutations = Factorial(items.Length);
    txtNumPermutations.Text = num_permutations.ToString();

    // Check the result.
    Debug.Assert(lstPermutations.Items.Count == num_permutations);
}

This code makes a list of the words you entered. It calls GeneratePermutations and displays the results.

The GeneratePermutations function really just sets up and then calls PermuteItems to do the real work.

// Generate permutations.
private List> GeneratePermutations(List items)
{
    // Make an array to hold the
    // permutation we are building.
    T[] current_permutation = new T[items.Count];

    // Make an array to tell whether
    // an item is in the current selection.
    bool[] in_selection = new bool[items.Count];

    // Make a result list.
    List> results = new List>();

    // Build the combinations recursively.
    PermuteItems(items, in_selection,
        current_permutation, results, 0);

    // Return the results.
    return results;
}

This function creates arrays to hold the current permutation and flags to indicate which items are in the current permutation. It then calls PermuteItems, telling it to assign the first item.

The PermuteItems function does all of the work.

// Recursively permute the items that are
// not yet in the current selection.
private void PermuteItems(List items, bool[] in_selection,
    T[] current_permutation, List> results, int next_position)
{
    // See if all of the positions are filled.
    if (next_position == items.Count)
    {
        // All of the positioned are filled.
        // Save this permutation.
        results.Add(current_permutation.ToList());
    }
    else
    {
        // Try options for the next position.
        for (int i = 0; i < items.Count; i++)
        {
            if (!in_selection[i])
            {
                // Add this item to the current permutation.
                in_selection[i] = true;
                current_permutation[next_position] = items[i];

                // Recursively fill the remaining positions.
                PermuteItems(items, in_selection,
                    current_permutation, results, next_position + 1);

                // Remove the item from the current permutation.
                in_selection[i] = false;
            }
        }
    }
}

The function first checks whether the current permutation is full. If so, it adds the current permutation to the results and stops.

If the current permutation is not full, the code loops through the items. When it finds an item that is not yet in the permutation, the function adds that item and calls itself recursively to fill the rest of the permutation. When the recursive call returns, the function unmarks the item it added and continues looping through the remaining items.