使用递归生成可能的值分配结果

Question

我正在尝试提出一种递归算法来生成所有可能的子 - 父分配可能性，给定完全随机性。

例如，假设我有 3 个孩子和 2 个父母，所有孩子将被随机分配给每个父母，可能的结果如下

   Parent 1       Parent 2
   0 Children     3 Children
   1 Children     2 Children
   2 Children     1 Children 
   3 Children     0 Children   

我一直在尝试一种方法来递归地提供孩子的数量和父母的数量以及其他变量来跟踪当前状态，但一直找不到任何有效的方法。它需要适用于任何给定数量的父母和孩子。

有人有什么想法吗？我正在用 Java 编码，尽管它不是代码，而是我需要帮助的算法。

Answer 1

假设你有 n 个孩子和 k 个父母。那么以下算法（在伪 java 中）应该可以工作：

int[] childrensForParent = new int[k];
/**
* Method assigns numberOfChildren children to parents with indices from 
* parentIndex to k-1
*/
void assignChildren(int parentIndex, int numberOfChildren) {
    if(parentIndex==k-1) {
         //All children left go to the last parent in a row
         childrensForParent[parentIndex] = numberOfChildren;
         //Do something with the result
         output(childrensForParent);
         return;
    } 
    for(int childrenCount= 0; childrenCount<=numberOfChildren; childrenCount++) {
        //assign children to current parent
        childrensForParent[parentIndex] = childrenCount;
        //assign children that left to next parents
        assignChildren(parentIndex+1, numberOfChildren-childrenCount);
    }
}
//Method call
assignChildren(0,n);

简短说明：

1. 如果您只有一个父级，则分配剩余的所有子项
2. 否则，如果您有k父母和n孩子
   1. 对于每个可能的孩子计数x（从 0 到 n）
      1. 将x子项分配给当前父项
      2. 将n-x子项分配给其余（k-1）父项（递归调用）。

附加信息：上面的算法将n的所有非负分区生成为k部分。查看这些文章：

• 维基百科上的分区;
• 关于此类分区数量的 Math.SE 问题

Answer 2

这一切都是完全未经测试的，但您可以从以下逻辑/伪代码开始：

// Define your starting objects/data
define a parent object that has a list field of children
define "parents" as an array of parent objects
define "children" as an array of children objects
// Prepare the data
randomize the "children" array via a shuffling algorithm
// Define your recursive method
define recursiveAssignChildren(parents, children):
    if children is empty, exit method
    take the first element of "children" and assign it to a random parent
    define lessChildren as children, excluding the first element that was already assigned to a parent
    call recursiveAssignChildren(parents, lessChildren)
// Call the recursive method to start process
call recursiveAssignChildren(parents, children)

Answer 3

许多问题都戴着问题设置者制作的封面。这可以通过在有人告诉你谜语时解决问题来实现（长句子，信息较少）。所以，要发现这个问题，你是这样想的：而不是处理这个问题，因为孩子需要以所有可能的方式分配给父母，你有两个数字 n1、n2（分别是父母的孩子数），你想使用 n1 加法添加 n1，所以如果你有 3 个孩子需要分配给 2 个父母，你想使用 3 个加法运算形成 2

个

   void generateAll(int c, int p, string str)
{
    if (c == 0 && p == 0)
    {
        cout << str << endl;
        return;
    }
    // if there are no parents and c > 0 then no children going to be asigned to any parent
    if (p == 0 && c > 0)
        return;
    // loop throug number of children 
    for (int i = 0; i <= c; i++)
    {
        generateAll(c - i, p - 1, str + "t"+ toString(i));
    }
}