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

Question

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

例如，假设我有 3 children 和 2 parents，所有 children 将随机分配给每个 parent，可能的结果如下

   Parent 1       Parent 2

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

我一直在想办法以递归方式执行此操作，提供 children 的数量和 parents 的数量以及其他变量以跟踪当前状态，但无法找到任何有效的方法。它需要为任何给定数量的 parents 和 children 工作。

有人有什么想法吗？我在 Java 中编码，虽然它不是代码，而是我需要帮助的算法。

Answer 1

假设您有 n children 和 k parent。然后下面的算法（在 pseudo-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);

简短说明：

如果你只有一个 parent 分配所有 children 剩下的
否则，如果您有 k parent 和 n children
1. 对于每个可能的 children 计数 x（从 0 到 n）
  1. 将xchildren分配给当前的parent
  2. 将n-xchildren分配给剩余的(k-1)parents(递归调用)。

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

Answer 2

这一切都完全未经测试，但您可以从以下 logic/pseudo 代码开始：

// 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

很多问题都是穿着问题setter做的封面。这可以通过把问题当成某人告诉你的谜语（长句子，信息较少）来实现。所以，为了发现这个问题，你可以这样想：不是处理这个问题，因为 children 需要以所有可能的方式分配给 parents，你有两个数字 n1，n2（[= 的数量13=] 数量 parents 分别）并且你想使用 n2 添加添加 n1 所以如果你有 3 children 需要分配给 2 parents 在这里你想要形成 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));
    }
}

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

Using Recursion to Generate Possible Value Assignment Outcomes

algorithm

recursion

random