获取列表的第i个排列 [英] Getting the ith permutation of a list

问题描述

我需要一个Fortran代码来计算给定列表的第i个排列{1,2,3，...，n}，而不需要计算所有的排列，即n !.
有没有人可以帮助我？对于大数字，以下实现可以避免溢出错误。

 ！ Fattoriale 
 RECURSIVE FUNCTION factorial（n）RESULT（n_factorial）
 IMPLICIT NONE 
 REAL :: IN $ :: b $ b 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（nk）） 
 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 
  

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.

解决方案

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

这篇关于获取列表的第i个排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！