1

Is there a generator function f(i,j,n) that returns, in deterministic constant time and space, the ith element (0<=i<n) of the jth permutation (0<=j<n!) of the first n integers? If so, how does it work? If not, can I see a disproof?

This question is related to this one: Create a random permutation of 1..N in constant space However, in this case, we want to be able to generate every permutation, depending on our choice of j, not just a particular or arbitrary one.

It's also related to this one: Random access random permutations (In fact, it's probably exactly the sort of thing the author of that question would have liked to have, though I can't be sure this is not more specific and constrained. In any case, I am not interested in parallelization.)

If it IS possible, then I also would like to know if we can eliminate the parameter j (since its length is O(n)) and just generate a permutation chosen uniformly at random without having to name it first.

If it is NOT possible, then I wonder if it's possible to probabilistically (but still in deterministic linear-time and constant space) generate a uniformly chosen permutation. For instance, a method that produces a uniformly chosen sequence which happens to also be a permutation >1% of the time.

I am asking this question because all of the methods I know for generating permutations require either storing the range of values to be permuted explicitly, or at least storing all the numbers which have been generated so far.

Community
  • 1
  • 1
quintopia
  • 121
  • 5
  • https://en.wikipedia.org/wiki/Factorial_number_system – phs Oct 03 '14 at 08:16
  • 1
    @phs I am aware of factoriadics, and had considered a solution involving them, but I couldn't figure out how to use them as inversion vectors to construct a particular permutation without storing all parts of the permutation already generated on the stack, and the goal here is to be able to find an element in the permutation /without/ knowing any (or many) of the other elements in the permutation – quintopia Oct 03 '14 at 15:37

1 Answers1

2

I did something similar for this problem a while ago.

With a little modification for your problem, it will generate directly the jth permutation and then pick its ith element.

#!/usr/bin/env python3

from math import factorial

def getJthPermutation(initList, j):
    j -= 1

    result = ""
    fac = factorial(len(initList) - 1)
    for div in range(len(initList) - 1, 0, -1):
        k = j // fac
        result += initList[k]
        del initList[k]

        j %= fac

        fac //= div
    result += initList[0]

    return result


def fct(i, j, n):
    list = [str(k) for k in range(n+1)]

    permutation = getNPermutation(list[:], j)

    return permutation[i]


if __name__ == "__main__":
    print(fct(3,1000000,9))
    print(fct(3,1,9))
    print(fct(1,factorial(9), 9))

(if you don't have python installed)

The complexity will still depends on n, but not on i nor j (if I am not mistaken).

ZomZom
  • 132
  • 5
  • 2
    Looks decent, but will be O(n^2) because calculating a single factorial is O(n), and you do this inside an O(n) loop. You could fix this by calculating the factorial just once before the loop, and dividing `fac` by `div` at the end of each loop cycle. – j_random_hacker Oct 02 '14 at 08:21
  • 1
    A bigger problem is that explicitly calculating n! requires O(n*lg(n)) space to store the result. I'm looking for a constant space solution. – quintopia Oct 03 '14 at 05:02