java - 生成一组到另一组的所有可能（无序）分配的算法

问题描述

鉴于：

一组颜色独特的蜡笔（大小为 x）。
一组孩子。
所有的蜡笔都必须分配给孩子们。
一个孩子可能有零到 x 支蜡笔。
每支蜡笔最终都应该有 1 个孩子。蜡笔不能分配给 2 个或更多的孩子。

我如何去寻找所有可能的分配组合？

例如：

class Crayon {
    String color;

    public Crayon(String color) {
        this.color = color;
    }

    public String getColor() {
        return color;
    }

    @Override
    public String toString() {
        return color;
    }
}


class Child {

    String name;
    Set<Crayon> crayons;

    public Child(String name) {
        this.name = name;
        crayons = new HashSet<Crayon>();
    }

    public void addCrayon(Crayon crayon) {
        crayons.add(crayon);
    }

    public Set<Crayon> getCrayons() {
        return crayons;
    }

    @Override
    public String toString() {
        return "Child [name=" + name + ", crayons=" + crayons + "]";
    }
}

public class DistributeCrayons {

    public static void main(String[] args) {

        Set<Crayon> crayons = new HashSet<>();
        crayons.add(new Crayon("red"));
        crayons.add(new Crayon("blue"));
        crayons.add(new Crayon("green"));
        crayons.add(new Crayon("orange"));
        crayons.add(new Crayon("brown"));
        crayons.add(new Crayon("yellow"));
        crayons.add(new Crayon("purple"));

        Child bob = new Child("bob");
        Child amy = new Child("amy");
        Child tom = new Child("tom");

        for(??) {
            for(??) {
                ??
                    System.out.println(bob +" "+ amy +" "+ tom);
                ??
            }
        }
    }
}

这应该输出所有可能的分配组合，例如：

孩子 [name=bob, crayons=[green, blue]] 孩子 [name=amy, crayons=[brown, red]] 孩子 [name=tom, crayons=[yellow, Purple, orange]]

孩子 [name=bob, crayons=[]] 孩子 [name=amy, crayons=[brown, red, blue]] 孩子 [name=tom, crayons=[yellow, Purple, orange, green]]

孩子 [name=bob, 蜡笔=[红色]] 孩子 [name=amy, 蜡笔=[棕色, 绿色, 紫色, 橙色]] 孩子 [name=tom, 蜡笔=[蓝色, 黄色]]

等等

更新

感谢大家提供宝贵的反馈，并感谢 גלעד ברקן 提供有效的 js 解决方案。（对不起，由于声誉计数，我无法投票或接受答案）。

我现在可以绕过它了，这是我的解决方案版本：

我将蜡笔和儿童转换为列表而不是集合。对于 7 支蜡笔（红色、蓝色、绿色、橙色、棕色、黄色、紫色）的列表，我的目标是生成三个孩子 bob (id="b")、amy (id="a") 和tom (id="t") 形式为 7 个字符的单词。例如：像“tbbbtat”这样的词意味着汤姆得到了红色、棕色和紫色的蜡笔，鲍勃得到了蓝色、绿色和橙色的蜡笔，艾米得到了黄色的。

public class DistributeCrayons {

    public static void main(String[] args) {

        List<Crayon> crayons = new ArrayList<>();
        crayons.add(new Crayon("red"));
        crayons.add(new Crayon("blue"));
        crayons.add(new Crayon("green"));
        crayons.add(new Crayon("orange"));
        crayons.add(new Crayon("brown"));
        crayons.add(new Crayon("yellow"));
        crayons.add(new Crayon("purple"));

        List<Child> children = new ArrayList<>();
        children.add(new Child("b"));
        children.add(new Child("a"));
        children.add(new Child("t"));

        List<String> assignments = null;
        for(int i = 0; i < crayons.size(); i++)
            assignments = addCrayonCombos(assignments, children);

        System.out.println(assignments);

    }

    static List<String> addCrayonCombos(List<String> assignments, List<Child> children) {
        if(assignments == null) {
            assignments = new ArrayList<String>();
            for(Child c: children)
                assignments.add(c.getId());
            return assignments;
        } else {
            List<String> updatedAssignments = new ArrayList<String>();
            for(String assignment: assignments) {
                for(Child c: children)
                    //append next permutations for a new crayon to existing "words"
                    updatedAssignments.add(assignment+c.getId());
            }
            return updatedAssignments;
        }
    }
}

这会生成预期的分配词列表（准确地说是 2187 个词），因为 7 支蜡笔中的每支都有 3 种可能性（即 3^7 = 2187）。

标签： javaalgorithmloopscollections

解决方案

如果我正确理解您的问题，这将比几个嵌套for循环复杂得多。

我会给你一个问题陈述和一些伪代码，也许你可以从中实现它。

你有两套：

蜡笔套装。我们称之为C.
人定了。我们称之为P.

在你的例子中，

C = {"red", "orange", "yellow", "green", "blue", "purple", "brown"}
P = {"bob", "amy", "tom"}

因此，您需要实现一个函数DistributeCrayons(Set<People> P, Set<Crayons> C)，该函数可以找到在C人群中分配蜡笔的所有方法，我们可以针对任何给定的分配P向每个人提供零个或多个蜡笔。如果至少一个人有一支蜡笔，而他们没有，那么两种P分布是不同的ABPAB

我将给出一个递归实现，因为这将是最容易考虑的：

DistributeCrayons(Set<People> P, Set<Crayons> C):
    for subset C' of C:
        for person P' in P:
            assign C' to P'

            if (P - P') == {}:
                return assignments
            else:
                DistributeCrayons(C - C', P - P')

在哪里：

for subset C' of C 在给定的迭代中遍历所有可能的子集C并分配C'给其中之一。

for person P' in P: 只是迭代P——在每次迭代中获取一个人。

assign C' to P' 将一组蜡笔分配C'给 person P'（意味着该人P'获得 set 中的所有蜡笔C'。）

{} 是空集。所以，if语句：if (P - P') == {}只检查是否是传递给P'的人集中的唯一人。PDistributeCrayons(...)

注意：我实际上并没有处理作业以及如何编码它们。这将比我在伪代码中显示的方式更复杂，因为每次调用时都必须重置分配DistributeCrayons(...)

~~我会继续思考这个问题，看看我是否能想出一个实际的代码片段给你。~~

更新：看起来你自己解决了。好的！

java - 生成一组到另一组的所有可能（无序）分配的算法

问题描述

解决方案

推荐阅读