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

• jonrsharpe: Is there some particular order you want for the permutations, or do you just want each i to return a unique and consistent permutation?
• GermanK: Just that for each i, you get a unique and consistent permutation: I don't really care about the order
• jonrsharpe: Possibly related: stackoverflow.com/q/23502180/3001761
• barak manos: How can it possibly run in O(n) for every i between 0 and n!?
• jonrsharpe: @barakmanos that's the point, the OP doesn't want to generate all permutations and index into it, rather work out which permutation of l would be at index i.

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

• coproc: how to compute the representation of a number in the factorial number system with O(n) arithmetic operations? As I see it: it takes O(n) operations to find the first digit and then you have to proceed recursively with the rest - thus needing O(n^2) operations (in the worst and average case).
• Gassa: @coproc: Just start from the other end! Compute the last digit by taking the number modulo 1, and then divide it by 1. Compute the second last digit by taking the current number modulo 2, and then divide it by 2. And so on.

Answer 2

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 3

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.

• GermanK: But that's not a plausible solution because of the order: if I want to access the last permutation in the list, I have to precompute all the others first.

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

• GermanK: OK, that is strictly doing what I asked. However, I would like the solution to have referencial transparency. This solution doesn't.
• Gassa: Nice take on the problem here! And if we change the "next permutation in O(1)" strategy to "a new random permutation in O(n)", this can be a feasible approach for certain applications.

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