java算法生成一个集合到另一个集合的所有可能（无序）赋值

Question

鉴于：

1. 一套颜色独特的蜡笔（尺寸为x）
2. 一群孩子
3. 所有的蜡笔都必须分配给孩子们
4. 一个孩子可能有零到x支蜡笔
5. 每支蜡笔的结尾应该正好有一个孩子。不能将蜡笔分配给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);
                ??
            }
        }
    }
}

这将输出所有可能的赋值组合，例如：

孩子[姓名=鲍勃，蜡笔=[绿色，蓝色]]孩子[姓名=艾米，蜡笔=[棕色，红色]]孩子[姓名=汤姆，蜡笔=[黄色，紫色，橙色]]

Child[name=bob，crayons=[]Child[name=amy，crayons=[棕色，红色，蓝色]]Child[name=tom，crayons=[黄色，紫色，橙色，绿色]]

Child[name=bob，crayons=[red]]Child[name=amy，crayons=[brown，green，purple，orange]]Child[name=tom，crayons=[blue，yellow]]

等等

更新

感谢大家的宝贵反馈，并感谢大家提供了一个可行的js解决方案。（很抱歉，由于声誉问题，我无法投票或接受答案）

我现在可以把我的头绕在它周围了，这是我的解决方案版本：

我把蜡笔和孩子们变成了列表而不是集合对于7支蜡笔（红色、蓝色、绿色、橙色、棕色、黄色、紫色）的列表，我的目标是以7个字符的单词的形式生成三个孩子bob（id=“b”）、amy（id=“a”）和tom（id=“t”）的所有作业例如：“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）

Answer 1

孩子们有点诡计。如果我们迭代这些蜡笔，然后依次将它们分配到不同的框中，我们就可以得到分配它们的所有方法。然后，我们可以根据自己的意愿给这些盒子贴上标签（或者按顺序给孩子们）

JavaScript代码：

；

；

function f(cr, ch, x, comb=[], i=0){
  if (ch.length * x < cr.length)
    return [];
    
  if (i == cr.length)
    return [comb];
    
  let result = [];
  
  for (let j=0; j<ch.length; j++){
    let _comb = ch.map((_, idx) =>
      comb[idx] ? comb[idx].slice() : []);
    
    if (_comb[j].length == x)
      continue;

    _comb[j].push(cr[i]);
    
    result = result.concat((f(cr, ch, x, _comb, i + 1)));
  }

  return result;
}

var crayons = ["red", "blue", "green", "orange", "brown", "yellow"];

var children = ["bob", "amy", "tom"];

var str = "";

for (let comb of f(crayons, children, 3))
  str += JSON.stringify(comb) + "\n";

console.log(str);

；

；

；

Answer 2

如果我正确理解了你的问题，这将比几个嵌套的for循环更加复杂

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

你有两套：

1. 蜡笔组。我们称之为C
2. 人们开始行动了。我们称之为P

在你的例子中

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

所以你需要实现一个函数DistributeCrayons(Set<People> P, Set<Crayons> C)，找到所有的方法在C中的人之间分配蜡笔，我们可以给P中的每个人零个或多个蜡笔，用于任何给定的分配。如果{}中至少有一个人在{}中有一支他们在{}中没有的蜡笔，那么{}和{}两种分布是不同的

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

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'（意思是person P'获取集C'中的所有蜡笔。）

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

注意：我还没有实际处理作业以及如何编写作业。这将比我在伪代码中显示的方式更加复杂，因为每次调用DistributeCrayons(...)

我会继续思考这个问题，看看是否能拿出一个真正的代码片段来给你

更新：看起来是你自己解决的。很好

Answer 3

有趣的问题。想到的解决方案结合了排列和分区。首先，把蜡笔列表的每一个排列都取下来。对于排列，有一些众所周知的算法，搜索应该会找到大量的算法

对于列表的每个排列，将列表分成三个部分，并将每个部分的蜡笔分配给三个子项。这应该会产生每一种可能的方式来分配蜡笔给孩子们

要将七支蜡笔的列表分为三部分，您需要将其分为两个位置。第一个将位于列表中从元素0之前到元素6之后的任何位置（包括6）。第二组的位置将与第一组相同，直到列表末尾（第6部分之后），也包括在内。最好将这些中断视为发生在列表的两个元素之间

分区可以通过嵌套循环完成

共有5040个排列，我相信每个排列有36个分区，所以如果我没弄错的话，总共应该有181440种方式来分配蜡笔。我不认为这种方法会有任何重复，但我还没有证明