Permutation von n Elementen
Ist eine Menge von n Elementen gegeben, so bezeichnet man die möglichen Anordnungen aller dieser n Elemente als Permutationen.
Sind alle n Elemente voneinander verschieden, so gibt es dafür n! Anordnungen.
Beispiel:
Menge= {a, b, c}
mögliche Anordnungen: abc, bac, acb, cab, cba, bca
Anwendungen:
+ Problem des Handlungsreisenden
+ Kostenoptimierungen bei der Leiterplattenherstellung
+ Kennzeichnung von Wanderwegen
+ Probleme der Wahrscheinlichkeitsrechnung
Gesucht ist ein Programm, das zu einer gegebenen Menge alle Permutationen erzeugt und ausgibt!
Entwurf (verbal):
1. Fall: n=1
Die Menge hat nur ein Element. Die Permutation des Elementes a[1] ist zu ermitteln. Das ist das Element selbst. Die Lösung ist gefunden und wird ausgegeben.
2. Fall: n>1
Alle Permutationen der Elemente a[1], a[2], a[3], ... , a[n-1], a[n] sind zu ermitteln.
Dazu wird jedes Element auf die letzte Position getauscht.
Die davor liegenden n-1 Elemente werden permutiert.
Das Rücktauschen der Elemente ist nach dem rekursiven Aufruf der Methode notwendig.
Quelltext:
public class Permutationen
{
static char[] a;
/* Feld von Elementen, die zu permutieren sind. */
static int p,anzahl;
/* p zaehlt die Anzahl der Permutationen anzahl haelt die Elemente der Menge fest.*/
static void ausgabe(int anzahl)
{
for (int k=1; k<=anzahl; k=k+1)
System.out.print(a[k]+" ");
System.out.println();
} // Ende der Ausgabe
static void perm (int n)
{
char hilf;
if (n == 1)
{
ausgabe(anzahl);
p = p+1;
}
else
{
for (int k=n; k>=1; k=k-1)
{
// Tausche von a[k] und a[n]
hilf=a[k];
a[k]=a[n];
a[n]=hilf;
perm (n-1);
// Ruecktausch von a[k] und a[n]
hilf=a[k];
a[k]=a[n];
a[n]=hilf;
} // Ende der Zaehlschleife
} // Ende der Verzweigung
} // Ende der Methode perm
public static void main(String[] args)
{
p = 0;
String eingabe;
System.out.println (" Bitte Zeichenkette eingeben: ");
eingabe=In.readString();
anzahl=eingabe.length();
a = new char[anzahl+1];
for (int i=1; i<=anzahl; i=i+1)
{
a[i] = eingabe.charAt(i);
}
perm (anzahl);
System.out.println();
System.out.println();
System.out.println( p+ " Permutationen");
} // Ende der Hauptprogrammes
} // Ende der Klasse