Поиск n-й перестановки без вычисления других

Ответ 1

Как указано RickyBobby, при рассмотрении лексикографического порядка перестановок вы должны использовать факториальное разложение в ваших интересах.

С практической точки зрения, вот как я это вижу:

• Выполните какое-то эвклидовое деление, за исключением того, что вы делаете это с факториалами, начиная с (n-1)!, (n-2)! и т.д.
• Сохранять коэффициенты в массиве. Коэффициент i -th должен быть числом между 0 и n-i-1 включительно, где i идет от 0 до n-1.
• Этот массив является вашей перестановкой. Проблема в том, что каждый фактор не заботится о предыдущих значениях, поэтому вам нужно их настроить. Более конкретно, вам нужно увеличивать каждое значение столько раз, сколько есть предыдущие значения, которые ниже или равны.

Следующий код C должен дать вам представление о том, как это работает (n - количество записей, а i - индекс перестановки):

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);
}

Например, ithPermutation(10, 3628799) печатает, как и ожидалось, последнюю перестановку из десяти элементов:

9 8 7 6 5 4 3 2 1 0

Ответ 2

Здесь решение, которое позволяет выбрать размер перестановки. Например, помимо возможности генерировать все перестановки из 10 элементов, он может генерировать перестановки пар из 10 элементов. Также он переставляет списки произвольных объектов, а не только целых чисел.

function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index / count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

Пример использования:

for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

Как это работает?

За этим стоит очень интересная идея. Давайте возьмем список A, B, C, D. Мы можем построить перестановку, вытягивая из нее элементы, как из колоды карт. Изначально мы можем нарисовать один из четырех элементов. Затем один из трех оставшихся элементов и так далее, пока, наконец, у нас ничего не останется.

Вот одна из возможных последовательностей выбора. Начиная сверху мы идем по третьему пути, затем по первому, второму и, наконец, по первому. И это наша перестановка № 13.

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

Давайте попробуем найти общую схему для упаковки последовательности вариантов в целое число без избыточности и распаковки обратно.

Одна интересная схема называется десятичной системой счисления. "27" можно рассматривать как выбор пути № 2 из 10, а затем выбор пути № 7 из 10.

Но каждая цифра может кодировать только варианты из 10 вариантов. Другие системы с фиксированным основанием, такие как двоичные и шестнадцатеричные, также могут кодировать только последовательности выбора из фиксированного числа альтернатив. Нам нужна система с переменным основанием, вроде единиц времени: "14:05:29" - это час 14 из 24, минута 5 из 60, секунда 29 из 60.

Что если мы возьмем универсальные функции "число в строку" и "строка в число" и введем их в заблуждение? Вместо того, чтобы брать один осциллограф, например parseInt ('beef', 16) и (48879).toString(16), они получат один осциллограф на каждую цифру.

function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n / radixes[i]);
    }
    return digits;
}

Это вообще работает?

// Decimal system
pack([4, 2], [10, 10]); // => 42

// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42

// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42

А теперь задом наперед:

unpack(42, [10, 10]); // => [4, 2]

unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]

Это так красиво. Теперь давайте применим эту параметрическую систему счисления к проблеме перестановок. Мы рассмотрим перестановки длины 2 из A, B, C, D. Какое их общее количество? Давайте посмотрим: сначала мы нарисуем один из 4 предметов, затем один из оставшихся 3, что 4 * 3 = 12 позволяет нарисовать 2 предмета. Эти 12 способов могут быть упакованы в целые числа [0..11]. Итак, давайте представим, что мы уже упаковали их, и попробуйте распаковать:

for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

Эти числа представляют варианты, а не индексы в исходном массиве. [0, 0] не означает взятие A, A, это означает, что нужно взять элемент № 0 из A, B, C, D (тот A) и затем пункт # 0 из оставшегося списка B, C, D (тот B). И в результате получается перестановка A, B.

Другой пример: [3, 2] означает получение элемента № 3 из A, B, C, D (этого D) и затем элемента № 2 из оставшегося списка A, B, C (этого C). И в результате получается перестановка D, C.

Это отображение называется кодом Лемера. Давайте сопоставим все эти коды Лемера с перестановками:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

Это именно то, что нам нужно. Но если вы посмотрите на функцию unpack, вы заметите, что она производит цифры справа налево (чтобы изменить действия pack). Выбор из 3 распаковывается перед выбором из 4. Это прискорбно, потому что мы хотим выбрать из 4 элементов перед выбором из 3. Не имея возможности сделать это, мы должны сначала вычислить код Лемера, накопить его во временный массив, а затем примените его к массиву элементов, чтобы вычислить фактическую перестановку.

Но если мы не заботимся о лексикографическом порядке, мы можем притвориться, что мы хотим выбрать один из трех элементов, прежде чем выбрать один из четырех. Тогда выбор из четырех будет первым из unpack. Другими словами, мы будем использовать unpack(n, [3, 4]) вместо unpack(n, [4, 3]). Этот трюк позволяет вычислить следующую цифру кода Лемера и немедленно применить ее к списку. Именно так и работает nth_permutation().

И последнее, что я хочу упомянуть, это то, что unpack(i, [4, 3]) тесно связан с системой факторных чисел. Посмотрите на это первое дерево еще раз, если мы хотим перестановки длины 2 без дубликатов, мы можем просто пропустить каждый второй индекс перестановки. Это даст нам 12 перестановок длины 4, которые можно обрезать до длины 2.

for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
    console.log(lehmer.slice(0, 2));
}

Ответ 3

Это зависит от того, как вы "сортируете" свои перестановки (например, лексикографический порядок).

Один из способов сделать это factorial number system, он дает вам биекцию между [0, n!] и всеми перестановками.

Тогда для любого числа я из [0, n!] вы можете вычислить i-ю перестановку, не вычисляя остальные.

Это факториальное письмо основано на том, что любое число между [0 и n!] может быть записано как:

SUM( ai.(i!) for i in range [0,n-1]) where ai <i 

(он очень похож на базовое разложение)

для получения дополнительной информации об этом разложении, посмотрите на этот поток: https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

надеюсь, что это поможет

Как указано в этой статье в википедии, этот подход эквивалентен вычислению код lehmer:

Очевидным способом генерации перестановок n является создание значений для код Lehmer (возможно, используя систему факториалов представление целых чисел до n!) и преобразование их в соответствующие перестановки. Однако последний шаг, в то время как трудно, эффективно реализовать, потому что это требует n операций каждого из выбора из последовательности и удаления из нее, в произвольном положении; очевидных представлений о последовательность как массив или связанный список, оба требуют (для разных причины) о n2/4 операциях для выполнения преобразования. С n вероятно, будет довольно небольшим (особенно, если генерация всех необходимы перестановки), что не слишком много проблемы, но оно оказывается, что и для случайных, и для систематической генерации есть простые альтернативы, которые делают значительно лучше. По этой причине не представляется полезным, хотя, безусловно, возможно, использовать специальный структура данных, которая позволила бы выполнить преобразование из Lehmer код для перестановки в O (n log n) времени.

Итак, лучше всего для набора элементов n выбрать O (n ln (n)) с адаптированной структурой данных.

Ответ 4

Здесь представлен алгоритм преобразования между перестановками и рангами в линейном времени. Однако ранжирование, которое он использует, не является лексикографическим. Это странно, но непротиворечиво. Я собираюсь дать две функции, которые преобразуются из ранга в перестановку, и одну, которая делает обратную.

Во-первых, для отмены (перейдите от ранга к перестановке)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

Затем, чтобы ранжировать:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

Время работы обоих из них равно O (n).

Там есть хорошая, читаемая статья, объясняющая, почему это работает: ранжирование и разблокирование перестановок в линейном времени, by Myrvold и Ruskey, письма для обработки информации Том 79, выпуск 6, 30 сентября 2001 г., стр. 281-284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Ответ 5

Вот краткое и очень быстрое (линейное по количеству элементов) решение в python, работающее для любого списка элементов (13 первых букв в примере ниже):

from math import factorial

def nthPerm(n,elems):#with n from 0
    if(len(elems) == 1):
        return elems[0]
    sizeGroup = factorial(len(elems)-1)
    q,r = divmod(n,sizeGroup)
    v = elems[q]
    elems.remove(v)
    return v + ", " + ithPerm(r,elems)

Примеры:

letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m']

ithPerm(0,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, k, l, m
ithPerm(4,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, m, k, l
ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j

Примечание. Я даю letters[:] (копия letters), а не буквы, потому что функция изменяет свой параметр elems (удаляет выбранный элемент)

Ответ 6

Следующий код вычисляет k-ю перестановку для заданного n.

т.е. n = 3. Различные перестановки   123   132   213   231   312   321

Если k = 5, вернуть 312. Другими словами, он дает k-ю лексикографическую перестановку.

    public static String getPermutation(int n, int k) {
        char temp[] = IntStream.range(1, n + 1).mapToObj(i -> "" + i).collect(Collectors.joining()).toCharArray();
        return getPermutationUTIL(temp, k, 0);
    }

    private static String getPermutationUTIL(char temp[], int k, int start) {
        if (k == 1)
            return new String(temp);
        int p = factorial(temp.length - start - 1);
        int q = (int) Math.floor(k / p);
        if (k % p == 0)
            q = q - 1;
        if (p <= k) {
            char a = temp[start + q];
            for (int j = start + q; j > start; j--)
                temp[j] = temp[j - 1];
            temp[start] = a;
        }
        return k - p >= 0 ? getPermutationUTIL(temp, k - (q * p), start + 1) : getPermutationUTIL(temp, k, start + 1);
    }

    private static void swap(char[] arr, int j, int i) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int factorial(int n) {
        return n == 0 ? 1 : (n * factorial(n - 1));
    }

Ответ 7

Это можно вычислить. Это код С#, который делает это для вас.

using System;
using System.Collections.Generic;

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

        private bool[] _valueUsed;

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

        // ************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            if (sortedValues.Length <= 0)
            {
                throw new ArgumentException("sortedValues.Lenght should be greater than 0");
            }

            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

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

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

        // ************************************************************************
        /// <summary>
        /// Return the permutation relative to the index received, according to 
        /// _sortedValues.
        /// 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 GetValuesForIndex(long sortIndex)
        {
            int size = _sortedValues.Length;

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

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should be 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;
            }
        }

        // ************************************************************************
        /// <summary>
        /// Calc the index, relative to _sortedValues, of the permutation received
        /// as argument. Returned index is 0 based.
        /// </summary>
        /// <param name="values"></param>
        /// <returns></returns>
        public long GetIndexOfValues(T[] values)
        {
            int size = _sortedValues.Length;
            long valuesIndex = 0;

            List<T> valuesLeft = new List<T>(_sortedValues);

            for (int index = 0; index < size; index++)
            {
                long indexFactorial = Factorial.GetFactorial(size - 1 - index);

                T value = values[index];
                int indexCorrected = valuesLeft.IndexOf(value);
                valuesIndex = valuesIndex + (indexCorrected * indexFactorial);
                valuesLeft.Remove(value);
            }
            return valuesIndex;
        }

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

Ответ 8

Если вы сохраняете все перестановки в памяти, например, в массиве, вы можете вернуть их обратно по одному за время O (1).

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

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