8

C# で Heap's Algorithm の実装を作成しようとしましたが、正しく動作しません。文字列のすべての順列を見つけてリストに追加する汎用実装を作成しようとしています。

私はこのように始めています：

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

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

Console.ReadKey();

そして、これが私の実装です：

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

アルゴリズムは正しい数の順列 (この場合は 6) を生成しますが、順列自体は正しくありません。

ABC       BAC       CBA               
BCA       ABC       BAC

ウィキペディアのヒープのアルゴリズムの擬似コードの例から逸脱しているとは思いません。このアルゴリズムの再帰的な性質のために、これをデバッグするのに苦労しています (概念化するのはかなり難しいです)。

問題が何であるかについて、誰かが洞察を提供できますか?

PS宿題ではなく、ただの楽しみです。

4

4 に答える 4

10

あなたのアルゴリズムはstring、実際の配列の代わりに渡すことに基づいています。文字列のコピーを渡すstringと、コピーされた文字列を変更しても、渡される実際の文字列は変更されません。

問題に変更stringするchar arrayと解決します。

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

注:冗長な数値入力を取り除きn、配列の長さから導き出すことができcharArray.Lengthますが、コードを不必要に変更したくありませんでした。

于 2015-07-09T18:09:42.697 に答える
4

まず最初に: デバッグ。再帰を処理する場合、コードをデバッグする最も簡単な方法は、IDE でブレーク ポイントを設定し、コードが期待どおりに動作していることをメモしながら、少しずつ実行することです。これにより、すべてのステップで変数の値を確認できます。

実際の値の代わりに文字列のコピーを渡しているため、文字列をどこにでも渡しても、期待どおりの結果が得られないことがわかります。代わりに参照渡しを行う場合 (C# で許可されているかどうかは不明)、期待どおりの結果が得られます。

于 2015-07-09T18:13:25.923 に答える
2

代わりに、参照によってパラメーターを渡します。これにより、期待される出力が得られます。

 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);
            }
        }
于 2015-07-09T18:24:21.310 に答える
1

おそらく私の実装はあなたを助けることができます...

最速だと思います…

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");
        }
    }
}
于 2016-04-15T02:58:49.260 に答える