Sunday, May 18, 2014

Create All Permutations

When programming I often had to find all permutations of a given set. Therefore today I want to present a, in my opinion, fast and elegant method for this.
This expects as a parameter a list of int values and then outputs all possible permutations of it. But the parameter of the int list can be replaced by any other data type.
The creation of the permutations works recursively. The part of the permutation created so far is saved in a list, in every step one element is added to this and removed from the list of remaining elements. If no elements are available any more, the current list is saved in the list of complete permutations.
The code for the function looks as follows:

public void RecCreatePermutation(List<int> current, List<int> elements)
{
    for (int i = 0; i < elements.Count; i++)
    {
        List<int> NewCurrent = Copy(current);
        List<int> NewElements = Copy(elements);
        NewCurrent.Add(elements[i]);
        NewElements.RemoveAt(i);
        if (NewElements.Count == 0)
        {
            Permutations.Add(NewCurrent);
        }
        else
            RecCreatePermutation(NewCurrent, NewElements);
    }
}
As you can see, in each step the function Copy() is called. This is necessary because lists are reference types in C# (for an explanation click here) - so changing a list in one call would change that list in all other calls.
The complete code should be self explanatory and looks as follows:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CreatePermutations
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            List<int> Elements = new List<int>();
            for (int i = 0; i < 5; i++)
            {
                Elements.Add(i);

            }
           List<List<int>> Perms = CreatePermutation(Elements);
        }

        List<List<int>> Permutations;
        public List<List<int>> CreatePermutation(List<int> elements)
        {
            Permutations = new List<List<int>>();
            RecCreatePermutation(new List<int>(), elements);
            return Permutations;
        }

        private List<int> Copy(List<int> dummy)
        {
            List<int> Result = new List<int>();
            foreach (int i in dummy)
                Result.Add(i);
            return Result;
        }

        public void RecCreatePermutation(List<int> current, List<int> elements)
        {
            for (int i = 0; i < elements.Count; i++)
            {
                List<int> NewCurrent = Copy(current);
                List<int> NewElements = Copy(elements);
                NewCurrent.Add(elements[i]);
                NewElements.RemoveAt(i);
                if (NewElements.Count == 0)
                {
                    Permutations.Add(NewCurrent);
                }
                else
                    RecCreatePermutation(NewCurrent, NewElements);
            }
        }
    }
}

No comments:

Post a Comment