接下来将n组成k部分 - 是否有人有工作算法？

Question

将n组成k部分 - 我想将n的所有可能成分列入k部分 - 是否有人有算法(最好是R)？或者知道它是否在图书馆的任何地方？

例如,如果我有n个立方体和k个袋子,并且想要列出袋子中立方体的所有可能排列.例如,有3种方法可以将2个立方体分成2个袋子:

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

我找到了NEXCOM的算法.我发现一个版本,它在这里用Fortran(第46页),但在Fortran中没有代码,所以真正了解发生了什么事情-任何帮助吗？

Answer 1

因为我花了一些精力来阅读其他c ++解决方案的意图,这里转换为python(也作为生成器结果而不是字符串):

def weak_compositions(boxes, balls, parent=tuple()):
  if boxes > 1:
    for i in xrange(balls + 1):
      for x in weak_compositions(boxes - 1, i, parent + (balls - i,)):
        yield x
  else:
    yield parent + (balls,)

测试:

>>> for x in weak_compositions(3, 5): print x
(5, 0, 0)
(4, 1, 0)
(4, 0, 1)
(3, 2, 0)
...
(0, 1, 4)
(0, 0, 5)

Answer 2

你试图列出的内容称为k -multicombination.问题通常以这种方式陈述:给出n个难以区分的球和k个盒子,列出所有可能的方法来分配盒子中的所有球.此类分发的数量为:

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

有关更多背景信息,请参阅十二折方式的方法4 .

这是枚举分布的代码(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个球):

(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)