找到一个整数分区的字典序 [英] Find the lexicographic order of an integer partition
问题描述
有关排列,给予 N
和 K
,我有一个函数,找到氏/ code>次方
N
字典顺序排列。此外,由于置换烫发
,我有一个函数,将查找 N
所有排列中排列的词典指数。要做到这一点,我用了因子分解如建议这个答案。
For permutations, given N
and k
, I have a function that finds the k
th permutation of N
in lexicographic order. Also, given a permutation perm
, I have a function that finds the lexicographic index of the permutation among all permutations of N
. To do this, I used the "factorial decomposition" as suggested in this answer.
现在我想要做同样的事情为 N
整数分区。例如, N = 7
,我希望能够索引(左)和分区之间来回(右):
Now I want to do the same thing for integer partitions of N
. For example, for N=7
, I want to be able to back and forth between the index (left) and the partition (right):
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 )
我已经尝试了几件事情。我想出了最好的是
I've tried a few things. The best I came up with was
sum = 0;
for (int i=0; i<length; ++i)
sum += part[i]*i;
return sum;
这给了以下内容:
which gives the following:
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,2
进入 6, 3,1,1
)。我看不出如何解决它,但是,因为我不知道该如何解释,当事情已经得到重组(如 6,3,1,1
进入 6,2,2
)。
This doesn't quite work, but seems to be on the right track. I came up with this because it sort of counts how many times I have to move a number down (like 6,3,2
goes to 6,3,1,1
). I can't see how to fix it, though, because I don't know how to account for when things have to get recombined (like 6,3,1,1
goes to 6,2,2
).
推荐答案
想想为什么因子分解工程变更和相同的逻辑在这里工作。但是,而不是使用 K!
为 K
对象,必须使用分区功能<的排列数code> P(N,K)为分区的数量 N
至多 K <最大的部分/ code>。对于
N = 7
,这些数字是:
Think about why the "factorial decomposition" works for permutations, and the same logic works here. However, instead of using k!
for the number of permutations of k
objects, you must use the partition function p(n,k)
for the number of partitions of n
with largest part at most k
. For n=7
, these numbers are:
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
。在这里,我们计算的7大一部分分区小于3的数量加4个分区具有最大的部分不到2加......同样的逻辑可以扭转这个数。在C中,(!未经测试)功能是:
which is 15 - [4 + 1 + 0 + 0] - 1 = 9
. Here you're computing the number of partitions of 7 with largest part less than 3 plus the number of partitions of 4 with largest part less than 2 plus ... The same logic can reverse this. In C, the (untested!) functions are:
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;
}
下面数参(INT N)
应返回 N
和数参(INT N,INT K)
应该返回的分区数 N
至多 K <最大的部分/ code>。您可以使用递推关系写这些吧。
Here numPar(int n)
should return the number of partitions of n
, and numPar(int n, int k)
should return the number of partitions of n
with largest part at most k
. You can write these yourself using recurrence relations.
这篇关于找到一个整数分区的字典序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!