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.}

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? — Tim
– Tim, Commented Jul 9, 2015 at 18:07

Orel Eraki · Accepted Answer · 2015-07-09 18:14:32Z

10

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.

edited Jul 9, 2015 at 18:14

answered Jul 9, 2015 at 18:09

Orel Eraki

12.2k4 gold badges31 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

alex Over a year ago

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?

LSU.Net Over a year ago

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". stackoverflow.com/questions/10792603/…

Orel Eraki Over a year ago

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

JRodge01 · Accepted Answer · 2015-07-09 18:13:25Z

4

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.

answered Jul 9, 2015 at 18:13

JRodge01

2801 silver badge8 bronze badges

1 Comment

alex Over a year ago

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

LSU.Net · Accepted Answer · 2015-07-09 18:24:21Z

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

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

Eric Ouellet · Accepted Answer · 2016-04-15 02:58:49Z

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

Collectives™ on Stack Overflow

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

4 Answers 4

3 Comments

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related