Getting the ith permutation of a list

Question

I need a fortran code that calculates the ith permutation of a given list {1,2,3,...,n}, without computing all the permutations, that are n!. Is there anyone that can help me? Thank you in advance.

I don't know Fortran, nor Mathematica, but developed such an algorithm for Scala - maybe you can read and reprduce it: [https://stackoverflow.com/a/8958309/312172] — user unknown, Feb 22 '16 at 03:21
I would advise you to search harder for a more procedural starting point, unless you want to write a recursive fortran function. In that case take a stab at it and show where you get stuck. — agentp, Feb 22 '16 at 18:55

score 1 · Answer 1 · answered Feb 22 '16 at 22:41

I solved my problem. In the following I show you both the Mathematica and Fortran codes I implemented. If you have any advise for improve them, do not esitate to comment.

MATHEMATICA (example: 10° permutation of {1,2,3,4,5})

n = 5;
i = 10;
p = Range[n];
ithPermutation = p;
Do[f = (n - k)!;
d = Floor[i/f];
ithPermutation[[k]] = p[[d + 1]];
p = Drop[p, {d + 1}];
i = Mod[i, f], {k, 1, n}];

FORTRAN

SUBROUTINE ith_permutazione(lista_iniziale,n,i,ith_permutation)
IMPLICIT NONE
INTEGER :: j,k,f
INTEGER, INTENT(IN) :: n,i
INTEGER, DIMENSION(1:n), INTENT(IN) :: lista_iniziale
INTEGER, DIMENSION(1:n) :: lista_lavoro
INTEGER, DIMENSION(1:n), INTENT(OUT) :: ith_permutation
lista_lavoro=lista_iniziale
j=i
DO k=1,n
    f=factorial(n-k)
    ith_permutation(k)=lista_lavoro(FLOOR(REAL(j/f))+1)
    lista_lavoro=PACK(lista_lavoro,MASK=lista_lavoro/=ith_permutation(k))
    j=MOD(j,f)
ENDDO
ENDSUBROUTINE ith_permutazione

score 1 · Accepted Answer · answered Feb 26 '16 at 17:16

For big numbers the following implementations preserve from overflow errors.

        ! Fattoriale
        RECURSIVE FUNCTION factorial(n) RESULT(n_factorial)
        IMPLICIT NONE
        REAL, INTENT(IN) :: n
        REAL :: n_factorial
        IF(n>0) THEN
            n_factorial=n*factorial(n-1)
        ELSE
            n_factorial=1
        ENDIF
        ENDFUNCTION factorial

        ! ith-permutazione di una lista
        SUBROUTINE ith_permutazione(lista_iniziale,n,i,ith_permutation)
        IMPLICIT NONE
        INTEGER :: k,n
        REAL :: j,f
        REAL, INTENT(IN) :: i
        INTEGER, DIMENSION(1:n), INTENT(IN) :: lista_iniziale
        INTEGER, DIMENSION(1:n) :: lista_lavoro
        INTEGER, DIMENSION(1:n), INTENT(OUT) :: ith_permutation
        lista_lavoro=lista_iniziale
        j=i
        DO k=1,n
            f=factorial(REAL(n-k))
            ith_permutation(k)=lista_lavoro(FLOOR(j/f)+1)
            lista_lavoro=PACK(lista_lavoro,MASK=lista_lavoro/=ith_permutation(k))
            j=MOD(j,f)
        ENDDO
        ENDSUBROUTINE ith_permutazione

Getting the ith permutation of a list

2 Answers2

Linked