C# Implementierung von Heaps Algorithmus funktioniert nicht

Question

Ich habe versucht, eine Implementierung von Heaps Algorithmus in C# schreiben, die nicht richtig funktioniert. Ich versuche, eine Allzweck-Implementierung zu erstellen, die alle Permutationen einer Zeichenfolge findet und sie zu einer Liste hinzufügt.

Ich fange wie folgt aus:

List<string> permutations = new List<string>(); 
GenerateHeapPermutations(3, "ABC", permutations); 

foreach (var p in permutations) 
{ 
    Console.WriteLine(p); 
} 

Console.ReadKey(); 

Und hier ist meine Implementierung:

public static void GenerateHeapPermutations(int n, string s, List<string> sList) 
{ 
    if (n == 1) 
    { 
     sList.Add(s); 
    } 
    else 
    { 
     for (int i = 0; i < n - 1; i++) 
     { 
      GenerateHeapPermutations(n - 1, s, sList); 

      if (n % 2 == 0) 
      { 
       // swap the positions of two characters 
       var charArray = s.ToCharArray(); 
       var temp = charArray[i]; 
       charArray[i] = charArray[n - 1]; 
       charArray[n - 1] = temp; 
       s = new String(charArray); 
      } 
      else 
      { 
       var charArray = s.ToCharArray(); 
       var temp = charArray[0]; 
       charArray[0] = charArray[n - 1]; 
       charArray[n - 1] = temp; 
       s = new String(charArray); 
      } 
     } 

     GenerateHeapPermutations(n - 1, s, sList); 
    } 
} 

Der Algorithmus hat die richtige Anzahl von Permutationen ergeben (in diesem Fall sechs), aber die Permutationen selbst sind falsch:

ABC  BAC  CBA    
BCA  ABC  BAC 

Ich glaube nicht, dass ich von derabweichen, und ich habe es schwer, dies aufgrund der rekursiven Natur dieses Algorithmus zu debuggen (ziemlich schwierig zu konzipieren).

Kann jemand einen Einblick geben, was das Problem sein könnte?

^{P.S. Keine Hausaufgaben, nur zum Spaß.}

Answer 1

Erste Dinge zuerst: Debugging. Wenn Sie sich mit Rekursion beschäftigen, besteht die einfachste Möglichkeit, Ihren Code zu debuggen, darin, Breakpunkte in Ihrer IDE zu setzen und schrittweise zu durchlaufen, indem Sie notieren, dass sich der Code verhält, wie Sie es erwarten. Auf diese Weise können Sie die Werte Ihrer Variablen bei jedem Schritt überprüfen.

Sie werden feststellen, dass das Übergeben der Zeichenfolge überall nicht zu dem führt, was Sie erwarten, weil Sie eine Kopie davon anstelle des tatsächlichen Werts übergeben. Wenn Sie stattdessen als Referenz übergeben werden (nicht sicher, ob C# dies zulässt), werden Sie das tun, was Sie erwarten.

Answer 2

Ihr Algorithmus basiert auf der Übergabe string anstelle des tatsächlichen Array. Bei der Übergabe string wird eine Kopie des Strings erstellt, wodurch die Änderung des kopierten Strings die tatsächliche Zeichenfolge, die übergeben wird, nicht ändert.

Bei der Änderung von string zu char array ist das Problem gelöst.

public static void Main() 
{ 
    List<string> permutations = new List<string>(); 
    GenerateHeapPermutations(3, new [] { 'A', 'B', 'C' }, permutations); 

    foreach (var p in permutations) 
    { 
     Console.WriteLine(p); 
    } 

    Console.ReadKey(); 
} 

public static void GenerateHeapPermutations(int n, char[] charArray, List<string> sList) 
{ 
    if (n == 1) 
    { 
     sList.Add(new string(charArray)); 
    } 
    else 
    { 
     for (int i = 0; i < n - 1; i++) 
     { 
      GenerateHeapPermutations(n - 1, charArray, sList); 

      int indexToSwapWithLast = (n%2 == 0 ? i : 0); 
      // swap the positions of two characters 
      var temp = charArray[indexToSwapWithLast]; 
      charArray[indexToSwapWithLast] = charArray[n - 1]; 
      charArray[n - 1] = temp; 
     } 

     GenerateHeapPermutations(n - 1, charArray, sList); 
    } 
} 

Hinweis: Sie können der redundanten Zahl n Eingang loszuwerden, und leiten sie von der Feldlänge von charArray.Length verwenden, aber, ich habe wollte nicht, Ihren Code unnötig ändern.

Answer 3

Ich würde stattdessen einen Parameter durch Verweis übergeben; Dies ergibt die erwartete Ausgabe.

string sample = "ABC"; 
      List<string> permutations = new List<string>(); 
      GenerateHeapPermutations(3, ref sample, permutations); 

      foreach (var p in permutations) 
      { 
       System.Console.WriteLine(p); 
      } 

      System.Console.ReadKey(); 




public static void GenerateHeapPermutations(int n, ref string s, List<string> sList) 
     { 
      if (n == 1) 
      { 
       sList.Add(s); 
      } 
      else 
      { 
       for (int i = 0; i < n - 1; i++) 
       { 
        GenerateHeapPermutations(n - 1, ref s, sList); 

        if (n % 2 == 0) 
        { 
         // swap the positions of two characters 
         var charArray = s.ToCharArray(); 
         var temp = charArray[i]; 
         charArray[i] = charArray[n - 1]; 
         charArray[n - 1] = temp; 
         s = new String(charArray); 
        } 
        else 
        { 
         var charArray = s.ToCharArray(); 
         var temp = charArray[0]; 
         charArray[0] = charArray[n - 1]; 
         charArray[n - 1] = temp; 
         s = new String(charArray); 
        } 
       } 

       GenerateHeapPermutations(n - 1, ref s, sList); 
      } 
     } 

Answer 4

Vielleicht ist meine Implementierung könnte Ihnen helfen ...

Ich denke, es ist die schnellste ...

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 
using System.Runtime.CompilerServices; 

namespace WpfPermutations 
{ 
    /// <summary> 
    /// EO: 2016-04-14 
    /// Generator of all permutations of an array of anything. 
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 
    /// </summary> 
    public static class Permutations 
    { 
     /// <summary> 
     /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. 
     /// </summary> 
     /// <param name="items">Items to permute in each possible ways</param> 
     /// <param name="funcExecuteAndTellIfShouldStop"></param> 
     /// <returns>Return true if cancelled</returns> 
     public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop) 
     { 
      int countOfItem = items.Length; 

      if (countOfItem <= 1) 
      { 
       return funcExecuteAndTellIfShouldStop(items); 
      } 

      var indexes = new int[countOfItem]; 
      for (int i = 0; i < countOfItem; i++) 
      { 
       indexes[i] = 0; 
      } 

      if (funcExecuteAndTellIfShouldStop(items)) 
      { 
       return true; 
      } 

      for (int i = 1; i < countOfItem;) 
      { 
       if (indexes[i] < i) 
       { // On the web there is an implementation with a multiplication which should be less efficient. 
        if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same. 
        { 
         Swap(ref items[i], ref items[indexes[i]]); 
        } 
        else 
        { 
         Swap(ref items[i], ref items[0]); 
        } 

        if (funcExecuteAndTellIfShouldStop(items)) 
        { 
         return true; 
        } 

        indexes[i]++; 
        i = 1; 
       } 
       else 
       { 
        indexes[i++] = 0; 
       } 
      } 

      return false; 
     } 

     /// <summary> 
     /// This function is to show a linq way but is far less efficient 
     /// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer 
     /// </summary> 
     /// <typeparam name="T"></typeparam> 
     /// <param name="list"></param> 
     /// <param name="length"></param> 
     /// <returns></returns> 
     static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) 
     { 
      if (length == 1) return list.Select(t => new T[] { t }); 

      return GetPermutations(list, length - 1) 
       .SelectMany(t => list.Where(e => !t.Contains(e)), 
        (t1, t2) => t1.Concat(new T[] { t2 })); 
     } 

     /// <summary> 
     /// Swap 2 elements of same type 
     /// </summary> 
     /// <typeparam name="T"></typeparam> 
     /// <param name="a"></param> 
     /// <param name="b"></param> 
     [MethodImpl(MethodImplOptions.AggressiveInlining)] 
     static void Swap<T>(ref T a, ref T b) 
     { 
      T temp = a; 
      a = b; 
      b = temp; 
     } 

     /// <summary> 
     /// Func to show how to call. It does a little test for an array of 4 items. 
     /// </summary> 
     public static void Test() 
     { 
      ForAllPermutation("123".ToCharArray(), (vals) => 
      { 
       Console.WriteLine(String.Join("", vals)); 
       return false; 
      }); 

      int[] values = new int[] { 0, 1, 2, 4 }; 

      Console.WriteLine("Ouellet heap's algorithm implementation"); 
      ForAllPermutation(values, (vals) => 
      { 
       Console.WriteLine(String.Join("", vals)); 
       return false; 
      }); 

      Console.WriteLine("Linq algorithm"); 
      foreach (var v in GetPermutations(values, values.Length)) 
      { 
       Console.WriteLine(String.Join("", v)); 
      } 

      // Performance Heap's against Linq version : huge differences 
      int count = 0; 

      values = new int[10]; 
      for (int n = 0; n < values.Length; n++) 
      { 
       values[n] = n; 
      } 

      Stopwatch stopWatch = new Stopwatch(); 

      ForAllPermutation(values, (vals) => 
      { 
       foreach (var v in vals) 
       { 
        count++; 
       } 
       return false; 
      }); 

      stopWatch.Stop(); 
      Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); 

      count = 0; 
      stopWatch.Reset(); 
      stopWatch.Start(); 

      foreach (var vals in GetPermutations(values, values.Length)) 
      { 
       foreach (var v in vals) 
       { 
        count++; 
       } 
      } 

      stopWatch.Stop(); 
      Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs"); 
     } 
    } 
}