Generate all of the permutations of a set of objects in C#

example

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

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

  • 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 method unmarks the item so it is not used and can be used again later.

The methods used by this program are generic. In this example, they use strings because strings are easy to enter on the form, but you can use the same methods to permute other kinds of 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<List<string>> results =
        GeneratePermutations<string>(items.ToList());

    // Display the results.
    lstPermutations.Items.Clear();
    foreach (List<string> 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 the GeneratePermutations method to build the permutations and then displays the results.

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

// Generate permutations.
private List<List<T>> GeneratePermutations<T>(List<T> 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<List<T>> results = new List<List<T>>();

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

    // Return the results.
    return results;
}

This method creates an array to hold the current permutation and an array of flags to indicate which items are in the current permutation. It then calls the PermuteItems method, telling it to assign the first item. The PermuteItems method, which is shown in the following code, does all of the interesting work.

// Recursively permute the items that are
// not yet in the current selection.
private void PermuteItems<T>(List<T> items, bool[] in_selection,
    T[] current_permutation, List<List<T>> 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<T>(items, in_selection,
                    current_permutation, results,
                    next_position + 1);

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

This method first checks whether the current permutation is full. If so, it adds the current permutation to the results list and returns.

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 method adds that item to the permutation and calls itself recursively to fill in the rest of the permutation. When the recursive call returns, the method unmarks the item it added and continues looping through the remaining items.


Download Example   Follow me on Twitter   RSS feed




This entry was posted in algorithms, combinatorics, mathematics, recursion and tagged , , , , , , , , , , . Bookmark the permalink.

10 Responses to Generate all of the permutations of a set of objects in C#

  1. That was an important editorial. I stumbled across your article and thought it exceptionally effective.

  2. Pingback: Generate all selections of K items from a set of N items in C#

  3. HarveySinc says:

    I thought about this at first too but then the current element wouldn t get put in between some of the following. So not all permutations would be generated.

    • RodStephens says:

      I don’t think I understand your comment. This method does generate all of the permutations. For example, in the picture above you can see that it generates 120 permutations of 5 items and 5! = 5×4×3×2×1 = 120.

      It could be the last step. After the recursion returns, the method must unmark the correct item as being used so it can be used in later recursions.

  4. Frixum says:

    This program will print all possible permutations, what if position size is less than whole population size ? for example 4 students and 3 chairs..

    like we want to arrange ABCD with position size 3.
    ABC
    ABD
    ACD
    ACB and so on .. Please suggest.

  5. App Coder says:

    Can you make another version for combination without repetition please. Where Ape Bear Cat Elf Dog are all the option enter and in another textbox it would request to enter the set amount of items to combine 3 or 4 for all Ape Bear Cat Elf Dog. Output in a dataGridView and save-as .csv if possible.

  6. Allan says:

    Hi

    Great work. really helped me a lot.

    But…
    What if i want all possible ways to put these together?
    If i have ABC and i want this to give me:
    ABC
    ACB
    BAC
    BCA
    CAB
    CBA
    AB
    AC
    BA
    BC
    CA
    CB
    A
    B
    C

    How would i do that?

    Hope you can give me some help here, i have been trying to do this for days now.

Leave a Reply

Your email address will not be published. Required fields are marked *