combinatorics - 下一步将n分解为k个部分-有人有有效的算法吗？

Question

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想要改善这个问题吗？更新问题，以便将其作为 on-topic用于堆栈溢出。

在12个月前关闭。



Improve this question




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

例如，如果我有n个多维数据集和k个袋子，并想列出袋子中所有可能的多维数据集排列。例如您可以通过3种方式将2个立方体放入2个袋子:

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

我找到了新汉的对数。我在Fortran中找到了它的 here版本(第46页)，但没有在Fortran中进行编码，因此无法真正了解正在发生的事情-有帮助吗？

最佳答案

您尝试列出的内容称为k多重组合。通常以这种方式说明问题:给定n个无法区分的球和k个盒子，列出所有可能的方式将所有球分配到盒子中。此类分布的数量为:

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

有关更多背景信息，请参见 Twelve-Fold Way的方法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)

关于combinatorics - 下一步将n分解为k个部分-有人有有效的算法吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4647120/

上一篇：visual-studio - Visual Studio 2017 占用本地 AppData 文件夹中的磁盘空间

下一篇：ruby-on-rails - 为什么 Rails 应用程序在底部显示数据库信息？

相关文章：

algorithm - 这个游戏的名字是什么？

java - 如何获得 N 组合 R 中的第 k 项

algorithm - 从有限值列表中寻找目标值的组合算法

c# - X 的所有可能组合分成 N 个堆栈

c# - 我在 C# 中选择 k 元素子集来处理大量数据的算法

python - 给定一个数字列表，找到所有矩阵，使得每列和每行的总和为 264

javascript - 查找总和为目标值的给定大小列表的子集

c++ - C++中的组合数(N选R)

ruby - 在 Ruby 中生成所有可能的字符串排列

java - Project Euler 9 解决方案没有给出正确的结果

Answer 1

您尝试列出的内容称为k多重组合。通常以这种方式说明问题:给定n个无法区分的球和k个盒子，列出所有可能的方式将所有球分配到盒子中。此类分布的数量为:

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

有关更多背景信息，请参见 Twelve-Fold Way的方法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)