Вопрос по algorithm, permutation, performance, optimization, c# – Генерация перестановок набора (наиболее эффективно)

55

Я хотел бы генерировать все перестановки набора (коллекции), например, так:

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 секунд. Хотя это можно считать впечатляющим, так как количество возможных перестановок набора размером 1111! что почти 40 миллионов.

Логически, с массивом размером 12 это займет примерно в 12 раз больше времени, так как12! является11! * 12и с массивом размером 13 это займет примерно в 13 раз больше времени, чем с размером 12, и так далее.

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

И у меня есть сильное предчувствие, что я могу каким-то образом значительно сократить это время (не переключаясь на язык, отличный от C #, - потому что оптимизация компилятора действительно оптимизирует довольно хорошо, и я сомневаюсь, что смог бы оптимизировать так хорошо, вручную, в Assembly).

Кто-нибудь знает какой-нибудь другой способ сделать это быстрее? Есть ли у вас какие-либо идеи относительно того, как сделать текущий алгоритм быстрее?

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

порождающийall перестановки не могут быть сделаны быстрее, чем количество перестановок. nhahtdh
Я смущен этой строкой: «но генерирую только одну перестановку за раз и продолжаю только при необходимости». Какова ваша цель? Emil Vikström
Кстати, поскольку то, что вы делаете, по сути своейO(n!)В-третьих, всегда будет довольно небольшое число, для которого вы говорите: «М требует несколько секунд, но М + 1 займет М + 1 раз дольше». Даже если бы вы могли ускорить свой код в миллион раз, вы бы получили только с 12 до 17. Это сделало бы вас в миллион раз счастливее? Steve Jessop
@DaveBish Как это поможет мне? Это создает комбинации, а не перестановки. SimpleVar
Содержит ли набор только уникальные элементы? Lieven Keersmaekers

Ваш Ответ

17   ответов
3

Обновление 2018-05-28, новая версия, самая быстрая ... (многопоточная)

enter image description here

                            Time taken for fastest algorithms

Нужно: решение Sani Singh Huttunen (самая быстрая лексика) и мой новый OuelletLexico3, поддерживающий индексацию

Индексирование имеет 2 основных преимущества:

allows to get anyone permutation directly allows multi-threading (derived from the first advantage)

Статья:Перестановки: быстрые реализации и новый алгоритм индексации, позволяющий многопоточность

На моей машине (6 ядер HyperTread: 12 потоков) Xeon E5-1660 0 @ 3,30 ГГц, тестирует алгоритмы, работающие с пустыми вещами, для 13! элементы (время в миллисекундах):

53071: Ouellet (implementation of Heap) 65366: Sani Singh Huttunen (Fastest lexico) 11377: Mix OuelletLexico3 - Sani Singh Huttunen

Примечание: использование общих свойств / переменных между потоками для действий перестановки сильно повлияет на производительность, если их использование является модификацией (чтение / запись). Это создаст & quot;ложный обмен& Quot; между нитями. Вы не получите ожидаемую производительность. Я получил это поведение во время тестирования. Мой опыт показал проблемы, когда я пытаюсь увеличить глобальную переменную для общего количества перестановок.

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

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

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


    }
}
Впечатляющая реализация действительно! Хотел бы я +100 это!
100% согласен с тобой! : -) ... Во многих случаях более быстрое решение MT было бы предпочтительнее, чем более медленное решение ST. Просто чтобы сообщить вам, мне понадобился бы этот код год или два назад.
Бум, детка. Boom! Кто-то скажет, что многопоточность - это мошенничество ... но не я: P Генерация перестановок - это отличная вещь для распараллеливания, и вы действительно можете пойти только так далеко без многопоточности SimpleVar
@SaniSinghHuttunen, Вау! Большое спасибо! Я не смог бы достичь такой производительности без вашего кода. Это действительно комбинация обоих ... +100 к вам тоже :-)!
1

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

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

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

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

Идея bools совсем не оказалась полезной ... Мне все равно нужно сравнивать значения, не являющиеся соседями, при поиске "swap partner" в «хвосте», и доступ к bool в массиве не сильно отличается от сравнения двух целых чисел. В этом случае управление вторым массивом тратит впустую время. Но хорошая идея. SimpleVar
Оказывается, я был неправ, это была отличная идея! Это значительно сокращает время! Спасибо! Ожидание, чтобы видеть, подходит ли что-нибудь лучше, и рассматривая пометить это как ответ. SimpleVar
+1 За хорошую информацию. Использование замыкания, возможно, несколько ускорит процесс, но лишь чуть-чуть. Я бы предположил, что он экономит только несколько операций стека, копируя указатель на массив, и такие мелочи, но ничего существенного. Вторая идея, которую вы предложили - использование логического массива, - может внести хорошие изменения! Я попробую это и вернусь к вам :) SimpleVar
@YoryeNathan Но теперь вы можете попробовать другие вещи. Например, развертывание цикла. Выбрасывать перми. Затем поменяйте местами последние два и выделите следующую перми. Затем вернитесь к более сложной логике, зная, что вы знаете, что последние два элемента обращены вспять. Это пропускает полную логику для половины перми и пропускает одно сравнение для другой половины перми. Вы можете попробовать развернуть дальше - в какой-то момент вы столкнетесь с проблемами с кешем, и это не будет иметь смысла.
Это хорошая идея, но я сомневаюсь, что это будет иметь большое значение. Это в основном спасает меня от нескольких объявленных переменных, которые сразу же входят и сразу выходят из двух циклов, и одного сравнения между двумя элементами. Сравнение может быть значительным, если элементы являются экземплярами классов, которые реализуют IComparable с некоторой логикой, но, опять же, в таком случае я бы использовал массив целых чисел {0, 1, 2, ...}, чтобы указать индексирование в массив элементов, для быстрого сравнения. SimpleVar
0

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

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

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

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

        }
    }
}
3

Вот общий искатель перестановок, который будет перебирать каждую перестановку коллекции и вызывать функцию оценки. Если функция оценки возвращает 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;
    }
}
Этот алгоритм примерно в 3 раза медленнее, чем моя реализация Кнута. На 12 элементов это занимает 33169мс по сравнению с 11941мс. Порядок также не является строго лексикографическим.
Для списка из 12 элементов (39 916 800 перестановок) этот код занимает ~ 1 мин 13 секунд против ~ 2 мин 40 секунд для кода в исходном сообщении.
Я сохранил элементы. Счет в переменную. Отправленный код теперь занимает ~ .55 секунд, чтобы перебрать список из десяти элементов. Код в исходном сообщении занимает ~ 2,22 секунды для того же списка.
Код высокого качества! Спасибо, что поделился SimpleVar
Мой текущий код составляет ~ 1,3-1,5 сек для 11 элементов. Дело в том, что вы делаете2N! свопы, когда минимально необходимые свопыN!. SimpleVar
8

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

Code:

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)
    }
@ErezRobinson Моя реализация составляет 3,8-3,9 секунды на моем компьютере (что не очень хорошо), а ваша - 13 секунд. Сани для меня составляет 3,7-3,8. SimpleVar
@ErezRobinson Кстати, оказывается, моя реализация на самом деле в стиле Кнута. SimpleVar
Я не проверял лексографический порядок, но на моем компьютере QuickPerm занял 11 секунд для 11 элементов, а ваш алгоритм занял 15 секунд. Во всяком случае, я желаю вам удачи.
Это примерно в 3 раза медленнее, чем моя текущая реализация, и также не повторяется в лексикографическом порядке. SimpleVar
@ErezRobinson: Это занимает около 7 секунд по сравнению с 1,7 секундами моей реализации алгоритма Кнутса с 11 элементами на моем компьютере, поэтому ваш алгоритм работает в 4 раза медленнее.
0

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * http://marknelson.us/2002/03/01/next-permutation/
 * Rearranges the elements into the lexicographically next greater permutation and returns true.
 * When there are no more greater permutations left, the function eventually returns false.
 */

// next lexicographical permutation

template <typename T>
bool next_permutation(T &arr[], int firstIndex, int lastIndex)
{
    int i = lastIndex;
    while (i > firstIndex)
    {
        int ii = i--;
        T curr = arr[i];
        if (curr < arr[ii])
        {
            int j = lastIndex;
            while (arr[j] <= curr) j--;
            Swap(arr[i], arr[j]);
            while (ii < lastIndex)
                Swap(arr[ii++], arr[lastIndex--]);
            return true;
        }
    }
    return false;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * Swaps two variables or two array elements.
 * using references/pointers to speed up swapping.
 */
template<typename T>
void Swap(T &var1, T &var2)
{
    T temp;
    temp = var1;
    var1 = var2;
    var2 = temp;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above function
#define N 3

void OnStart()
{
    int i, x[N];
    for (i = 0; i < N; i++) x[i] = i + 1;

    printf("The %i! possible permutations with %i elements:", N, N);

    do
    {
        printf("%s", ArrayToString(x));

    } while (next_permutation(x, 0, N - 1));

}

// Output:
// The 3! possible permutations with 3 elements:
// "1,2,3"
// "1,3,2"
// "2,1,3"
// "2,3,1"
// "3,1,2"
// "3,2,1"

Этот код трудно понять. В этом случае имеет смысл быть кратким с именами переменных.
33

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

    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;
    }
@YoryeNathan, Код, или этого не произошло.
Это немного быстрее, чем моя реализация, большое спасибо! Я все еще ожидаю, что улучшение будет намного более значительным - что, вероятно, будет означать изменение самого алгоритма. +1 за правильный ответ, хотя! SimpleVar
Тестирование массива размером 12 показывает, что моя реализация заняла 46 секунд, а ваша - 43, поэтому, хотя вы опередили меня на 3 секунды, я, по крайней мере, ищу способ сократить половину времени. SimpleVar
@YoryeNathan, а вы должны читателям "Я думаю, что я опубликую статью где-нибудь о моей работе".
3 секунды - это вечность на SO ...;) Одним из способов значительно улучшить было бы распараллеливание алгоритма. Но это не всегда применимо. Но посмотрите здесь:scidok.sulb.uni-saarland.de/volltexte/2005/397/pdf/…
-1

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

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
Да, это действительно не так сложно реализовать факторинг. Идея в том, чтобы самим иметь перестановки. Не говоря уже о том, что вам лучше всего.Permutations(4) вместо бессмысленного набора символов. SimpleVar
И все же, весь ответ остается неуместным для предмета. SimpleVar
верно, но каждый раз, когда мне задавали этот вопрос в интервью, ввод всегда представлял собой строку символов, поэтому казалось целесообразным представить его таким образом.
0

Я нашел этот алгоритм в коде Розетты, и он действительно самый быстрый, который я пробовал.http://rosettacode.org/wiki/Permutations#C

/* Boothroyd method; exactly N! swaps, about as fast as it gets */
void boothroyd(int *x, int n, int nn, int callback(int *, int))
{
	int c = 0, i, t;
	while (1) {
		if (n > 2) boothroyd(x, n - 1, nn, callback);
		if (c >= n - 1) return;
 
		i = (n & 1) ? 0 : c;
		c++;
		t = x[n - 1], x[n - 1] = x[i], x[i] = t;
		if (callback) callback(x, nn);
	}
}
 
/* entry for Boothroyd method */
void perm2(int *x, int n, int callback(int*, int))
{
	if (callback) callback(x, n);
	boothroyd(x, n, n, callback);
}
 

Этот код трудно понять. В этом случае имеет смысл быть кратким с именами переменных.
1

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

[...] generating a single permutation, at a time, and continuing only if necessary

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

Steinhaus & # x2013; Johnson & # x2013; Алгоритм Троттера в Википедии

Красиво объяснилВот

1

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

11 elements:

mine: 0.39 seconds

Knuth's: 0.624 seconds

13 elements:

mine: 56.615 seconds

Knuth's: 98.681 seconds

Вот мой код на 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

перестановки не генерируются в порядке с этим алгоритмом
Раз уж мы говорим о производительности, избавимся от неровных массивов и вместо этого будем использовать шаг.
Кажется интересным, хотя кажется, что это немного медленнее, чем моя текущая реализация (помечено как ответ). Хотя я бы хотел это понять. Также интересно, как вы на самом деле рассчитали производительность с неработающим кодом (new int[end + 1][2] должен статьnew int[end + 1][] с соответствующим циклом инициализации следующего) SimpleVar
2

Вот рекурсивная реализация со сложностьюO(n * n!)1 основанный на обмене элементами массива. Массив инициализируется значениями из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. There are n! permutations of n elements to be printed.

Хорошее и аккуратное решение для общих целей. Однако по скорости он отстает. Но +1 для хорошего кода, так как большинство кодеров, вероятно, предпочтут удобочитаемость для большинства применений. SimpleVar
0

// Permutations are the different ordered arrangements of an n-element
// array. An n-element array has exactly n! full-length permutations.

// This iterator object allows to iterate all full length permutations
// one by one of an array of n distinct elements.

// The iterator changes the given array in-place.

// Permutations('ABCD') => ABCD  DBAC  ACDB  DCBA
//                         BACD  BDAC  CADB  CDBA
//                         CABD  ADBC  DACB  BDCA
//                         ACBD  DABC  ADCB  DBCA
//                         BCAD  BADC  CDAB  CBDA
//                         CBAD  ABDC  DCAB  BCDA

// count of permutations = n!

// Heap's algorithm (Single swap per permutation)
// http://www.quickperm.org/quickperm.php
// https://stackoverflow.com/a/36634935/4208440
// https://en.wikipedia.org/wiki/Heap%27s_algorithm


// My implementation of Heap's algorithm:

template<typename T>
class PermutationsIterator
{
	int b, e, n;
	int c[32];  /* control array: mixed radix number in rising factorial base.
	            the i-th digit has base i, which means that the digit must be
	            strictly less than i. The first digit is always 0,  the second
	            can be 0 or 1, the third 0, 1 or 2, and so on.
	            ArrayResize isn't strictly necessary, int c[32] would suffice
	            for most practical purposes. Also, it is much faster */

public:
	PermutationsIterator(T &arr[], int firstIndex, int lastIndex)
	{
		this.b = firstIndex;  // v.begin()
		this.e = lastIndex;   // v.end()
		this.n = e - b + 1;

		ArrayInitialize(c, 0);
	}

	// Rearranges the input array into the next permutation and returns true.
	// When there are no more permutations left, the function returns false.

	bool next(T &arr[])
	{
		// find index to update
		int i = 1;

		// reset all the previous indices that reached the maximum possible values
		while (c[i] == i)
		{
			c[i] = 0;
			++i;
		}

		// no more permutations left
		if (i == n)
			return false;

		// generate next permutation
		int j = (i & 1) == 1 ? c[i] : 0;    // IF i is odd then j = c[i] otherwise j = 0.
		swap(arr[b + j], arr[b + i]);       // generate a new permutation from previous permutation using a single swap

		// Increment that index
		++c[i];
		return true;
	}

};

4

Here is the fastest implementation I ended up with:

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

Usage and testing performance:

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

Printing method:

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

Going deeper:

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

Permutations aren't lexicographic - this allows me to practically perform less operations between permutations. The implementation is recursive, and when the "view" size is 3, it skips the complex logic and just performs 6 swaps to get the 6 permutations (or sub-permutations, if you will). Because the permutations aren't in a lexicographic order, how can I decide which element to bring to the start of the current "view" (sub permutation)? I keep record of elements that were already used as "starters" in the current sub-permutation recursive call and simply search linearly for one that wasn't used in the tail of my array. The implementation is for integers only, so to permute over a generic collection of elements you simply use the Permutations class to permute indices instead of your actual collection. The Mutex is there just to ensure things don't get screwed when the execution is asynchronous (notice that you can pass an UnsafeAction parameter that will in turn get a pointer to the permuted array. You must not change the order of elements in that array (pointer)! If you want to, you should copy the array to a tmp array or just use the safe action parameter which takes care of that for you - the passed array is already a copy).

Note:

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

Наслаждаться.

Это ужасная реализация, извините ...
@sam Код в вопросе стабильный и работает хорошо, да. Но тема на самом деле делала его максимально эффективным (даже за счет читабельности), что мне помогло это решение. SimpleVar
@ Lu4 Что в этом плохого? Чем больше оптимизаций, тем менее красивый код - но он работает молниеносно. SimpleVar
Ваша оригинальная реализация (предоставленная в вашем вопросе) является лучшим решением здесь. Это чистый и быстрый код и генерирует отсортированную перестановку. Я никогда не использовал это помеченное как ответ на самом деле ...
Постскриптум Я на самом деле изучаю ваше оригинальное решение, у меня была та же интуиция, что и у вас, но мне не удалось написать общее решение. Отлично сработано.
1

Есть доступное введение в алгоритмы и обзор реализаций в Стивене Скиене.Algorithm Design Manual (глава 14.4 во втором издании)

Скиена ссылки Д. Кнута. Искусство компьютерного программирования, том 4, глава 2: создание всех кортежей и перестановок. Аддисон Уэсли, 2005.

Я раньше не слышал об алгоритме Кнута, но оказалось, что мой алгоритм в значительной степени принадлежит ему. SimpleVar
Ссылка не работает для меня, хотя Google находит и этот веб-сайт, поэтому это странно. Пинг к нему в CMD приводит к тайм-аутам, поэтому я могу только догадываться, что связь на самом деле не работает. SimpleVar
Я думаю, что сайт автора закрыт. Прибегайте к Амазонке или вашей библиотеке.
@MattHickford В книге есть хорошая информация, но ничего, что может мне помочь. SimpleVar
Я думаю, что Кнут всесторонний, но у меня нет копии.
18

Update 2018-05-28:

A new multithreaded version (lot faster) is available below as another answer. Also an article about permutation: Permutations: Fast implementations and a new indexing algorithm allowing multithreading

Слишком поздно ...

По последним тестам (обновлено 2018-05-22)

Fastest is mine BUT not in lexicographic order For fastest lexicographic order, Sani Singh Huttunen solution seems to be the way to go.

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

Ouellet : 29 SimpleVar: 95 Erez Robinson : 156 Sani Singh Huttunen : 37 Pengyang : 45047

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

Ouellet : 48.437 SimpleVar: 159.869 Erez Robinson : 327.781 Sani Singh Huttunen : 64.839

Преимущества моего решения:

Heap's algorithm (Single swap per permutation) No multiplication (like some implementations seen on the web) Inlined swap Generic No unsafe code In place (very low memory usage) No modulo (only first bit compare)

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

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;
        });
Спасибо! Я только что реализовал то, что нашел в Википедии.
@SaniSinghHuttunen. Хорошо, спасибо за разъяснения.
Доверяя вашему тесту, я отметил это как ответ. Выглядит очень мило! SimpleVar
Конечно, куча работает быстрее, чем большинство (все?) Других алгоритмов. Но это "ломается" исходное требование «лексикографического порядка».
@SaniSinghHuttunen, я согласен, что это не в лексикографическом порядке, но если я хорошо помню, я думаю, что это не было требованием исходного вопроса ... Это зависит от ваших потребностей ...
10

Что ж, если вы можете справиться с этим в 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);
Это лучший алгоритм, маленький, чистый, без мьютексов, отличный, спасибо!
Отличный ответ. Переведено это без проблем в C # (работает над ref int []).
@Yorye: хорошо, два обмена занимают, может быть, 8 инструкций. Вызов функции, вход и возврат занимает максимум 10. Внутренняя пара циклов является доминирующей, так что вы говорите, может быть, 20 инструкций для каждой перестановки. Если вы бьете это, это довольно умно.
@Yorye: Ну, как я уже сказал, почти все время печатается. Если вы просто закомментируете распечатку, вы увидите, сколько времени занимает сам алгоритм. В C #, где вам предлагается создавать классы коллекций, итераторы и делать все виды распределения памяти, любой хороший алгоритм может быть сделан медленным, как патока.
Это был один из первых алгоритмов, которые я придумал и попробовал, но он не самый быстрый. Моя текущая реализация быстрее. SimpleVar

Похожие вопросы