生成集合的排列(最有效)

Question

我想生成一个集合(集合)的所有排列,如下所示:

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

一般而言,这不是"如何"的问题,而是关于如何最有效的问题.此外,我不想生成所有排列并返回它们,但一次只生成一个排列,并且只在必要时继续(很像迭代器 - 我也尝试过,但结果却少了有效).

我已经测试了很多算法和方法,并提出了这个代码,这是我尝试过的最有效的代码:

public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
    // More efficient to have a variable instead of accessing a property
    var count = elements.Length;

    // Indicates whether this is the last lexicographic permutation
    var done = true;

    // Go through the array from last to first
    for (var i = count - 1; i > 0; i--)
    {
        var curr = elements[i];

        // Check if the current element is less than the one before it
        if (curr.CompareTo(elements[i - 1]) < 0)
        {
            continue;
        }

        // An element bigger than the one before it has been found,
        // so this isn't the last lexicographic permutation.
        done = false;

        // Save the previous (bigger) element in a variable for more efficiency.
        var prev = elements[i - 1];

        // Have a variable to hold the index of the element to swap
        // with the previous element (the to-swap element would be
        // the smallest element that comes after the previous element
        // and is bigger than the previous element), initializing it
        // as the current index of the current item (curr).
        var currIndex = i;

        // Go through the array from the element after the current one to last
        for (var j = i + 1; j < count; j++)
        {
            // Save into variable for more efficiency
            var tmp = elements[j];

            // Check if tmp suits the "next swap" conditions:
            // Smallest, but bigger than the "prev" element
            if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
            {
                curr = tmp;
                currIndex = j;
            }
        }

        // Swap the "prev" with the new "curr" (the swap-with element)
        elements[currIndex] = prev;
        elements[i - 1] = curr;

        // Reverse the order of the tail, in order to reset it's lexicographic order
        for (var j = count - 1; j > i; j--, i++)
        {
            var tmp = elements[j];
            elements[j] = elements[i];
            elements[i] = tmp;
        }

        // Break since we have got the next permutation
        // The reason to have all the logic inside the loop is
        // to prevent the need of an extra variable indicating "i" when
        // the next needed swap is found (moving "i" outside the loop is a
        // bad practice, and isn't very readable, so I preferred not doing
        // that as well).
        break;
    }

    // Return whether this has been the last lexicographic permutation.
    return done;
}

它的用法是发送一个元素数组,然后返回一个布尔值,指示这是否是最后一个词典排列,以及将数组改为下一个排列.

用法示例:

var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
    PrintArray(arr);
}

问题是我对代码的速度感到不满意.

迭代大小为11的数组的所有排列大约需要4秒.虽然它可以被认为是令人印象深刻的,因为一组11号的可能排列量11!接近4000万.

逻辑上,对于大小为12的数组,它将花费大约12倍的时间,因为12!是11! * 12,并且对于大小为13的数组,它将花费大约13倍于12大小的时间,依此类推.

所以你可以很容易地理解如何使用12或更大的数组,它需要很长时间才能完成所有排列.

而且我有一种强烈的预感,我可以以某种方式减少那么多的时间(没有切换到C#以外的语言 - 因为编译器优化确实非常好地优化,我怀疑我可以在Assembly中手动优化).

有没有人知道以其他方式更快地完成这项工作？您是否知道如何使当前算法更快？

请注意,我不想使用外部库或服务来实现这一点 - 我希望拥有代码本身,并希望它尽可能高效.

Answer 1

这可能就是你要找的东西.

    private static bool NextPermutation(int[] numList)
    {
        /*
         Knuths
         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
         2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
         3. Swap a[j] with a[l].
         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

         */
        var largestIndex = -1;
        for (var i = numList.Length - 2; i >= 0; i--)
        {
            if (numList[i] < numList[i + 1]) {
                largestIndex = i;
                break;
            }
        }

        if (largestIndex < 0) return false;

        var largestIndex2 = -1;
        for (var i = numList.Length - 1 ; i >= 0; i--) {
            if (numList[largestIndex] < numList[i]) {
                largestIndex2 = i;
                break;
            }
        }

        var tmp = numList[largestIndex];
        numList[largestIndex] = numList[largestIndex2];
        numList[largestIndex2] = tmp;

        for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {
            tmp = numList[i];
            numList[i] = numList[j];
            numList[j] = tmp;
        }

        return true;
    }

Answer 2

更新2018-05-28:

• 下面提供了一个新的多线程版本(快得多)作为另一个答案.
• 还有一篇关于置换的文章:置换:快速实现和允许多线程的新索引算法

有点太晚了......

根据最近的测试(更新2018-05-22)

• 最快的是我但不是按字典顺序排列
• 对于最快的词典顺序,Sani Singh Huttunen解决方案似乎是要走的路.

在我的机器上发布的10个项目(10!)的性能测试结果(毫秒):

• Ouellet:29
• SimpleVar:95
• 埃雷兹罗宾逊:156
• Sani Singh Huttunen:37岁
• 彭阳:45047

在我的机器上发布的13项(13!)的性能测试结果(秒):

• Ouellet:48.437
• SimpleVar:159.869
• 埃雷兹罗宾逊:327.781
• Sani Singh Huttunen:64.839

我的解决方案的优点:

• 堆的算法(每个置换单交换)
• 没有乘法(就像网上看到的一些实现)
• 内联交换
• 通用
• 没有不安全的代码
• 到位(内存使用率非常低)
• 没有模数(只有第一位比较)

我对Heap算法的实现:

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

这是我的测试代码:

Task.Run(() =>
            {

                int[] values = new int[12];
                for (int n = 0; n < values.Length; n++)
                {
                    values[n] = n;
                }

                // Eric Ouellet Algorithm
                int count = 0;
                var stopwatch = new Stopwatch();
                stopwatch.Reset();
                stopwatch.Start();
                Permutations.ForAllPermutation(values, (vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                    return false;
                });
                stopwatch.Stop();
                Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // Simple Plan Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
                permutations2.Permutate(1, values.Length, (int[] vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                });
                stopwatch.Stop();
                Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // ErezRobinson Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                };
                stopwatch.Stop();
                Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
            });

用法示例:

ForAllPermutation("123".ToCharArray(), (vals) =>
    {
        Console.WriteLine(String.Join("", vals));
        return false;
    });

int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
        {
            Console.WriteLine(String.Join("", vals));
            return false;
        });

Answer 3

好吧,如果你能用C语言处理它,然后翻译成你选择的语言,你就不能比这更快,因为时间将由以下因素控制print:

void perm(char* s, int n, int i){
  if (i >= n-1) print(s);
  else {
    perm(s, n, i+1);
    for (int j = i+1; j<n; j++){
      swap(s[i], s[j]);
      perm(s, n, i+1);
      swap(s[i], s[j]);
    }
  }
}

perm("ABC", 3, 0);

Answer 4

我所知道的最快排列算法是QuickPerm算法.
这是实现,它使用yield return,因此您可以按需要一次迭代一个.

码:

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        List<T> list = new List<T>(set);

        int i, j, tmp; // Upper Index i; Lower Index j

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

                for (int x = 0; x < N; x++)
                {
                    yieldRet[x] = list[a[x]-1];
                }
                yield return yieldRet;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }

Answer 5

更新2018-05-28，一个新版本，最快的...（多线程）

                            Time taken for fastest algorithms

需要：Sani Singh Huttunen（最快的lexico）解决方案和我的新OuelletLexico3，它们支持索引编制

索引具有2个主要优点：

• 允许直接获得任何排列
• 允许多线程（源自第一个优势）

文章：排列：快速实现和允许多线程的新索引算法

在我的机器上（6个超线程内核：12个线程），Xeon E5-1660 0 @ 3.30Ghz，测试运行空数据的算法要执行的13次！项目（以毫秒为单位的时间）：

• 53071：Ouellet（实现堆）
• 65366：Sani Singh Huttunen（最快的词汇）
• 11377：混合OuelletLexico3-Sani Singh Huttunen

附带说明：如果对线程的用法进行了修改（读/写），则在线程之间使用共享属性/变量进行置换操作将极大地影响性能。这样做会产生错误的共享在线程之间 ”。您将无法获得预期的性能。测试时出现了这种现象。当我尝试为置换的总计数增加全局变量时，我的经验显示出问题。

用法：

PermutationMixOuelletSaniSinghHuttunen.ExecuteForEachPermutationMT(
  new int[] {1, 2, 3, 4}, 
  p => 
    { 
      Console.WriteLine($"Values: {p[0]}, {p[1]}, p[2]}, {p[3]}"); 
    });

码：

using System;
using System.Runtime.CompilerServices;

namespace WpfPermutations
{
    public class Factorial
    {
        // ************************************************************************
        protected static long[] FactorialTable = new long[21];

        // ************************************************************************
        static Factorial()
        {
            FactorialTable[0] = 1; // To prevent divide by 0
            long f = 1;
            for (int i = 1; i <= 20; i++)
            {
                f = f * i;
                FactorialTable[i] = f;
            }
        }

        // ************************************************************************
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static long GetFactorial(int val) // a long can only support up to 20!
        {
            if (val > 20)
            {
                throw new OverflowException($"{nameof(Factorial)} only support a factorial value <= 20");
            }

            return FactorialTable[val];
        }

        // ************************************************************************

    }
}


namespace WpfPermutations
{
    public class PermutationSaniSinghHuttunen
    {
        public static bool NextPermutation(int[] numList)
        {
            /*
             Knuths
             1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
             2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
             3. Swap a[j] with a[l].
             4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

             */
            var largestIndex = -1;
            for (var i = numList.Length - 2; i >= 0; i--)
            {
                if (numList[i] < numList[i + 1])
                {
                    largestIndex = i;
                    break;
                }
            }

            if (largestIndex < 0) return false;

            var largestIndex2 = -1;
            for (var i = numList.Length - 1; i >= 0; i--)
            {
                if (numList[largestIndex] < numList[i])
                {
                    largestIndex2 = i;
                    break;
                }
            }

            var tmp = numList[largestIndex];
            numList[largestIndex] = numList[largestIndex2];
            numList[largestIndex2] = tmp;

            for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--)
            {
                tmp = numList[i];
                numList[i] = numList[j];
                numList[j] = tmp;
            }

            return true;
        }
    }
}


using System;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3<T> // Enable indexing 
    {
        // ************************************************************************
        private T[] _sortedValues;

        private bool[] _valueUsed;

        public readonly long MaxIndex; // long to support 20! or less 

        // ************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

            MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
        }

        // ************************************************************************
        public T[] Result { get; private set; }

        // ************************************************************************
        /// <summary>
        /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
        /// </summary>
        /// <param name="sortIndex"></param>
        /// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
        /// <returns></returns>
        public void GetSortedValuesFor(long sortIndex)
        {
            int size = _sortedValues.Length;

            if (sortIndex < 0)
            {
                throw new ArgumentException("sortIndex should greater or equal to 0.");
            }

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should less than factorial(the lenght of items)");
            }

            for (int n = 0; n < _valueUsed.Length; n++)
            {
                _valueUsed[n] = false;
            }

            long factorielLower = MaxIndex;

            for (int index = 0; index < size; index++)
            {
                long factorielBigger = factorielLower;
                factorielLower = Factorial.GetFactorial(size - index - 1);  //  factorielBigger / inverseIndex;

                int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);

                int correctedResultItemIndex = 0;
                for(;;)
                {
                    if (! _valueUsed[correctedResultItemIndex])
                    {
                        resultItemIndex--;
                        if (resultItemIndex < 0)
                        {
                            break;
                        }
                    }
                    correctedResultItemIndex++;
                }

                Result[index] = _sortedValues[correctedResultItemIndex];
                _valueUsed[correctedResultItemIndex] = true;
            }
        }

        // ************************************************************************
    }
}


using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace WpfPermutations
{
    public class PermutationMixOuelletSaniSinghHuttunen
    {
        // ************************************************************************
        private long _indexFirst;
        private long _indexLastExclusive;
        private int[] _sortedValues;

        // ************************************************************************
        public PermutationMixOuelletSaniSinghHuttunen(int[] sortedValues, long indexFirst = -1, long indexLastExclusive = -1)
        {
            if (indexFirst == -1)
            {
                indexFirst = 0;
            }

            if (indexLastExclusive == -1)
            {
                indexLastExclusive = Factorial.GetFactorial(sortedValues.Length);
            }

            if (indexFirst >= indexLastExclusive)
            {
                throw new ArgumentException($"{nameof(indexFirst)} should be less than {nameof(indexLastExclusive)}");
            }

            _indexFirst = indexFirst;
            _indexLastExclusive = indexLastExclusive;
            _sortedValues = sortedValues;
        }

        // ************************************************************************
        public void ExecuteForEachPermutation(Action<int[]> action)
        {
            //          Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} started: {_indexFirst} {_indexLastExclusive}");

            long index = _indexFirst;

            PermutationOuelletLexico3<int> permutationOuellet = new PermutationOuelletLexico3<int>(_sortedValues);

            permutationOuellet.GetSortedValuesFor(index);
            action(permutationOuellet.Result);
            index++;

            int[] values = permutationOuellet.Result;
            while (index < _indexLastExclusive)
            {
                PermutationSaniSinghHuttunen.NextPermutation(values);
                action(values);
                index++;
            }

            //          Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} ended: {DateTime.Now.ToString("yyyyMMdd_HHmmss_ffffff")}");
        }

        // ************************************************************************
        public static void ExecuteForEachPermutationMT(int[] sortedValues, Action<int[]> action)
        {
            int coreCount = Environment.ProcessorCount; // Hyper treading are taken into account (ex: on a 4 cores hyperthreaded = 8)
            long itemsFactorial = Factorial.GetFactorial(sortedValues.Length);
            long partCount = (long)Math.Ceiling((double)itemsFactorial / (double)coreCount);
            long startIndex = 0;

            var tasks = new List<Task>();

            for (int coreIndex = 0; coreIndex < coreCount; coreIndex++)
            {
                long stopIndex = Math.Min(startIndex + partCount, itemsFactorial);

                PermutationMixOuelletSaniSinghHuttunen mix = new PermutationMixOuelletSaniSinghHuttunen(sortedValues, startIndex, stopIndex);
                Task task = Task.Run(() => mix.ExecuteForEachPermutation(action));
                tasks.Add(task);

                if (stopIndex == itemsFactorial)
                {
                    break;
                }

                startIndex = startIndex + partCount;
            }

            Task.WaitAll(tasks.ToArray());
        }

        // ************************************************************************


    }
}