Next将n分解为k个部分-有人能用算法吗？ [英] Next Composition of n into k parts - does anyone have a working algorithm?

问题描述

将 n 组成为 k 的部分-我想将n的所有可能组成都列出为k个部分-有人有算法吗（最好在R中）？还是知道它是否在图书馆的任何地方？

Composition of n into k parts - I want to list all the possible compositions of n into k parts - does anyone have an algorithm (preferably in R)? Or know if it's in library anywhere?

例如，如果我有 n 个立方体和 k 个袋子，并希望列出袋子中所有可能的立方体排列方式。例如您可以通过3种方式将2个立方体放入2个袋子：

For example, if I have n cubes, and k bags, and want to list all the possible arrangements of the cubes in the bags. e.g. there are 3 ways you can arrange 2 cubes into 2 bags:

(2, 0) (1, 1) (0, 2)

我找到了NEXCOM的对数。我在此处（第46页）中找到了它的版本Fortran，但不使用Fortran进行编码，因此真的了解发生了什么-有帮助吗？

I've found the NEXCOM alogarithm. I've found a version of it here (page 46) in Fortran, but don't code in Fortran so really understand what's going on - any help?

推荐答案

您要尝试列出的内容被称为 k 多重组合。通常以这种方式陈述问题：给定 n个不可区分的球和 k 盒子，列出所有可能的方式来分配盒子中的所有球。这样的分布数为：

What you are attempting to list is called an k-multicombination. The problem is often stated this way: given n indistinguishable balls and k boxes, list all possible ways to distribute all of the balls in the boxes. The number of such distributions is:

factorial(n + k - 1) / (factorial(k - 1) * factorial(n))

有关更多背景信息，请参见十二折方式。

For further background, see Method 4 of the Twelve-Fold Way.

这是代码列举分布情况（C ++）：

Here is the code to enumerate the distributions (C++):

string & ListMultisets(unsigned au4Boxes, unsigned au4Balls, string & strOut = string ( ), string strBuild = string ( ))
{
    unsigned au4;
    if (au4Boxes > 1) for (au4 = 0; au4 <= au4Balls; au4++)
    {
        stringstream ss;
        ss << strBuild << (strBuild.size() == 0 ? "" : ",") << au4Balls - au4;
        ListMultisets (au4Boxes - 1, au4, strOut, ss.str ( ));
    }
    else
    {
        stringstream ss;
        ss << "(" << strBuild << (strBuild.size() == 0 ? "" : ",") << au4Balls << ")\n";
        strOut += ss.str ( );
    }
    return strOut;
}



int main(int argc, char * [])
{    
    cout << endl << ListMultisets (3, 5) << endl;
    return 0;
}

这是上述程序的输出（5个球分布在三个框中） ：

Here is the output from the above program (5 balls distributed over three boxes):

(5,0,0)
(4,1,0)
(4,0,1)
(3,2,0)
(3,1,1)
(3,0,2)
(2,3,0)
(2,2,1)
(2,1,2)
(2,0,3)
(1,4,0)
(1,3,1)
(1,2,2)
(1,1,3)
(1,0,4)
(0,5,0)
(0,4,1)
(0,3,2)
(0,2,3)
(0,1,4)
(0,0,5)

这篇关于Next将n分解为k个部分-有人能用算法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！