Get a permutation as a function of a unique given index in O(n)

Question

I would like to have a function get_permutation that, given a list l and an index i, returns a permutation of l such that the permutations are unique for all i bigger than 0 and lower than n! (where n = len(l)).

I.e. get_permutation(l,i) != get_permutation(l,j) if i!=j for all i, j s.t. 0 <= i and j < len(l)!).

Moreover, this function has to run in O(n).

For example, this function would comply the with the requirements, if it weren't for the exponential order:

def get_permutation(l, i):
     return list(itertools.permutations(l))[i]

Does anyone has a solution for the above described problem?

EDIT: I want the permutation from the index NOT the index from the permutation

Answer 1

If you don't care about which permutations get which indices, an O(n) solution becomes possible if we consider that arithmetic operations with arbitrary integers are O(1).

For example, see the paper "Ranking and unranking permutations in linear time" by Wendy Myrvold and Frank Ruskey.

In short, there are two ideas.

---

(1) Consider Fisher-Yates shuffle method to generate a random permutation (pseudocode below):

p = [0, 1, ..., n-1]
for i := 0 upto n-1:
    j := random_integer (0, i)
    exchange p[i] and p[j]

This transform is injective: if we give it a different sequence of random integers, it is guaranteed to produce a different permutation. So, we substitute random integers by non-random ones: the first one is 0, the second one 0 or 1, ..., the last one can be any integer from 0 to n-1.

---

(2) There are n! permutations of order n. What we want to do now is to write an integer from 0 to n!-1 in factorial number system: the last digit is always 0, the previous one is 0 or 1, ..., and there are n possibilities from 0 to n-1 for the first digit. Thus we will get a unique sequence to feed the above pseudocode with.

Now, if we consider division of our number by an integer from 1 to n to be O(1) operation, transforming the number to factorial system is O(n) such divisions. This is, strictly speaking, not true: for large n, the number n! contains on the order of O(n log n) binary digits, and that division's cost is proportional to the number of digits.

---

In practice, for small n, O(n^2) or O(n log n) methods to rank or unrank a permutation, and also methods requiring O(2^n) or O(n!) memory to store some precomputed values, may be faster than an O(n) method involving integer division, which is a relatively slow operation on modern processors. For n large enough so that the n! does not fit into a machine word, the "O(n) if order-n! integer operations are O(1)" argument stops working. So, you may be better off for both small and large n if you don't insist on it being theoretically O(n).

Answer 2

Update: possible dupe of Finding n-th permutation without computing others, see there for algorithm.

If len(l) will be small, you could precompute perm_index = permutations(range(len(l))) and use it as a list of lists of indexes into your actual data.

Moreover, if you have a list of permutations from range(len(l)) and you need one for for range(len(l) - 1) you can do something like:

[x - 1 for x in perm_index[i][1:]]

Which takes advantage of the fact that the permutations are in sorted order when generated.

Answer 3

Based on http://www.2ality.com/2013/03/permutations.html here's a possible solution. As @Gassa pointed out, elements.pop is not constant in order, and hence the solution is not linear in the length of the list. Therefore, I won't mark this as an accepted answer. But, it does the job.

def integerToCode(idx, permSize):                                                                                                                                       
    if (permSize <= 1):                                                                                                                                                 
        return [0]                                                                                                                                                      
    multiplier = math.factorial(permSize-1)                                                                                                                             
    digit =idx / multiplier                                                                                                                                             
    return [digit] +  integerToCode(idx % multiplier, permSize-1)                                                                                                       


def codeToPermutation(elements, code):                                                                                                                                  
    return map(lambda i: elements.pop(i), code)                                                                                                                         

def get_permutation(l, i):                                                                                                                                              
    c = integerToCode(i, len(l))                                                                                                                                        
    return codeToPermutation(list(l), c)

Answer 4

This solution works in O(1) (runtime complexity; amortised cost for dictionary lookups):

Code

#!/usr/bin/env python

import itertools


def get_permutation():
    memoize = {}

    def _memoizer(l, i):
        if str(l) in memoize and i not in memoize[str(l)]:
            memoize[str(l)][i] = memoize[str(l)]['permutations'].next()
        else:
            p = itertools.permutations(l)
            memoize[str(l)] = {'permutations': p}
            memoize[str(l)][i] = memoize[str(l)]['permutations'].next()
        return memoize[str(l)][i]
    return _memoizer

if __name__ == '__main__':
    get_permutation = get_permutation()
    l1 = list(range(10))
    l2 = list(range(5))
    print(get_permutation(l1, 1))
    print(get_permutation(l1, 20))
    print(get_permutation(l2, 3))

Output

(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
(0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
(0, 1, 2, 3, 4)

How it works

The code stores all past calls in a dictionary. It also stores the permutation object(s). So in case a new permutation gets requested, the next permutation is used.

The code uses itertools.permutations

Answer 5

A bit too late... C# code that should give you the result you expect:

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

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