找到组合，给定n个带有x个球的框

我正在开发一个项目，其中我有三个盒子（截至目前），每个盒子都有一些颜色的球

所以我将它们存储在Map of String and List of String ，如下所示。

 Map<String, List> boxBallMap = new LinkedHashMap<String, List>(); 

上面地图中的数据可以是这样的 –

 {box1=[blue, red, orange]} {box2=[blue, red]} {box3=[blue, red, orange]} 

因此，盒子中球的可能组合可以是 –

（要点A） ::所有具有相同球数的盒子 –

 {box1=[blue, red, orange]} {box2=[blue, red, orange]} {box3=[blue, red, orange]} or 

（要点B） ::任何一个盒子都没有球。 所以让我们说box3没有任何球 –

 {box1=[blue, red, orange]} {box2=[blue, red, orange]} {box3=[]} or 

（要点C） ::有些盒子的球数较少。 所以我们说box2只有两个球 –

 {box1=[blue, red, orange]} {box2=[blue, red]} {box3=[blue, red, orange]} or 

（要点D） ::任何一个盒子都没有任何球。 所以让我们说box3和box2没有任何球 –

 {box1=[blue, red, orange]} {box2=[]} {box3=[]} 

问题陈述：-

根据上面的输入，我需要返回一个映射，它将是List<Map> ，让我们说（POINT A） ，下面的映射将作为输出返回 –

 [{box1=blue, box2=red, box3=orange}, {box1=red, box2=orange, box3=blue}, {box1=orange, box2=blue, box3=red}] 

在这里，如果你看到，每一行都有每个盒子的交替颜色的球 – 意思blue for box1为blue for box1 ， red for box2 orange for box3 red for box2 orange for box3 。 我不能在每一排都有相同颜色的球。 所以这种组合是不可能的，因为它有两个盒子的相同颜色的球。

 {box1=blue, box2=blue, box3=orange} 

而且，在第二行中，我不会使用第一行中用于该盒子的那些球。

输出组合是在传递的输入上生成的，如（点A）所示 。

现在，让我们说（POINT B）作为box3没有任何球的输入，我将返回另一个映射，如下所示，它将是List<Map> –

 [{box1=blue, box2=red}, {box1=red, box2=orange}, {box1=orange, box2=blue}] 

在上面的输出中，您可以看到没有box3因为没有输入，但每行中的box1和box2具有交替的球颜色。

现在，让我们说（POINT C）作为一个输入，其中box2只有两种颜色的球，我将返回另一个映射，如下所示，它将是List<Map> –

 [{box1=blue, box2=red, box3=orange}, {box1=red, box3=blue}, {box1=orange, box2=blue, box3=red}] 

在上面的输出中，你可以看到第二行没有box2因为box2只有球的red和blue ，为了使组合正确，box2在第一行和第三行只是为了维持每一行的规则有交替颜色的球。

现在我无法理解我将如何编写这样的方法，它可以返回我在传递此问题的输入上的映射基础？

注意：-

这里的盒子现在总是三个，但是球可以如输入中所示的那样变化

任何建议都会对此有很大帮助。 谢谢。

更新： –

我的基本问题是给出了如上所示的球和盒的输入 – 如何返回映射，使得在每一行中，盒子使用交替/不同颜色的球，并且他们需要确保在前一行中，那些球的颜色没有被同一个盒子使用。

对于（POINT C）作为输入，其中box2只有两种颜色的球，我想返回如下所示的映射，它也是List<Map> –

 [{box1=blue, box2=red, box3=orange}, {box1=red, box3=blue}, {box1=orange, box2=blue, box3=red}] 

• 在第一行中， box1 has blue ， box2 has red ， box3 has orange ，有交替颜色的球。
• 在第二行， box1 has red为什么？ bcoz blue已经在box1的第一行中使用，box3在第二行中没有box2 。
• 同样对于第三行也是如此。

我之前遇到的解决方案，但是假设每个盒子中的球数总是相同的 –

 public List<Map> createMappings(List boxes, List balls) { List<Map> result = new ArrayList<Map>(); for(int i = 0; i < balls.size(); i++) { Map row = new HashMap(); for(int j = 0; j < boxes.size(); j++) { String box = boxes.get(j); int ballIndex = (j + i) % balls.size(); String ball = balls.get(ballIndex); row.put(box, ball); } result.add(row); } return result; } 

如果我们可以修改它以开始接受我作为Map的输入并在球的数量可以不同时处理用例，那么对我来说它将变得非常容易

UPDATE

如果我正在尝试下面的输入组合，那么我输出为空，这是错误的。

 List balls1 = Arrays.asList(); List balls2 = Arrays.asList(); List balls3 = Arrays.asList("red", "blue"); Map<String, List> maps = new LinkedHashMap<String, List>(); maps.put("box3", balls3); maps.put("box2", balls2); maps.put("box1", balls1); List<Map> mappings = generateMappings(maps); // below mappings is coming as empty somehow which is wrong System.out.println(mappings); 

但对于上述输入，输出应如下所示 –

 [{box3=red}, {box3=blue}] 

而且，它也不适用于以下输入 –

 List balls1 = Arrays.asList("red", "blue", "orange"); List balls2 = Arrays.asList("red", "blue", "orange"); List balls3 = Arrays.asList("red", "blue", "orange", "purple", "pink"); 

使用上面的输入组合，我可以在其他行中看到相同的颜色球，对于违反第三规则的一些盒子。

更新： –

我的规则是 –

• 在每一行中，方框应具有交替的球颜色。 如果你看到上面的每一行，每一行都有交替颜色的球 – 意思blue for box1为blue for box1 ， red for box2 orange for box3 red for box2 ，第一行为orange for box3 red for box2 orange for box3 。
• 其次，我不能在每一行中使用相同颜色的球。 因此，下面的组合是不可能的，因为它具有相同颜色的球，用于一行中的两个盒子。 {box1=blue, box2=blue, box3=orange}
• 第三，在下一行中，我不会将这些球用于先前行中使用过的盒子。 因此第二行不能为box1设置blue ，因为它已经在第一行中被box1 。

最终守则： –

最后的代码应该是这样的 –

 public static List<Map> create(Map<String, List> input) { List<Map> output = new ArrayList<Map>(); // find all boxes List boxes = new ArrayList(input.keySet()); // find all colors Set distinctColors = new LinkedHashSet(); for (List e : input.values()) { for (String color : e) { if (!distinctColors.contains(color)) { distinctColors.add(color); } } } List colors = new ArrayList(distinctColors); Set generationHistory = new LinkedHashSet(); int colorIndex = 0; for(int i = 0; i < colors.size(); i++) { Map row = new LinkedHashMap(); output.add(row); colorIndex = i; for(int j = 0; j = boxes.size()) { boxIndex = 0; } String box = boxes.get(boxIndex); List boxColors = input.get(box); if(colorIndex >= colors.size()) { colorIndex = 0; } String color = colors.get(colorIndex++); // a combination is generated only if the actual // colors does exist in the actual box // and it has not already been generated i all previous rows if(boxColors.contains(color) && isNotYetGenerated(box, color, generationHistory)) { row.put(box, color); } } } return output; } private static boolean isNotYetGenerated(String box, String color, Set generationHistory) { String key = box + "=" + color; boolean notYetGenerated = !generationHistory.contains(key); if (notYetGenerated) { generationHistory.add(key); } return notYetGenerated; } 

Answer 1

基本上你必须将所有盒子与所有可能的颜色组合在一起。 在每个新行中，一个框获得分配给它在上一行中的下一个颜色。 如果你编写所有可能的盒子/颜色组合并写下所有索引，它会变得更清晰。 PointA是一个很好的例子：

用于输入

 {box1=[blue, red, orange]} {box2=[blue, red, orange]} {box3=[blue, red, orange]} 

以上输入的所有组合都是（使用boxIndex，colorIndex在前面）：

 0,0 {box1=blue} 0,1 {box1=red} 0,2 {box1=orange} 1,0 {box2=blue} 1,1 {box2=red} 1,2 {box2=orange} 2,0 {box3=blue} 2,1 {box3=red} 2,2 {box3=orange} 

您正在寻找以下输出：

 {box1=blue, box2=red, box3=orange} {box1=red, box2=orange, box3=blue} {box1=orange, box2=blue, box3=red} 

因此，您正在寻找的指数如下：

 row1 0,0 1,1 2,2 row2 0,1 1,2 2,0 row3 0,2 1,0 2,1 

现在，当你知道你在寻找什么时，写一些循环就变得容易了（ 免责声明：据我正确理解你的问题/未完全测试!!! ）：

 public List> create(Map> input) { List> output = new ArrayList<>(); // find all boxes List boxes = new ArrayList<>(input.keySet()); // find all colors Set distinctColors = new LinkedHashSet<>(); for(List e : input.values()) { for(String color : e) { if(! distinctColors.contains(color)) { distinctColors.add(color); } } } List colors = new ArrayList(distinctColors); int colorIndex = 0; for(int i = 0; i < boxes.size(); i++) { Map row = new LinkedHashMap<>(); output.add(row); colorIndex = i; for(int j = 0; j < colors.size(); j++) { int boxIndex = j; if(boxIndex >= boxes.size()) { boxIndex = 0; } String box = boxes.get(boxIndex); List boxColors = input.get(box); if(colorIndex >= colors.size()) { colorIndex = 0; } String color = colors.get(colorIndex++); // a combination is generated only if the actual // colors does exist in the actual box if(boxColors.contains(color)) { row.put(box, color); } } } return output; } 

以下是使用您提供的一些输入的一些测试：

点A

 @Test public void createFromPointA() { // {box1=[blue, red, orange]} // {box2=[blue, red, orange]} // {box3=[blue, red, orange]} // [{box1=blue, box2=red, box3=orange}, // {box1=red, box2=orange, box3=blue}, // {box1=orange, box2=blue, box3=red}] // 0,0 {box1=blue} // 0,1 {box1=red} // 0,2 {box1=orange} // 1,0 {box2=blue} // 1,1 {box2=red} // 1,2 {box2=orange} // 2,0 {box3=blue} // 2,1 {box3=red} // 2,2 {box3=orange} // 0,0 1,1 2,2 // 0,1 1,2 2,0 // 0,2 1,0 2,1 Map> input = new LinkedHashMap<>(); input.put("box1", Arrays.asList("blue", "red", "orange")); input.put("box2", Arrays.asList("blue", "red", "orange")); input.put("box3", Arrays.asList("blue", "red", "orange")); List> output = create(input); for(Map e : output) { System.out.println(e); } } 

PointB

 @Test public void createFromPointB() { // {box1=[blue, red, orange]} // {box2=[blue, red, orange]} // {box3=[]} // [{box1=blue, box2=red}, // {box1=red, box2=orange}, // {box1=orange, box2=blue}] // 0,0 {box1=blue} // 0,1 {box1=red} // 0,2 {box1=orange} // 1,0 {box2=blue} // 1,1 {box2=red} // 1,2 {box2=orange} // 2,x {box3=blue} // 2,x {box3=red} // 2,X {box3=orange} // 0,0 1,1 2,x // 0,1 1,1 2,x // 0,2 1,0 2,x Map> input = new LinkedHashMap<>(); input.put("box1", Arrays.asList("blue", "red", "orange")); input.put("box2", Arrays.asList("blue", "red", "orange")); input.put("box3", Collections.emptyList()); List> output = create(input); for(Map e : output) { System.out.println(e); } } 

PointC

 @Test public void createFromPointC() { // {box1=[blue, red, orange]} // {box2=[blue, red]} // {box3=[blue, red, orange]} // [{box1=blue, box2=red, box3=orange}, // {box1=red, box3=blue}, // {box1=orange, box2=blue, box3=red}] // 0,0 {box1=blue} // 0,1 {box1=red} // 0,2 {box1=orange} // 1,0 {box2=blue} // 1,1 {box2=red} // 1,x {box2=orange} // 2,0 {box3=blue} // 2,1 {box3=red} // 2,2 {box3=orange} // 0,0 1,1 2,2 // 0,1 1,x 2,0 // 0,2 1,0 2,1 Map> input = new LinkedHashMap<>(); input.put("box1", Arrays.asList("blue", "red", "orange")); input.put("box2", Arrays.asList("blue", "red")); input.put("box3", Arrays.asList("blue", "red", "orange")); List> output = create(input); for(Map e : output) { System.out.println(e); } } 

OUTPUTA

 {box1=blue, box2=red, box3=orange} {box1=red, box2=orange, box3=blue} {box1=orange, box2=blue, box3=red} 

OUTPUTB

 {box1=blue, box2=red} {box1=red, box2=orange} {box1=orange, box2=blue} 

OutputC

 {box1=blue, box2=red, box3=orange} {box1=red, box3=blue} {box1=orange, box2=blue, box3=red} 

希望这有助于或至少为您提供一些寻找解决方案的提示。

编辑

您可以替换外部for循环

 for(int i = 0; i < boxes.size(); i++) { 

同

 for(int i = 0; i < colors.size(); i++) { 

这样，生成的方向是在颜色数量不是方框的颜色之后。 如果这对其他组合没有帮助，那么您可能需要在向行添加组合之前添加检查：

 if(boxColors.contains(color) && notYetGenerated()) { row.put(box, color); } 

编辑2

以下是isNotYetGenerated的示例实现

 private boolean isNotYetGenerated(String box, String color, Set generationHistory) { String key = box + "=" + color; boolean notYetGenerated = ! generationHistory.contains(key); if(notYetGenerated) { generationHistory.add(key); } return notYetGenerated; } 

在create方法中创建set并将其传递给该方法。

  Set generationHistory = new LinkedHashSet<>(); int colorIndex = 0; int index = boxes.size() > colors.size() ? boxes.size() : colors.size(); for(int i = 0; i < index; i++) { Map row = new LinkedHashMap<>(); output.add(row); colorIndex = i; for(int j = 0; j < index; j++) { int boxIndex = j; if(boxIndex >= boxes.size()) { boxIndex = 0; } String box = boxes.get(boxIndex); List boxColors = input.get(box); if(colorIndex >= colors.size()) { colorIndex = 0; } String color = colors.get(colorIndex++); // a combination is generated only if the actual // colors does exist in the actual box // and it has not already been generated i all previous rows if(boxColors.contains(color) && isNotYetGenerated(box, color, generationHistory)) { row.put(box, color); } } } 

测试PonitF

 @Test public void createFromPointF() { // {box1=red, box2=blue, box3=orange} // {box1=blue, box2=orange, box3=purple} // {box1=red, box3=pink} // {box3=red, box1=orange} // {box3=blue} // 0,0 {box1=red} // 0,1 {box1=blue} // 0,2 {box1=orange} // 0,x {box1=purple} // 0,x {box1=pink} // // 1,0 {box2=red} // 1,1 {box2=blue} // 1,2 {box2=orange} // 1,x {box2=purple} // 1,x {box2=pink} // // 2,0 {box3=red} // 2,1 {box3=blue} // 2,2 {box3=orange} // 2,3 {box3=purple} // 2,4 {box3=pink} // 0,0 1,1 2,2 // 0,1 1,2 2,3 // 0,x 1,x 2,0 // 0,x 1,0 2,1 Map> input = new LinkedHashMap<>(); input.put("box1", Arrays.asList("red", "blue", "orange")); input.put("box2", Arrays.asList("red", "blue", "orange")); input.put("box3", Arrays.asList("red", "blue", "orange", "purple", "pink")); List> output = create(input); Assert.assertEquals( "{box1=red, box2=blue, box3=orange}\r\n" + "{box1=blue, box2=orange, box3=purple}\r\n" + "{box1=orange, box3=pink}\r\n" + "{box3=red}\r\n" + "{box2=red, box3=blue}\r\n", toString(output)); } private String toString(List> output) { StringWriter sw = new StringWriter(); for(Map e : output) { sw.write(e.toString()); sw.write("\r\n"); } return sw.toString(); } 

OuputF

 {box1=red, box2=blue, box3=orange} {box1=blue, box2=orange, box3=purple} {box1=orange, box3=pink} {box3=red} {box2=red, box3=blue} 

Answer 2

您可能会考虑以下策略（代码未提供，因为这是“家庭作业”）：

1. 创建一个有颜色的Ball类
2. 创建一个Box类，该类具有球数的count方法和addBall方法
3. 在Box中创建一个“选择”方法，你给出一个球arrays，它会将球从hte框中拉出来，该球与球arrays输入上的任何颜色都不匹配或为null。

通过创建列（具有框中最大球数的大小）开始处理您的输出，然后对于第1行从第1行中拉出一个没有球颜色的球从第2行拉出第2行拉出来自方框2的球，在列中没有颜色）…

Answer 3

如果我正确理解了这个问题，你可以做的是以下内容：

1. 按照它们在其中的球数（从最小到最大的盒子的升序）对盒子进行排序。
2. 虽然还有颜色
3. 循环排序的列表框
4. 在每次迭代中从框中选择一种颜色（如果还有一个），在当前迭代（while循环）中尚未选取颜色

希望这可以帮助。 没有密码，不得不睡觉。

编辑：这是伪代码：

 arranged_colors = [] // empty list, this is you desired output sort_the_boxes(boxes) // ascending, by the number of colors in it while( there_are_more_colors_left() ) { // a method that is easy to implement current_list = [] // empty list for( box in boxes ) { for( color in box ) { if( not color in current_list ) { current_list.add(color) box.remove(color) break } } } aranged_colors.add(current_colors) }