8

与えられた と の順列についてN、の番目の順列を辞書順にk見つける関数があります。また、順列 が与えられた場合、 のすべての順列の中から順列の辞書式インデックスを見つける関数があります。これを行うには、この回答で提案されている「階乗分解」を使用しました。kNpermN

の整数パーティションに対して同じことをしたいと思いますN。たとえばN=7、インデックス (左) とパーティション (右) の間を行き来できるようにしたい:

 0 ( 7 )
 1 ( 6 1 )
 2 ( 5 2 )
 3 ( 5 1 1 )
 4 ( 4 3 )
 5 ( 4 2 1 )
 6 ( 4 1 1 1 )
 7 ( 3 3 1 )
 8 ( 3 2 2 )
 9 ( 3 2 1 1 )
10 ( 3 1 1 1 1 )
11 ( 2 2 2 1 )
12 ( 2 2 1 1 1 )
13 ( 2 1 1 1 1 1 )
14 ( 1 1 1 1 1 1 1 )

私はいくつかのことを試しました。私が思いついた最高のものは

sum = 0;
for (int i=0; i<length; ++i)
  sum += part[i]*i;
return sum;

これにより、次のようになります。

 0  0( 7 )
 1  1( 6 1 )
 2  2( 5 2 )
 3  3( 5 1 1 )
 3  4( 4 3 )
 4  5( 4 2 1 )
 6  6( 4 1 1 1 )
 5  7( 3 3 1 )
 6  8( 3 2 2 )
 7  9( 3 2 1 1 )
10 10( 3 1 1 1 1 )
 9 11( 2 2 2 1 )
11 12( 2 2 1 1 1 )
15 13( 2 1 1 1 1 1 )
21 14( 1 1 1 1 1 1 1 )

これはうまくいきませんが、正しい軌道に乗っているようです。これを思いついたのは、数字を下に移動する必要がある回数をカウントするためです ( 6,3,2goes toのように6,3,1,1)。ただし、物事を再結合する必要がある場合を説明する方法がわからないため、修正方法がわかりません（ のよう6,3,1,1に6,2,2）。

4

2 に答える 2

2

「階乗分解」が順列に対して機能する理由を考えてみてください。ここでも同じロジックが機能します。k!ただし、オブジェクトの順列の数に​​を使用する代わりに、最大部分が最大の の分割数にk分割関数を使用する必要があります。の場合、これらの数値は次のとおりです。p(n,k)nkn=7

k | p(7,k)
0 | 0
1 | 1
2 | 4
3 | 8
4 | 11
5 | 13
6 | 14
7 | 15

(3,2,1,1)たとえば、の辞書式インデックスを取得するには、次のように計算します。

p(3+2+1+1) - [ p(3+2+1+1,3-1) + p(2+1+1,2-1) + p(1+1,1-1) + p(1,1-1) ] - 1

です15 - [4 + 1 + 0 + 0] - 1 = 9。ここでは、最大部分が 3 未満の 7 のパーティションの数に加えて、最大部分が 2 未満の最大部分の 4 のパーティションの数に加えて ... 同じロジックでこれを逆にすることができます。C では、(テストされていない!) 関数は次のとおりです。

int
rank(int part[], int size, int length) {
    int r = 0;
    int n = size;
    int k;
    for (int i=0; i<length; ++i) {
        k = part[i];
        r += numPar(n,k-1);
        n -= k;        
    }
    return numPar(size)-r;
}

int
unrank (int n, int size, int part[]) {
    int N = size;
    n = numPar(N)-n-1;

    int length = 0;

    int k,p;
    while (N>0) {
        for (k=0; k<N; ++k) {
            p = numPar(N,k);
            if (p>n) break;
        }
        parts[length++] = k;
        N -= k;
        n -= numPar(N,k-1);
    }
    return length;
}

ここでは、numPar(int n)のパーティションの数を返す必要があり、最大部分が最大の のパーティションの数を返す必要があります。これらは、再帰関係を使用して自分で記述できます。nnumPar(int n, int k)nk

于 2014-01-24T22:00:49.980 に答える
0 
#include <stdio.h>

// number of combinations to divide by the number of k below n
int partition(int n, int k){
    int p,i;

    if(n<0) return 0;
    if(n<2 || k==1) return 1;
    for(p=0,i=1;i<=k;i++){
        p+=partition(n-i,i);
    }
    return p;
}

void part_nth_a(int n, int k, int nth){
    if(n==0)return;
    if(n== 1 || n==k && nth == 0){
        printf("%d ", n);
        return ;
    }
    int i, diff;
    for(i=0;i<k;++i){
        diff = partition(n, k-i) - partition(n, k-i-1);
        if(nth < diff){
            printf("%d ", k-i);
            n -= (k-i);
            if(diff == 1)
                part_nth_a(n, k-i, 0);
            else
                part_nth_a(n, k-i, nth);
            return;
        }
        nth -= diff;
    }
}

void part_nth(int n, int nth){
    if(nth == 0){
        printf("%d ", n);
        return ;
    }
    int i, j, numOfPart;
    for(i=1;i<n;++i){
        numOfPart = n-i < i ? partition(i, n-i) : partition(i, i);
        if(nth <= numOfPart)
            break;
        nth -= numOfPart;
    }
    printf("%d ", n-i);
    if(n-i < i)
        part_nth_a(i, n-i, nth-1);
    else
        part_nth_a(i, i, nth-1);
}

int main(){
    int n = 7;
    int i, numOfPart = partition(n, n);
    for(i=0;i<numOfPart;++i){
        printf("%2d ( ", i);
        part_nth(n, i);
        printf(")\n");
    }
    return 0;
}
于 2014-01-25T06:52:21.820 に答える