C# implementation of Heap's algorithm doesn't work

Question

I've attempted to write an implementation of Heap's Algorithm in C# which isn't working correctly. I'm trying to create a general-purpose implementation that will find all permutations of a string, and add them to a list.

I'm starting out like this:

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

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

Console.ReadKey();

And here's 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 does yield 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 I'm deviating from the pseudocode example of Heap's algorithm on Wikipedia, and I'm having a hard time debugging this due the recursive nature of this algorithm (pretty tricky to conceptualize).

Could anyone offer any insight as to what the problem could be?

^{P.S. Not homework, just for fun.}

Zenda

From the pseudo-code: procedure generate(n : integer, A : array of any):, but you have GenerateHeapPermutations(int n, string s, List<string> sList) - why the extra string argument? – Glossectomy

@Glossectomy he is just saving the permuted strings. – Eutectoid

Alex, I've edited my code, so i won't repeat myself. – Trentontrepan

Answer 1

First things first: debugging. When dealing with recursion, the easiest way to debug your code is to set break points in your IDE and step through it bit by bit, taking notes that the code is behaving how you expect it to. This allows you to look at the values of your variables at every step.

You'll find that passing your string in everywhere is not yielding what you expect it to because you're passing a copy of it instead of the actual value. If you pass by reference instead (not sure if C# allows that), you'll do what you're expecting.

Aneto

This answer along with this MSDN tutorial is what ultimately helped me implement a string-based solution implementation of the algorithm - thanks! – Zenda

Answer 2

You're algorithm is based on passing string instead of the actual array. When passing string a copy of the string is taken, thus changing the copied string won't change the actual string which is passed.

When changing string to char array the problem is solved.

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 the redundant number n input, and derive it from the array length, by using charArray.Length but, I didn't wanted to change your code unnecessarily.

Trentontrepan

This does work, but I'm having a hard time understanding why. Could you go into a little more detail about why the string-based version of this code does not work? – Zenda

This post does a great job in explaining the difference in passing a string by reference vs by value. The key is the way you originally passed in the constant "ABC". #10793103 – Transmitter

@alex, I will add a Further Explanation, in few hours (going out :) ) – Trentontrepan

Answer 3

I would pass in a parameter by reference instead; this yields the expected output.

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

Transmitter

This is the same way that I ended up solving the problem - thanks! – Zenda

Answer 4

Perhaps my implementation could help you...

I think it 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'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 : https://mcmap.net/q/81374/-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");
        }
    }
}

Pskov