对于排列,给定N
和k
,我有一个函数,它以字典顺序找到N
第k
个排列。 另外,给定一个置换perm
,我有一个函数,可以在N
所有排列中找到排列的词典索引。 为此,我使用了本答案中建议的“因子分解”。
现在我想对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,2
到6,3,1,1
)。 我不知道如何解决它,因为我不知道如何解决事情必须重新组合(如6,3,1,1
到6,2,2
)。
想想为什么“因子分解”适用于排列,同样的逻辑在这里起作用。 但是,而不是使用k!
对于k
对象的排列k
,必须使用分区函数p(n,k)
表示n
的最大部分为k
的分区k
。 对于n=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
。 在这里,您计算的是7个分区的数量,其中最大部分小于3加上4个分区的数量,最大部分小于2加…相同的逻辑可以反转这一点。 在C中,(未经测试的!)函数是:
int rank(int part[], int size, int length) { int r = 0; int n = size; int k; for (int i=0; i0) { for (k=0; kn) break; } parts[length++] = k; N -= k; n -= numPar(N,k-1); } return length; }
这里numPar(int n)
应该返回numPar(int n)
的分区n
, numPar(int n, int k)
应该返回n
的分区数,其中最大部分最多为k
。 您可以使用递归关系自己编写。
需要了解更多c/c++开发分享查找整数分区的字典顺序,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
#include // 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(ni,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
以上就是c/c++开发分享查找整数分区的字典顺序相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980202.html