Создание перестановок набора (наиболее эффективно)

Ответ 1

Вот самая быстрая реализация, с которой я закончил:

public class Permutations
{
    private readonly Mutex _mutex = new Mutex();

    private Action<int[]> _action;
    private Action<IntPtr> _actionUnsafe;
    private unsafe int* _arr;
    private IntPtr _arrIntPtr;
    private unsafe int* _last;
    private unsafe int* _lastPrev;
    private unsafe int* _lastPrevPrev;

    public int Size { get; private set; }

    public bool IsRunning()
    {
        return this._mutex.SafeWaitHandle.IsClosed;
    }

    public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
    {
        return this.Permutate(start, count, action, null, async);
    }

    public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
    {
        return this.Permutate(start, count, null, actionUnsafe, async);
    }

    private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
    {
        if (!this._mutex.WaitOne(0))
        {
            return false;
        }

        var x = (Action)(() =>
                             {
                                 this._actionUnsafe = actionUnsafe;
                                 this._action = action;

                                 this.Size = count;

                                 this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
                                 this._arrIntPtr = new IntPtr(this._arr);

                                 for (var i = 0; i < count - 3; i++)
                                 {
                                     this._arr[i] = start + i;
                                 }

                                 this._last = this._arr + count - 1;
                                 this._lastPrev = this._last - 1;
                                 this._lastPrevPrev = this._lastPrev - 1;

                                 *this._last = count - 1;
                                 *this._lastPrev = count - 2;
                                 *this._lastPrevPrev = count - 3;

                                 this.Permutate(count, this._arr);
                             });

        if (!async)
        {
            x();
        }
        else
        {
            new Thread(() => x()).Start();
        }

        return true;
    }

    private unsafe void Permutate(int size, int* start)
    {
        if (size == 3)
        {
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();

            return;
        }

        var sizeDec = size - 1;
        var startNext = start + 1;
        var usedStarters = 0;

        for (var i = 0; i < sizeDec; i++)
        {
            this.Permutate(sizeDec, startNext);

            usedStarters |= 1 << *start;

            for (var j = startNext; j <= this._last; j++)
            {
                var mask = 1 << *j;

                if ((usedStarters & mask) != mask)
                {
                    Swap(start, j);
                    break;
                }
            }
        }

        this.Permutate(sizeDec, startNext);

        if (size == this.Size)
        {
            this._mutex.ReleaseMutex();
        }
    }

    private unsafe void DoAction()
    {
        if (this._action == null)
        {
            if (this._actionUnsafe != null)
            {
                this._actionUnsafe(this._arrIntPtr);
            }

            return;
        }

        var result = new int[this.Size];

        fixed (int* pt = result)
        {
            var limit = pt + this.Size;
            var resultPtr = pt;
            var arrayPtr = this._arr;

            while (resultPtr < limit)
            {
                *resultPtr = *arrayPtr;
                resultPtr++;
                arrayPtr++;
            }
        }

        this._action(result);
    }

    private static unsafe void Swap(int* a, int* b)
    {
        var tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

Использование и тестирование:

var perms = new Permutations();

var sw1 = Stopwatch.StartNew();

perms.Permutate(0,
                11,
                (Action<int[]>)null); // Comment this line and...
                //PrintArr); // Uncomment this line, to print permutations

sw1.Stop();
Console.WriteLine(sw1.Elapsed);

Метод печати:

private static void PrintArr(int[] arr)
{
    Console.WriteLine(string.Join(",", arr));
}

Перейти глубже:

Я даже не думал об этом в течение очень долгого времени, поэтому я могу только объяснить свой код так много, но здесь общая идея:

• Перестановки не лексикографические - это позволяет мне практически выполнять меньше операций между перестановками.
• Реализация рекурсивна, а когда размер представления равен 3, он пропускает сложную логику и просто выполняет 6 свопов, чтобы получить 6 перестановок (или подперестановок, если хотите).
• Поскольку перестановки не находятся в лексикографическом порядке, как я могу решить, какой элемент нужно довести до начала текущего "представления" (субперестановка)? Я сохраняю запись элементов, которые уже использовались в качестве "стартеров" в текущем рекурсивном вызове с перестановкой и просто выполняются линейно для одного, который не использовался в хвосте моего массива.
• Реализация предназначена только для целых чисел, поэтому для перестановки над общим набором элементов вы просто используете класс Permutations для перестановки индексов вместо вашей фактической коллекции.
• Мьютекс предназначен только для обеспечения того, чтобы все не зависало, когда выполнение является асинхронным (обратите внимание, что вы можете передать параметр UnsafeAction, который, в свою очередь, получит указатель на перенастроенный массив. Вы не должны изменять порядок элементов в этом массиве (указатель)! Если вы хотите, вы должны скопировать массив в массив tmp или просто использовать безопасный параметр действия, который позаботится об этом для вас - переданный массив уже является копией).

Примечание:

Я понятия не имею, насколько хороша эта реализация на самом деле - я так долго ее не трогал. Испытайте и сравните с другими реализациями самостоятельно, и дайте мне знать, если у вас есть обратная связь!

Enjoy.

Ответ 2

Это может быть то, что вы ищете.

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

Ответ 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);

Ответ 4

Самый быстрый алгоритм перестановки, о котором я знаю, является алгоритмом QuickPerm.
Вот реализация, она использует возврат доходности, чтобы вы могли выполнять итерацию по мере необходимости.

Код:

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

Ответ 5

Немного поздно...

Согласно моим тестам, моя реализация алгоритм кучи, как представляется, дает максимальную производительность...

Результаты теста производительности для 12 элементов (12!) в выпуске на моей машине:

 - 1453051904 items in 10728 millisecs ==> My implementation of Heap (code included)
 - 1453051904 items in 18053 millisecs ==> Simple Plan
 - 1453051904 items in 85355 millisecs ==> Erez Robinson

Преимущества:

• Алгоритм кучи (Single swap на перестановку)
• Нет умножения (например, некоторые реализации, видимые в Интернете)
• Встроенный обмен
• Generic
• Небезопасный код
• На месте (очень низкая память)
• Нет modulo (только сравнение первого бит)

Моя реализация алгоритм кучи:

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 Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// </summary>
    public static class Permutations
    {
        /// <summary>
        /// Heap 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 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 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 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;
        });

Ответ 6

Вот общий поиск перестановок, который будет перебирать каждую перестановку коллекции и вызывать функцию evalution. Если функция evalution возвращает true (она нашла ответ, который она искала), искатель перестановки прекратит обработку.

public class PermutationFinder<T>
{
    private T[] items;
    private Predicate<T[]> SuccessFunc;
    private bool success = false;
    private int itemsCount;

    public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
    {
        this.items = items;
        this.SuccessFunc = SuccessFunc;
        this.itemsCount = items.Count();

        Recurse(0);
    }

    private void Recurse(int index)
    {
        T tmp;

        if (index == itemsCount)
            success = SuccessFunc(items);
        else
        {
            for (int i = index; i < itemsCount; i++)
            {
                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;

                Recurse(index + 1);

                if (success)
                    break;

                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;
            }
        }
    }
}

Вот простая реализация:

class Program
{
    static void Main(string[] args)
    {
        new Program().Start();
    }

    void Start()
    {
        string[] items = new string[5];
        items[0] = "A";
        items[1] = "B";
        items[2] = "C";
        items[3] = "D";
        items[4] = "E";
        new PermutationFinder<string>().Evaluate(items, Evaluate);
        Console.ReadLine();
    }

    public bool Evaluate(string[] items)
    {
        Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
        bool someCondition = false;

        if (someCondition)
            return true;  // Tell the permutation finder to stop.

        return false;
    }
}

Ответ 7

Как есть много ответов, я сделал несколько сводок. Для 11 предметов:

OP original (NextPermutation)   363ms
Sani Huttunen (NextPermutation) 334ms
Mike Dunlavey (perm)            433ms
Erez Robinson (QuickPerm)       210ms
Sam (PermutationFinder)         608ms

Я отклонил ответ SimpleVars, поскольку он не работает корректно и небезопасен. Это было быстрее всего, когда не было никаких действий, но с действием на перестановку скорость значительно уменьшилась. Я оптимизировал ответ @ErezRobinson немного, чтобы увидеть реальную производительность алгоритма. Это самый быстрый, слишком грустный, я понятия не имею, как это работает. Btw, когда я переместил суммирование (более поздним) в процедуру, чтобы избежать вызова действия, он достиг 160 мс.

public void QuickPermErez<T>(IEnumerable<T> set, Action<T[]> action)
{
    T[] arr = set.ToArray();
    int N = arr.Length;
    int[] p = new int[N];

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

    action(arr);

    i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
    while (i < N)
    {
        if (p[i] < i)
        {
            j = (i & 1) * p[i]; // IF i is odd then j = p[i] otherwise j = 0                    
            tmp = arr[j]; // swap(arr[j], arr[i])
            arr[j] = arr[i];
            arr[i] = tmp;

            action(arr);

            p[i]++;
            i = 1;
        }
        else // p[i] == i
        {
            p[i] = 0; // reset p[i] to zero
            i++;
        }
    }
}

Я суммировал первый элемент в массиве каждой перестановки, чтобы выполнить базовый тест и сделать его по крайней мере немного реальным сценарием. Я изменил перм, чтобы его можно было тестировать таким образом, но он был действительно косметическим.

void perm(int[] s, int n, int i, Action<int[]> ev)
{
    if (i >= n - 1) ev(s);
    else {
        perm(s, n, i + 1, ev);
        for (int j = i + 1; j < n; j++)
        {
            //swap(s[i], s[j]);
            int tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            perm(s, n, i + 1, ev);
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
}

И для полноты кода тестирования:

int[] arr;
int cnt;
Stopwatch st = new Stopwatch();
int N = 11;

arr = Enumerable.Range(1, N).ToArray();
cnt = 0;
st.Restart();
do
{
    cnt += arr[0];
} while (!NextPermutationOP(arr));
Console.WriteLine("OP: " + cnt + ", " + st.ElapsedMilliseconds.ToString());

arr = Enumerable.Range(1, N).ToArray();
cnt = 0;
st.Restart();
do
{
    cnt += arr[0];
} while (NextPermutationSani(arr));
Console.WriteLine("Sani: " + cnt + ", " + st.ElapsedMilliseconds.ToString());

arr = Enumerable.Range(1, N).ToArray();
cnt = 0;
st.Restart();
new PermutationFinder<int>().Evaluate(arr, (x) =>
{
    cnt += x[0];
    return false;
});
Console.WriteLine("Sam: " + cnt + ", " + st.ElapsedMilliseconds.ToString());   

arr = Enumerable.Range(1, N).ToArray();
cnt = 0;
st.Restart();
perm(arr, N, 0, (x) => cnt += x[0]);
Console.WriteLine("Mike: " + cnt + ", " + st.ElapsedMilliseconds.ToString());

arr = Enumerable.Range(1, N).ToArray();
cnt = 0;
st.Restart();
QuickPermErez(arr, (x) => cnt += x[0]);
Console.WriteLine("Erez: " + cnt + ", " + st.ElapsedMilliseconds.ToString()); 

Ответ 8

Вот рекурсивная реализация со сложностью O(n * n!) ¹ основанная на замене элементов массива. Массив инициализируется значениями из 1, 2, ..., n.

using System;

namespace Exercise
{
class Permutations
{
    static void Main(string[] args)
    {
        int setSize = 3;
        FindPermutations(setSize);
    }
    //-----------------------------------------------------------------------------
    /* Method: FindPermutations(n) */
    private static void FindPermutations(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = i + 1;
        }
        int iEnd = arr.Length - 1;
        Permute(arr, iEnd);
    }
    //-----------------------------------------------------------------------------  
    /* Method: Permute(arr) */
    private static void Permute(int[] arr, int iEnd)
    {
        if (iEnd == 0)
        {
            PrintArray(arr);
            return;
        }

        Permute(arr, iEnd - 1);
        for (int i = 0; i < iEnd; i++)
        {
            swap(ref arr[i], ref arr[iEnd]);
            Permute(arr, iEnd - 1);
            swap(ref arr[i], ref arr[iEnd]);
        }
    }
}
}

На каждом рекурсивном шаге мы заменяем последний элемент текущим элементом, на который указывает локальная переменная в цикле for, а затем указываем уникальность подкачки: увеличивая локальную переменную цикла for и уменьшая условие завершения цикла for, который изначально устанавливается на число элементов в массиве, когда последнее становится равным нулю, мы завершаем рекурсию.

Вот вспомогательные функции:

    //-----------------------------------------------------------------------------
    /*
        Method: PrintArray()

    */
    private static void PrintArray(int[] arr, string label = "")
    {
        Console.WriteLine(label);
        Console.Write("{");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i < arr.Length - 1)
            {
                Console.Write(", ");
            }
        }
        Console.WriteLine("}");
    }
    //-----------------------------------------------------------------------------

    /*
        Method: swap(ref int a, ref int b)

    */
    private static void swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

^{1. Существуют n! перестановки элементов n для печати. ​​}

Ответ 9

Там доступно введение в алгоритмы и обзор реализаций в Steven Skiena Руководство по разработке алгоритмов (глава 14.4 во втором издании)

Локена ссылается на Д. Кнута. Искусство компьютерного программирования, том 4. Fascicle 2: Генерация всех кортежей и перестановок. Addison Wesley, 2005.

Ответ 10

Я был бы удивлен, если бы действительно были исправления порядка. Если есть, то С# нуждается в фундаментальном улучшении. Кроме того, делать что-либо интересное с вашей перестановкой, как правило, требует больше работы, чем ее генерация. Таким образом, стоимость генерации будет незначительной в общей схеме вещей.

Тем не менее, я предлагаю попробовать следующее. Вы уже пробовали итераторы. Но попробовали ли вы функцию, которая принимает замыкание в качестве входных данных, а затем вызывает это замыкание для каждой найденной перестановки? В зависимости от внутренней механики С# это может быть быстрее.

Аналогично, попробовали ли вы функцию, которая возвращает замыкание, которое будет перебирать определенную перестановку?

При любом подходе существует ряд микро-оптимизаций, с которыми вы можете экспериментировать. Например, вы можете отсортировать свой входной массив и после этого вы всегда знаете, в каком порядке он находится. Например, у вас может быть массив bools, указывающий, является ли этот элемент меньше следующего, и вместо сравнения вы можете просто посмотрите на этот массив.

Ответ 11

Я создал алгоритм немного быстрее, чем Knuth one:

11 элементов:

мину: 0,39 секунды

Кнут: 0,624 секунды

13 элементов:

mine: 56.615 секунд

Кнут: 98.681 секунд

Здесь мой код в Java:

public static void main(String[] args)
{
    int n=11;
    int a,b,c,i,tmp;
    int end=(int)Math.floor(n/2);
    int[][] pos = new int[end+1][2];
    int[] perm = new int[n];

    for(i=0;i<n;i++) perm[i]=i;

    while(true)
    {
        //this is where you can use the permutations (perm)
        i=0;
        c=n;

        while(pos[i][1]==c-2 && pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]=0;
            i++;
            c-=2;
        }

        if(i==end) System.exit(0);

        a=(pos[i][0]+1)%c+i;
        b=pos[i][0]+i;

        tmp=perm[b];
        perm[b]=perm[a];
        perm[a]=tmp;

        if(pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]++;
        }
        else
        {
            pos[i][0]++;
        }
    }
}

Проблема заключается в том, что мой алгоритм работает только для нечетных чисел элементов. Я быстро написал этот код, поэтому я уверен, что есть лучший способ реализовать мою идею, чтобы получить лучшую производительность, но сейчас у меня нет времени для работы над этим, чтобы оптимизировать ее и решить проблему, когда число элементы четные.

Это одна своп для каждой перестановки, и она использует действительно простой способ узнать, какие элементы нужно менять.

Я написал объяснение метода кода в своем блоге: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

Ответ 12

Как автор этого вопроса задавал вопрос об алгоритме:

[...], создавая единую перестановку за раз и продолжая только при необходимости

Я бы предложил рассмотреть алгоритм Steinhaus-Johnson-Trotter.

алгоритм Steinhaus-Johnson-Trotter в Википедии

Красиво объяснено здесь

Ответ 13

Это 1 час ночи, и я смотрел телевизор и думал об этом же вопросе, но со строковыми значениями.

С учетом слова найдите все перестановки. Вы можете легко изменить это, чтобы обрабатывать массив, наборы и т.д.

Мне пришлось немного поработать, но решение, которое я придумал, было следующим:

string word = "abcd";

List<string> combinations = new List<string>();

for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));
        }
    }
}

Здесь тот же код, что и выше, но с некоторыми комментариями

string word = "abcd";

List<string> combinations = new List<string>();

//i is the first letter of the new word combination
for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        //add the first letter of the word, j is past i so we can get all the letters from j to the end
        //then add all the letters from the front to i, then skip over i (since we already added that as the beginning of the word)
        //and get the remaining letters from i+1 to right before j.
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            //if we're at the very last word no need to get the letters after i
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            //add i as the first letter of the word, then get all the letters up to i, skip i, and then add all the lettes after i
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));

        }
    }
}

Ответ 14

Если вы просто хотите рассчитать количество возможных перестановок, вы можете избежать этой тяжелой работы выше и использовать что-то вроде этого (изобретенное в С#):

public static class ContrivedUtils 
{
    public static Int64 Permutations(char[] array)
    {
        if (null == array || array.Length == 0) return 0;

        Int64 permutations = array.Length;

        for (var pos = permutations; pos > 1; pos--)
            permutations *= pos - 1;

        return permutations;
    }
}

Вы называете это следующим образом:

var permutations = ContrivedUtils.Permutations("1234".ToCharArray());
// output is: 24
var permutations = ContrivedUtils.Permutations("123456789".ToCharArray());
// output is: 362880