Sonntag, 18. Mai 2014

Alle Permutationen erzeugen

Oft musste ich beim Programmieren alle Permutationen einer bestimmten Menge finden und ausgeben. Deshalb möchte ich heute eine, wie ich finde, schnelle und elegante Methode dafür vorstellen.
Diese erwartet als Parameter eine Liste von int Werten, und gibt dann alle möglichen Permutationen dieser aus. Der Parameter int der Liste lässt sich aber durch einen beliebigen anderen Datentyp ersetzen.
Das Erzeugen der Permutationen funktioniert rekursiv. Der aktuell erzeugte Teil der Permutation wird als Liste gespeichert, in jedem Schritt wird dieser ein Element hinzugefügt und dieses aus der Liste der verbleibenden Elemente entfernt. Sind keine Elemente mehr vorhanden, wird die aktuelle Liste in die Liste der fertigen Permutationen aufgenommen.
Der Code für diese Funktion sieht so aus:

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);
    }
}
Wie man sieht, wird jeweils eine Funktion Copy() aufgerufen. Das ist deshalb nötig, weil Listen in C# Verweistypen sind (für eine genaue Erklärung siehe hier) - so würde das Ändern der Liste in einem Aufruf auch die Liste in allen anderen Aufrufen mit dieser Liste ändern.
Der komplette Code sollte selbsterklärend sein und sieht so aus:

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);
            }
        }
    }
}

Kommentare:

  1. coll. danke für de tipp

    AntwortenLöschen
  2. Der Kommentar wurde von einem Blog-Administrator entfernt.

    AntwortenLöschen
  3. Der Kommentar wurde von einem Blog-Administrator entfernt.

    AntwortenLöschen
  4. Anstatt der Funktion "Copy" kann auch einfach der Copy-Constructor genommen werden ;)

    (List NewCurrent = new List(current);)

    AntwortenLöschen