Implementation of heaps algorithm

Question

Please I don't seem to know what is wrong with this my C# implementation of the heaps permutation algorithm. It does not give the correct permutation of an input array. Can somebody help me out?

Here is the pseudo-code

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
else
    for i := 0; i < n - 1; i += 1 do
        generate(n - 1, A)
        if n is even then
            swap(A[i], A[n-1])
        else
            swap(A[0], A[n-1])
        end if
    end for
    generate(n - 1, A)
end if

this is my c# Implementation

static void Permute(int[] A, int n) {
    if (n == 1) {
        printArray(A);
    } else {
        for (int i = 0; i < n - 1; i++) {
            Permute(A, n - 1);

            if (n % 2 == 0) {
                A = Swap(A, A[i], A[n - 1]);
                printArray(A);
            } else {
                A = Swap(A, A[0], A[n - 1]);
                printArray(A);
            }

        }

        Permute(A, n - 1);
    }
}


static int[] Swap(int[] A, int x, int y) {
    int temp;
    temp = A[x];
    A[x] = A[y];
    A[y] = temp;

    return A;
}

static void printArray(int[] A) {
    foreach(var x in A) {
        Console.Write(x);

    }
    Console.WriteLine();
}

Answer 1

Just as information for anybody...

You could achieve a really better performance by doing some adjustments:

• Convert recursion to iteration (less memory, better efficiency)
• Your swap function can be inlined and you could receive 2 parameters only by reference
• Modulo could be expensive to calculate, you could compare bit 1 instead
• You can make it generic which would not effect performance but will become more flexible
• To also improve flexibility, you can pass a func as a parameter to your method.

Just as a reference, I included my implementation of it.

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

Answer 2

Looks for me, that your meaning about the swap function, as you defined, expects to get the array and indexes of the swapped values.

So instead of:

Swap(A, A[i], A[n - 1]);
Swap(A, A[0], A[n - 1]);

Should be:

Swap(A, i, n - 1);
Swap(A, 0, n - 1);

By the way, if you had this algorithm for array of any other type than int[] you whould get compilation error in the swap call. You haven't have compilation error because of the coincidence that your array elements are of the same type as array index type: int

And another thing, even though its not an issue, it is not necessary to return the array, from Swap function. The first argument of the Swap, the array is passed by reference, so the Swap function works on the same array instance as in the caller function and not on its copy. So after you remove the unnecessary return from Swap, the printArray(A); called right after the Swap will print the same as you have now.

Answer 3

Try this:

public static IEnumerable<IEnumerable<T>> Permute<T>(this IList<T> v)
{
    ICollection<IList<T>> result = new List<IList<T>>();

    Permute(v, v.Count, result);

    return result;
}

private static void Permute<T>(IList<T> v, int n, ICollection<IList<T>> result)
{
    if (n == 1)
    {
        result.Add(new List<T>(v));
    }
    else
    {
        for (var i = 0; i < n; i++)
        {
            Permute(v, n - 1, result);
            Swap(v, n % 2 == 1 ? 0 : i, n - 1);
        }
    }
}

private static void Swap<T>(IList<T> v, int i, int j)
{
    var t = v[i];
    v[i] = v[j];
    v[j] = t;
}