This example is somewhat similar to Generate all of the permutations of a set of objects in C#. The basic idea is to use a recursive routine to assign the next item to the combination. The first call to the routine assigns the combination's first item, the next call assigns the second item, and so forth until the combination is complete.

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:

• 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 recursion continues until the combination contains the right number of items. Then the function reads the items that are selected in the current combination and adds them to the list of results.

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 and N.
    string[] items = txtItems.Text.Split(' ');
    int n = int.Parse(txtNumPerSelection.Text);

    // Generate the selections.
    List> results =
        GenerateSelections(items.ToList(), n);

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

    // Calculate the number of items.
    decimal num_combinations = NChooseK(items.Length, n);
    txtNumCombinations.Text = num_combinations.ToString();

    // Check the result.
    Debug.Assert(lstCombinations.Items.Count == num_combinations);
}

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

It also calls function NChooseK to display the number of combinations. For a description of that function, see Calculate the binomial coefficient "N choose K" efficiently in C#.

The GenerateSelections function really just sets up and then calls SelectItems to do the real work.

// Generate selections of n items.
private List> GenerateSelections(List items, int n)
{
    // 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.
    SelectItems(items, in_selection, results, n, 0);

    // Return the results.
    return results;
}

This function creates an array to indicate which items are in the current selection. It then calls SelectItems, telling it how many items it needs to add to each selection.

The SelectItems function does all of the work.

// Recursively select n additional items with indexes >= first_item.
// If n == 0, add the current combination to the results.
private void SelectItems(List items, bool[] in_selection,
    List> results, int n, int first_item)
{
    if (n == 0)
    {
        // Add the current selection to the results.
        List selection = new List();
        for (int i = 0; i < items.Count; i++)
        {
            // If this item is selected, add it to the selection.
            if (in_selection[i]) selection.Add(items[i]);
        }
        results.Add(selection);
    }
    else
    {
        // Try adding each of the remaining items.
        for (int i = first_item; i < items.Count; i++)
        {
            // Try adding this item.
            in_selection[i] = true;

            // Recursively add the rest of the required items.
            SelectItems(items, in_selection, results, n - 1, i + 1);

            // Remove this item from the selection.
            in_selection[i] = false;
        }
    }
}

The function first checks whether the current selection needs more items. If it does not, it adds the current permutation to the results and returns.

If the current selection needs more items, 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 selection. When the recursive call returns, the function unmarks the item it added and continues looping through the remaining items.