L'implementazione C# dell'algoritmo di Heap non funziona

Question

Ho tentato di scrivere un'implementazione di Heap's Algorithm in C# che non funziona correttamente. Sto provando a creare un'implementazione generica che trovi tutte le permutazioni di una stringa e le aggiunga a una lista.

Sto iniziando come questo:

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

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

Console.ReadKey(); 

Ed ecco la mia realizzazione:

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

L'algoritmo fa cedere il corretto numero di permutazioni (in questo caso, sei), ma il le stesse permutazioni non sono corrette:

ABC  BAC  CBA    
BCA  ABC  BAC 

Non penso di deviare dallo pseudocode example of Heap's algorithm on Wikipedia, e ho difficoltà a eseguire il debug di questo a causa della natura ricorsiva di questo algoritmo (piuttosto difficile da concettualizzare).

Qualcuno può offrire qualche idea su quale potrebbe essere il problema?

^{P.S. Non fare i compiti, solo per divertimento.}

Answer 1

Prima di tutto: debug. Quando si ha a che fare con la ricorsione, il modo più semplice per eseguire il debug del codice è impostare i punti di interruzione nel proprio IDE e procedere passo dopo passo, prendendo nota che il codice si sta comportando come ci si aspetta. Questo ti permette di guardare i valori delle tue variabili ad ogni passo.

Scoprirai che passare la stringa dappertutto non produce ciò che ti aspetti, perché ne stai passando una copia invece del valore effettivo. Se passi invece per riferimento (non so se C# lo consente), farai quello che ti aspetti.

Answer 2

L'algoritmo si basa sul passaggio dello string anziché sull'array effettivo. Quando si passa string, viene eseguita una copia della stringa, pertanto la modifica della stringa copiata non cambierà la stringa effettiva che viene passata.

Quando si modifica string in char array il problema è risolto.

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

Nota: Si può sbarazzarsi del superfluo inserimento del numero n, e derivare dalla lunghezza della matrice, utilizzando charArray.Length ma, non ho voluto cambiare il codice inutilmente.

Answer 3

Passerei invece un parametro per riferimento; questo produce l'output atteso.

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

Forse la mia implementazione potrebbe aiutare ...

Penso che sia il più veloce ...

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