MSDN Magazin > Home > Ausgaben > 2006 > December >  Testlauf: Zeichenfolgepermutationen
Testlauf
Zeichenfolgepermutationen
Dr. James McCaffrey

Codedownload verfügbar unter: TestRun2006_12.exe (161 KB)
Browse the Code Online
Die Fähigkeit zum programmgesteuerten Erstellen und Verwenden der Vertauschung (Permutation) von Zeichenfolgen ist eine grundlegende Voraussetzung für Softwaretests. Die Permutation von Zeichenfolgen ist eine Neuanordnung von mehreren Zeichenfolgen. Wenn Sie beispielsweise anfangs drei Zeichenfolgen haben (Apfel, Banane und Kirsche), sind sechs Permutationen möglich:
{ "apple", "banana", "cherry" }
{ "apple", "cherry", "banana" }
{ "banana", "apple", "cherry" }
{ "banana", "cherry", "apple" }
{ "cherry", "apple", "banana" }
{ "cherry", "banana", "apple" }
Eine typische Anwendung von Permutationen beim Testen von Software ist das Erstellen von Testfalldaten für Geräte-, API- und Modultests. Angenommen, Sie haben eine Methode, die drei Zeichenfolgen akzeptiert, und eine der Testfalleingaben lautet „Apfel“, „Banane“, „Kirsche“. In den meisten Situationen würden Sie mit den anderen Eingabepermutationen fünf zusätzliche Testfälle erstellen. Es gibt viele weitere Anwendungsmöglichkeiten für Permutationen in Softwaretests. Permutationen sind bei der Softwareentwicklung sogar so wichtig und so verbreitet, dass Fragen zu Permutationen zu den häufigsten Fragen bei Vorstellungsgesprächen für Testjobs bei Microsoft gehören.
Worauf dieser Artikel abzielt, zeigt sich am besten anhand einer Abbildung. Abbildung 1 zeigt die Ausführung eines Demo-Programms. (Der vollständige Quellcode für diese Demo ist im Download-Bereich dieses Artikels erhältlich.) Wie in der Ausgabe von Abbildung 1 zu sehen ist, sind die drei grundlegenden Fertigkeiten in Bezug auf Zeichenfolgepermutationen die Fähigkeit, die Anzahl der möglichen Permutationen für eine bestimmte Anzahl von Zeichenfolgen zu berechnen, die Fähigkeit, alle Permutationen zu erzeugen sowie die Fähigkeit, eine bestimmte Permutation zu erstellen.
Abbildung 1 Demo der Zeichenfolgekombinationen (Klicken Sie zum Vergrößern auf das Bild)
Da sich die Bezeichnungen für Permutationen zwischen den einzelnen Domänen unterscheiden, erfahren Sie zunächst einige Begriffe, die in diesem Artikel verwendet werden. Die Bezeichnung „Permutationselement“ bezieht sich auf einen geordneten Satz von Zeichenfolgen aus einem Ursprungssatz. „Atom“ ist eine der individuellen Zeichenfolgen in einem Permutationselement. Die „Permutationsordnung“ ist die Anzahl der Atome in einem Element. In diesem Artikel werden lexikografische Permutationen verwendet. Das bedeutet, dass das anfängliche Permutationselement, das sogenannte Identitätselement, Atome in der Reihenfolge des Wörterbuchs auflistet. Jedes Permutationselement ist also relativ zu den anderen Elementen angeordnet. Das heißt, es gibt ein separates Identitäts-Permutationselement, ein separates letztes Element, und jedes Element hat ein Vorgänger- und ein Nachfolgerelement (außer das erste Element, das keinen Vorgänger hat, und das letzte Element, das keinen Nachfolger hat). Der Begriff „Zeichenfolgepermutation“ schließlich bezeichnet ein Permutationselement, dessen Atome aus Zeichenfolgen bestehen. Dieser Begriff wird verwendet, da mathematische Permutationen der Ordnung n ganzzahlige Atome zwischen 0 und n-1 haben, wie z. B. { 0, 1, 2 }. Die Gesamtanzahl der Permutationselemente der Ordnung n ist n! (ausgesprochen „Fakultät n“). Bei vier Atomen ergibt sich folgende Gesamtanzahl von Permutationselementen:
   4! = 4 * 3 * 2 * 1 = 24
Der Grund dafür ist einfach zu verstehen. Als erstes Atom des Elements kann ein beliebiges der n Atome gewählt werden. Als Nächstes kann ein beliebiges der n-1 verbleibenden Atome gewählt werden, usw.
Permutationen sind eng mit Kombinationen verwandt und werden manchmal damit verwechselt. Zeichenfolgekombinationen sind Teilmengen eines anfänglichen Zeichenfolgesatzes, wobei die Reihenfolge keine Rolle spielt. Nehmen Sie als Beispiel den Zeichenfolgesatz, der aus Apfel, Banane und Kirsche besteht. Es gibt drei Kombinationselemente der Teilmenge k = 1:
    { "apple" }, { "banana" }, {"cherry" }
Es gibt drei Kombinationselemente der Teilmenge k = 2:
{ "apple", "banana" }
{ "apple", "cherry" }
{ "banana", "cherry" }
Und es gibt ein Kombinationselement mit der Teilmenge k = 3:
{ "apple", "banana", "cherry" }
Die Ausgabe des MSDN®Magazin vom Juli 2004 enthält einen Artikel zu Kombinationen, „Using Combinations to Improve Your Software Test Case Generation“ (in englischer Sprache).
Im weiteren Verlauf dieses Artikels lernen Sie das allgemeine Design von Zeichenfolgepermutations-Klassen kennen, einschließlich eines einfachen Konstruktors, und erfahren, wie alle möglichen Permutationselemente durch einen geradlinigen Algorithmus zur Erstellung des Nachfolgers eines bestimmten Permutationselements erzeugt werden können. Anschließend wird das Erstellen eines bestimmten Permutationselements mit einer Technik erläutert, die einen besonders eleganten Algorithmus verwendet. Sie lernen Techniken kennen, um zu bestimmen, wie viele Permutationselemente für einen anfänglichen Zeichenfolgesatz vorhanden sind. Den Abschluss bildet eine kurze Erläuterung der Anpassungs- und Erweiterungsmöglichkeiten der hier vorgestellten Codes und Algorithmen, mit denen Sie Ihre eigenen Anforderungen erfüllen können. Dieser Artikel erläutert verschiedene nützliche neue Tools, die die Fertigkeiten eines Entwicklers erweitern können.

Eine Zeichenfolgepermutations-Klasse
Zeichenfolgepermutationen sind ideal für die Implementierung mit objektorientierter Vorgehensweise geeignet, da Permutationen eng verwandte Daten (die Zeichenfolgenatome) und Code enthalten. Die allgemeine Struktur der Klassenbibliothek sehen Sie in Abbildung 2.
using System;
using System.Text;

namespace StringPermLib
{
  public class StringPerm
  {
    private string[] element;
    private int order;

    public StringPerm(string[] atoms) { ... }
    public StringPerm(string[] atoms, int k) { ... }

    public override string ToString() { ... }

    public static bool IsValid(string[] e) { ... }
    public StringPerm Successor() { ... }

    public static ulong FactorialCompute(int n) { ... }
    public static ulong FactorialLookup(int n) { ... }
    public static ulong FactorialRecursive(int n) { ... }
  }
}

Die Klasse wurde hier als „StringPerm“ bezeichnet, Sie können jedoch einen anderen Namen wählen. Die Klasse „StringPerm“ hat nur zwei Datenfelder, beide sind privat: ein Zeichenfolgen-Array (benanntes Element), das individuelle Atomzeichenfolgen für ein bestimmtes Zeichenfolge-Permutationselement enthält, und ein ganzzahliges Feld zum Speichern der Permutationsklassen-Ordnung. Es wurde kein Standardkonstruktor implementiert. Stattdessen ist ein Konstruktor enthalten, der ein Zeichenfolgen-Array als einzelnen Eingabeparameter akzeptiert und das Identitäts-Permutationselement erstellt:
public StringPerm(string[] atoms)
{
    if (atoms == null) throw new ArgumentNullException("atoms");
    if (!IsValid(atoms)) throw new ArgumentException("atoms");
    this.element = new string[atoms.Length];
    atoms.CopyTo(this.element, 0);
    this.order = atoms.Length;
}
Es wird einfach unter Verwendung der Methode „Array.CopyTo“ Speicherplatz für das Klassen-Array-Feld zugewiesen, um die einzelnen Werte zuzuordnen, und anschließend die Eigenschaft „Length“ (Länge) des Eingabearguments verwendet, um dem Feld mit der Reihenfolge einen Wert zuzuweisen. Dies ist ein einfacher, übersichtlicher Code zum Erstellen einer Klasse. Mit dem folgenden Codeausschnitt wird der Klassenkonstruktor aufgerufen:
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
StringPerm p = new StringPerm(atoms);
Da es sich um eine lexikografische Zeichenfolgepermutations-Klasse handelt, muss der Konstruktor ein sortiertes Zeichenfolgen-Array akzeptieren. Dazu wurde die statische Methode „IsValid“ zur Klasse hinzugefügt, die vom Konstruktor aufgerufen wird. Dies ist eine Möglichkeit zur Implementierung von „IsValid“:
public static bool IsValid(string[] e)
{
    if (e == null) return false;
    if (e.Length < 2) return false;
    for (int i = 0; i < e.Length - 1; ++i)
    {
        if (e[i].CompareTo(e[i + 1]) >= 0) return false;
    }
    return true;
}
Diese Methode akzeptiert ein Zeichenfolgen-Array und gibt „true“ als Eingabeargument an den StringPerm-Konstruktor zurück, wenn das Array gültig ist, andernfalls „false“. Das Eingabe-Array darf nicht Null sein und muss mindestens zwei Zellen enthalten. Sie können diesen Teil des Codes ändern, um eine Zeichenfolgepermutation der Ordnung 1 zu ermöglichen. Anschließend wird die Methode „String.CompareTo“ verwendet, um sicherzustellen, dass jedes Zeichenfolgenatom im Eingabe-Array geringer als der Nachfolger ist. Anders gesagt, die Zeichenfolgenatome müssen in der richtigen Reihenfolge vorliegen und dürfen nicht doppelt vorkommen. Hier wird umgekehrte Logik verwendet und „false“ zurückgegeben, wenn das Zeichenfolgenatom an der Indexposition i größer als oder gleich dem Zeichenfolgenatom am Index i+1 ist. Sie können doppelte Werte auch zulassen, wie im folgenden Array:
{ "ant", "bat",
 "bat", "cow" }
Dazu ändern Sie den Operator >= in >.
Es ist auch eine Hilfsmethode „ToString“ zu empfehlen. Hier eine Möglichkeit:
public override string ToString()
{
    StringBuilder result = new StringBuilder();
    result.Append("{ ");
    for (int i = 0; i < this.order; ++i)
    {
        result.Append(this.element[i]);
        result.Append(" ");
    }
    result.Append("}");
    return result;
}
Dabei wird lediglich eine Ergebniszeichenfolge durch Verkettung der einzelnen Atome, getrennt durch ein Leerzeichen, erstellt und in geschweifte Klammern eingeschlossen.

Erstellen von allen Permutationen der Ordnung n
Eine Vorgehensweise zum Erstellen von allen Zeichenfolgepermutationen ist das Schreiben einer Successor-Methode, die das nächste lexikografische Zeichenfolgepermutations-Element für ein bestimmtes Element zurückgibt. Dies ist ein interessantes Problem mit einer eleganten Lösung. Der Algorithmus zum Suchen des Nachfolgers (Successor) eines Permutationselements bestimmt die Positionen zweier Atome, tauscht die beiden Atome aus und kehrt dann die Reihenfolge der Atome am rechten Ende um. Am besten lässt sich dies an einem Beispiel erläutern. Angenommen, Sie arbeiten mit einer Zeichenfolgepermutation von Ziffern, und dies ist das aktuelle Permutationselement:
{ "1" "3" "5" "4" "2" "0" }
Dies ist das Nachfolgerelement:
{ "1" "4" "0" "2" "3" "5" }
Zuerst suchen Sie einen linken und einen rechten Index, die auf zwei Atome verweisen, die getauscht werden. Um den linken Index festzustellen, beginnen Sie beim vorletzten Atom (in diesem Beispiel 2) und gehen nach links, bis Sie auf ein Atom treffen, das kleiner als das aktuelle Atom ist. In diesem Beispiel gehen Sie nach links, bis Sie Atom 3 erreichen, da 3 kleiner als 5 ist. Der linke Index ist also [1]. Um den rechten Index festzustellen, beginnen Sie bei dem am weitesten rechts stehenden Atom (in diesem Fall 0) und gehen nach links, bis Sie auf ein Atom treffen, das größer als das Atom am linken Index ist. Im Beispiel gehen Sie nach links, bis Sie Atom 4 erreichen. Der rechte Index ist also [3]. Vertauschen Sie nun die Atome am linken und rechten Index ([1] und [3]). Sie erhalten folgendes Ergebnis:
{ "1" "4" "5" "3" "2" "0" }
Abschließend kehren Sie alle Atome rechts vom linken Index um, in diesem Fall alle Atome rechts von [1], also 5, 3, 2 und 0. So lautet das endgültige Ergebnis für den Nachfolger:
{ "1" "4" "0" "2" "3" "5" }
Der Code zur Implementierung dieses Algorithmus ist in Abbildung 3 dargestellt.
public StringPerm Successor()
{
  StringPerm result = new StringPerm(this.element);
  int left, right;

  // Step #1 - Find left value 
  left = result.order - 2;  
  while ((result.element[left].CompareTo(result.element[left + 1])) >= 0
         && (left >= 1))
  {
    --left;
  }
  if ((left == 0) &&
      (this.element[left].CompareTo(this.element[left + 1])) >= 0)
  {
    return null;
  }

  // Step #2 - find right; first value > left
  right = result.order - 1;
  while (result.element[left].CompareTo(result.element[right]) >= 0)
  {
    --right;
  }

  // Step #3 - swap [left] and [right]
  string temp = result.element[left];
  result.element[left] = result.element[right];
  result.element[right] = temp;

  // Step #4 - reverse order the tail
  int i = left + 1;        
  int j = result.order - 1;
  while (i < j)
  {
    temp = result.element[i];
    result.element[i++] = result.element[j];
    result.element[j--] = temp;
  }

  return result;
}

Diese Successor-Methode gilt nur für Permutationen ohne doppelte Atome. Etwas schwieriger wird es, wenn Sie bestimmen wollen, was mit dem letzten Permutationselement passiert. Angenommen, Sie arbeiten mit dem folgenden Element:
{ "ant", "bat", "cow", "dog" }
Das letzte Permutationselement lautet so:
{ "dog", "cow", "bat", "ant" }
Es gibt verschiedene Möglichkeiten für diese Situation. Wenn der Wert des linken Index im Successor-Code bestimmt wird, der linke Index den Wert 0 hat und das Atom von [0] größer ist als das Atom von [1], ist das letzte Permutationselement erreicht. In diesem Fall wird Null zurückgegeben. Alternativ dazu kann auch das (erste) Identitätselement zurückgegeben werden (wobei man wieder an den Beginn der Permutationssequenz gelangt) oder eine Ausnahme ausgegeben werden.
Mit dieser Successor-Methode können Sie einfach eine einzelne Nachfolgerpermutation für ein bestimmtes Permutationselement erzeugen oder alle Permutationselemente erstellen (falls keine doppelten Atome vorhanden sind). Gehen Sie dabei folgendermaßen vor:
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
Console.WriteLine("In lexicographical order, all permutations are:\n");
for(StringPerm p = new StringPerm(atoms); p != null; p = p.Successor())
{
  Console.WriteLine(p.ToString());
}
In diesem Algorithmus können Probleme bei doppelten Zeichenfolgenatomen auftreten. Wie bereits erwähnt, lässt dieser Code keine Duplikate zu. Wenn Sie jedoch doppelte Atome in den Permutationselementen zulassen möchten, können Sie zuerst die Hilfsmethode „IsValid“ anpassen, wie im vorherigen Abschnitt beschrieben. Um dann alle Permutationselemente mit Duplikaten zu erzeugen, müssen Sie eine andere Methode verwenden, z. B. die, die im folgenden Abschnitt vorgestellt wird.

Bestimmen eines speziellen Permutationselements
Angenommen, Sie möchten nur ein bestimmtes Zeichenfolge-Permutationselement erstellen. Sie haben beispielsweise die Zeichenfolgen „ant“, „bat“, „cow“ und „dog“ und möchten nur Element [13], also:
{ "cow" "ant" "dog" "bat" }
Zunächst sieht die Lösung ganz einfach aus: starten Sie einfach mit einem Identitäts-Permutationselement, und rufen Sie anschließend die Methode „Successor“ aus dem vorherigen Abschnitt 13-mal auf. Doch was, wenn Sie statt mit 4 mit 20 Zeichenfolgenatomen arbeiten? In diesem Fall gibt es 2.432.902.008.176.640.000 Permutationselemente! Und Sie benötigen nur Element [999.999.999.999]. Bei einem Test mit der Schleifenmethode ließ die Antwort auf einem Desktopcomputer mehr als 24 Stunden auf sich warten. Außerdem funktioniert die Schleifenmethode zum Erstellen aller Permutationselemente nicht, wenn Sie doppelte Atome zulassen. Es gibt jedoch einen Algorithmus, mit dem der Computer die Antwort in weniger als einer Sekunde findet, selbst wenn Atomduplikate zugelassen sind.
Dieser Algorithmus, der ein bestimmtes Permutationselement direkt berechnet, basiert auf einer mathematischen Konstruktion, der so genannten Faktoriellen. Eine Faktorielle ist eine alternative Darstellung einer Ganzzahl. Die Faktorielle wird aus dem gewünschten Indexwert berechnet und anschließend in ein Permutationselement umgewandelt.
Nachfolgend finden Sie eine Erläuterung einer Faktoriellen. Nehmen Sie die Zahl 859. Wenn Sie die Ordnung auf n = 7 setzen, wird die Zahl 859 wie folgt dargestellt:
(6! * 1) + (5! * 1) + (4! * 0) + 
(3! * 3) + (2! * 0) + (1! * 1) + (0! * 0)

= 720 + 120 + 0 + 18 + 0 + 1

= 859
Die Faktorielle von 859 ist also [1 1 0 3 0 1 0]. Jede beliebige Zahl kann als Faktorielle mit einer bestimmten Folge dargestellt werden. Der Vorteil ist, dass es eine Eins-zu-Eins-Zuordnung zwischen Faktoriellen und Permutationselementen gibt. Ein Beispiel für Permutationen der Ordnung 4 sehen Sie in Abbildung 4: die Beziehung zwischen einer Ganzzahl, der Faktoriellen und der entsprechenden mathematischen Permutation.
index  factoradic    permutation
=================================
0      [ 0 0 0 0 ]   { 0 1 2 3 } 
1      [ 0 0 1 0 ]   { 0 1 3 2 } 
2      [ 0 1 0 0 ]   { 0 2 1 3 } 
3      [ 0 1 1 0 ]   { 0 2 3 1 } 
4      [ 0 2 0 0 ]   { 0 3 1 2 } 
5      [ 0 2 1 0 ]   { 0 3 2 1 } 
6      [ 1 0 0 0 ]   { 1 0 2 3 } 
7      [ 1 0 1 0 ]   { 1 0 3 2 } 
8      [ 1 1 0 0 ]   { 1 2 0 3 } 
9      [ 1 1 1 0 ]   { 1 2 3 0 } 
10     [ 1 2 0 0 ]   { 1 3 0 2 } 
11     [ 1 2 1 0 ]   { 1 3 2 0 } 
12     [ 2 0 0 0 ]   { 2 0 1 3 } 
13     [ 2 0 1 0 ]   { 2 0 3 1 } 
14     [ 2 1 0 0 ]   { 2 1 0 3 } 
15     [ 2 1 1 0 ]   { 2 1 3 0 } 
16     [ 2 2 0 0 ]   { 2 3 0 1 } 
17     [ 2 2 1 0 ]   { 2 3 1 0 } 
18     [ 3 0 0 0 ]   { 3 0 1 2 } 
19     [ 3 0 1 0 ]   { 3 0 2 1 } 
20     [ 3 1 0 0 ]   { 3 1 0 2 } 
21     [ 3 1 1 0 ]   { 3 1 2 0 } 
22     [ 3 2 0 0 ]   { 3 2 0 1 } 
23     [ 3 2 1 0 ]   { 3 2 1 0 }

Hier kommt ein weiteres Beispiel. Angenommen, Sie haben die vier Zeichenfolgenatome „ant“, „bat“, „cow“ und „dog“, und Sie möchten die Permutation [13] direkt berechnen. Bestimmen Sie zuerst die Faktorielle von 13, also [2 0 1 0], und ordnen Sie dann diese Faktorielle der entsprechenden mathematischen Permutation zu, in diesem Fall { 2 0 3 1 }. Anschließend ordnen Sie die Permutation den anfänglichen Zeichenfolgenatomen zu:
{ "cow", "ant", "dog", "bat" }
Eine ausführliche Beschreibung der Faktoriellen überschreitet den Umfang dieses Artikels. Sie finden jedoch ein Kapitel zu diesem Thema in meinem Buch .NET Test Automation Recipes (Apress, 2006) sowie im Internet.
Die Teilroutine zum Bestimmen eines bestimmten Permutationselements wurde als Hilfskonstruktor implementiert. Der Code wird in Abbildung 5 gezeigt. Mit dem Konstruktor aus Abbildung 5 können Sie beispielsweise Folgendes aufrufen:
string[] atoms = new string[] { "ant", "bat", "cow", "dog" };
Console.WriteLine("\nJust element [13] computed directly is:");
p = new StringPerm(atoms, 13);
Console.WriteLine("     " + p.ToString());
public StringPerm(string[] atoms, int k)
{
  this.element = new string[atoms.Length];
  this.order = atoms.Length;

  // Step #1 - Find factoradic of k
  int[] factoradic = new int[this.order];
  for (int j = 1; j <= this.order; ++j)
  {
    factoradic[this.order - j] = k % j;
    k /= j;
  }

  // Step #2 - Convert factoradic[] to numeric permuatation in perm[]
  int[] temp = new int[this.order];
  int[] perm = new int[this.order];
  for (int i = 0; i < this.order; ++i)
  {
    temp[i] = ++factoradic[i];
  }
  perm[this.order - 1] = 1;  // right-most value is set to 1.
  for (int i = this.order - 2; i >= 0; --i)
  {
    perm[i] = temp[i];
    for (int j = i + 1; j < this.order; ++j)
    {
      if (perm[j] >= perm[i]) ++perm[j];
    }
  }
  for (int i = 0; i < this.order; ++i)  // put in 0-based form
    --perm[i];

  // Step #3 - map numeric permutation to string permutation
  for (int i = 0; i < this.order; ++i)
    this.element[i] = atoms[perm[i]];

}

Dieser Konstruktor ermöglicht Ihnen außerdem, alle Permutationselemente zu erstellen, unabhängig davon, ob sie doppelte Atome enthalten. Sehen Sie sich beispielsweise folgenden Code an:
string[] atoms = new string[] { "ant", "bat", "cow", "cow" };
StringPerm p = null;
Console.WriteLine("All permutations are:\n");
for (int k = 0; (ulong)k < StringPerm.FactorialLookup(4); ++k)
{
  p = new StringPerm(atoms, k);
  Console.WriteLine(k + " " + p.ToString());
}
Mit dieser Vorgehensweise werden doppelte Permutationselemente erzeugt. Falls Sie ausschließlich eindeutige Elemente wünschen, können Sie verschiedene Methoden anwenden. Beispielsweise können Sie alle Elemente in eine Hashtabelle laden und vor jeder Hinzufüge-Operation auf Duplikate überprüfen lassen.

Die Anzahl der Permutationselemente der Ordnung n
Das Berechnen der Gesamtanzahl von Zeichenfolge-Permutationselementen für einen bestimmten Zeichenfolgesatz ist gleichzeitig schwierig und einfach. Angenommen, Sie haben die Zeichenfolgen „ant“, „bat“, „cow“ und „dog“ und die Ordnung ist n = 4. Es gibt insgesamt 24 Permutationselemente, wie in Abbildung 1 gezeigt. Jedes beliebige Element kann einen der vier Zeichenfolgenatome in der ersten Position (am weitesten links) haben, dann eines der verbleibenden drei Atome an der nächsten Position, eines der verbleibenden zwei Atome wiederum an der nächsten Position und schließlich das letzte verbleibende Atom an der letzten Position. Anders ausgedrückt, für n = 4 gibt es 4 * 3 * 2 * 1 = 24 Permutationselemente. Sie erkennen dies sicher als die Formel für die Fakultät n (häufig als n! geschrieben). Deshalb ist die Gesamtanzahl der Zeichenfolge-Permutationselemente der Ordnung n gleich der Fakultät von n. Man könnte meinen, das ist ein recht einfaches Problem, oder? Nicht unbedingt. Es gibt drei unterschiedliche Implementierungen einer faktoriellen Methode.
Eine Herangehensweise, die häufig von Studienabgängern verwendet wird, ist das Schreiben einer faktoriellen Methode unter Verwendung von Rekursion. Beispiel:
public static ulong FactorialRecursive(int n)
{
  if (n < 0) throw new ArgumentOutOfRangeException("n");
  if (n == 0 || n == 1) return 1;
  else return (ulong)n * FactorialRecursive(n - 1);
}
Dies ist meist nicht empfehlenswert, und kann im schlimmsten Fall die falsche Antwort liefern. Der Wert von n! wird sehr schnell sehr groß. Beispielsweise sieht der Wert von 64! etwa wie folgt aus:
126,886,932,100,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000
Genau genommen ist der größte Wert, der durch eine Variable vom Typ „ulong“ gespeichert werden kann, lediglich 20! und sieht so aus:
20 * 19 * 18 *. .. * 2 * 1 = 2,432,902,008,176,640,000
Was würde passieren, wenn Sie
ulong result = FactorialRecursive(21)
in einem Programm aufrufen? Man würde einen arithmetischen Überlauf erwarten, aber in der Regel geschieht das nicht. Der Compiler erreicht „ulong.MaxValue“ (der bei 18.446.744.073.709.551.615 liegt) und beginnt dann wieder von vorn bei 0, ohne eine Warnung auszugeben. CLR kann Überlauf und Unterlauf von numerischen Operationen überprüfen – Sie können diese Funktion beim Kompilieren aktivieren. Zusätzlich zu diesem Problem gibt es keinen wirklichen guten Grund für die Verwendung einer rekursiven Lösung. Ein zweiter Versuch einer faktoriellen Methode ist die iterative Berechnung der Antwort, in etwa so:
public static ulong FactorialCompute(int n)
{
  if (n < 0 || n > 20)
      throw new Exception("Input argument must be between 0 and 20");
  ulong answer = 1;
  for (int i = 1; i <= n; ++i) answer = checked(answer * (ulong)i);
  return answer;
}
Dies ist in den meisten Fällen weitaus besser. Diese Methode überprüft die Eingabeparameter und verwendet das überprüfte C#-Schlüsselwort, das eine Laufzeitausnahme zurückgibt, wenn der arithmetische Überlauf erfolgt. Da die Anzahl der Eingabeargumente jedoch recht niedrig ist (0 bis 20), können Sie die 21 möglichen Ergebnisse in einer Suchtabelle speichern, um etwa folgende Lösung zu erhalten:
public static ulong FactorialLookup(int n)
{
  if (n < 0 || n > 20)
    throw new Exception("Input argument must be between 0 and 20");
  ulong[] answers = new ulong[] { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
    362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
    1307674368000, 20922789888000, 355687428096000, 6402373705728000,
    121645100408832000, 2432902008176640000 };
  return answers[n];
}
In den meisten Testszenarios für Software ist die Suche die effizienteste Herangehensweise. Natürlich bieten diese verschiedenen Möglichkeiten zur Implementierung einer faktoriellen Methode nur einen groben Überblick über diese Teilroutine.

Zusammenfassung
Zeichenfolgepermutationen können auf verschiedene Arten verwendet werden. Angenommen, Sie testen ein Software-Einrichtungsprogramm und möchten die Auswirkung der Installationsreihenfolge von drei zusätzlichen, aber zusammengehörigen Programmen ermitteln. Ihr Softwareprogramm heißt „A“, die anderen drei Programme „B“, „C“ und „D“. Mit den Techniken in diesem Artikel können Sie ganz einfach bestimmen, dass es 24 Installationsreihenfolgen gibt und diese Permutationen problemlos erstellen. Aber was passiert, wenn es 19 zugehörige Programme gibt? Sie werden feststellen, dass 20! Installationsreihenfolgen zu viel zum Testen sind, und müssen Prioritäten festlegen.
Zusammenfassend kann man sagen, Zeichenfolgepermutationen sind Neuanordnungen von mehreren Zeichenfolgen. Das Verständnis und die Verwendung von Zeichenfolgepermutationen ist eine grundlegende Fähigkeit´ für Softwaretester. Insbesondere sollten alle Tester wissen, wie sie berechnen können, wie viele Permutationselemente es für einen bestimmten Anfangssatz von Zeichenfolgen gibt, wie sie alle möglichen Permutationselemente erzeugen können und wie sie effizient ein bestimmtes Permutationselement erstellen. In diesem Artikel haben Sie erfahren, wie Sie genau diese Aufgaben durchführen können. Der hier dargestellte Code kann unverändert verwendet und an die jeweiligen Anforderungen angepasst werden.

Schicken Sie Ihre Fragen und Kommentare in englischer Sprache an Dr. James McCaffrey unter testrun@microsoft.com.


Dr. James McCaffrey arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler von Microsoft organisiert. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem Internet Explorer und MSN Search. James ist der Autor von „.NET Test Automation Recipes“ (Apress, 2006). Sie erreichen ihn unter jmccaffrey@volt.com oder v-jammc@microsoft.com.

Page view tracker