C # heap algorithm implementation not working

Question

I tried to write an implementation of the heap algorithm in C #, which does not work correctly. I am trying to create a universal implementation that finds all permutations of a string and adds them to the list.

I start like this:

List<string> permutations = new List<string>(); GenerateHeapPermutations(3, "ABC", permutations); foreach (var p in permutations) { Console.WriteLine(p); } Console.ReadKey(); 

And here is my implementation:

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

The algorithm gives the correct number of permutations (in this case, six), but the permutations themselves are incorrect:

 ABC BAC CBA BCA ABC BAC 

I don’t think that I am deviating from the pseudocode of the heap algorithm example on Wikipedia , and I have heavy debugging due to the recursive nature of this algorithm (it is rather difficult to conceptualize).

Can someone give an idea of ​​what might be the problem?

^{PS Not homework, just for fun.}

Answer 1

First things: debugging. When you do recursion, the easiest way to debug your code is to set breakpoints in your IDE and step by step little by little, taking notes that the code behaves as you expect. This allows you to look at the values ​​of your variables at every step.

You will find that passing your string around the world does not give what you expect, because you are passing a copy of it instead of the actual value. If instead you pass the link (not sure if C # allows), you will do what you expect.

Answer 2

You are an algorithm based on passing a string instead of the actual array. When transferring string , a copy of the string is executed, so changing the copied string does not change the actual string that is transmitted.

When changing string to char array problem is resolved.

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

Note. . You can get rid of entering the excess number n and get it from the length of the array using charArray.Length , but I did not want to change my code unnecessarily.

Answer 3

Instead, I would pass the parameter by reference; this gives the expected result.

  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

Perhaps my implementation may help you ...

I think this is the fastest ...

 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 Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 /// </summary> public static class Permutations { /// <summary> /// Heap 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 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 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 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"); } } }