给定n个盒子和x个球，找到组合

小编典典

给定n个盒子和x个球，找到组合

algorithm

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

所以我将它们存储在一个Map of String and List of String如下所示的文件中。

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

上图中的数据可以是这样的-

{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<String, String>>例如 （POINT A） ，下面的映射将作为输出返回-

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

在这里，如果你看，每行都有每一盒球的替代颜色-这意味着blue for box1，red for box2，orange for box3。我不能在每行中使用相同颜色的球。因此，这种组合是不可能的，因为它具有两个盒子的相同颜色的球。

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

而且，在第二行中，我将不使用该行第一行中使用的那些球。

输出组合是根据传递的输入生成的，如 （POINT A）所示 。

现在，假设 （POINT B） 作为输入，其中box3没有任何球，我将返回另一个映射，如下所示List<Map<String, String>>-

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

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

现在，假设 （POINT C） 作为输入，其中box2只有两种颜色的球，我将返回另一个映射，如下所示List<Map<String, String>>-

[{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<String, String>>也是：

[{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<String, String>> createMappings(List<String> boxes, List<String> balls) {
    List<Map<String, String>> result = new ArrayList<Map<String, String>>();
    for(int i = 0; i < balls.size(); i++) {
        Map<String, String> row = new HashMap<String,String>();
        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并处理球数可能不同的用例，那么对我来说这将变得非常容易

更新

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

List<String> balls1 = Arrays.asList();
List<String> balls2 = Arrays.asList();
List<String> balls3 = Arrays.asList("red", "blue");


Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
maps.put("box3", balls3);
maps.put("box2", balls2);
maps.put("box1", balls1);

List<Map<String, String>> mappings = generateMappings(maps);

// below mappings is coming as empty somehow which is wrong
System.out.println(mappings);

但是对于上面的输入，输出应该如下所示-

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

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

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

通过上面的输入组合，我可以在其他行中看到一些违反第三条规则的颜色球。

更新：-

我的规则是-

在每一行中，盒子应该有不同颜色的球。如果你看到这样，各行都有每一盒球的替代颜色-这意味着blue for box1，red for box2，orange for box3在第一行。
其次，我不能在每排中使用相同颜色的球。因此，下面的组合是不可能的，因为它在一行中的两个盒子中具有相同颜色的球。 {box1=blue, box2=blue, box3=orange}
第三，在下一行中，我将不使用在较早的行中使用的那些球作为盒子。因此第二行不能具有bluefor，box1因为它已经在第一行中使用过box1。

最终代码：-

所以最终代码应该像这样-

public static List<Map<String, String>> create(Map<String, List<String>> input) {
List<Map<String, String>> output = new ArrayList<Map<String, String>>();
// find all boxes
List<String> boxes = new ArrayList<String>(input.keySet());

// find all colors
Set<String> distinctColors = new LinkedHashSet<String>();
for (List<String> e : input.values()) {
    for (String color : e) {
    if (!distinctColors.contains(color)) {
        distinctColors.add(color);
    }
    }
}
List<String> colors = new ArrayList<String>(distinctColors);

Set<String> generationHistory = new LinkedHashSet<String>();
int colorIndex = 0;
for(int i = 0; i < colors.size(); i++) {
    Map<String, String> row = new LinkedHashMap<String, String>();
    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<String> 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<String> generationHistory) {
String key = box + "=" + color;
boolean notYetGenerated = !generationHistory.contains(key);
if (notYetGenerated) {
    generationHistory.add(key);
}
return notYetGenerated;
}

阅读 273

2020-07-28

共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<Map<String, String>> create(Map<String, List<String>> input) {
    List<Map<String, String>> output = new ArrayList<>();
    // find all boxes
    List<String> boxes = new ArrayList<>(input.keySet());

    // find all colors
    Set<String> distinctColors = new LinkedHashSet<>();
    for(List<String> e : input.values()) {
        for(String color : e) {
            if(! distinctColors.contains(color)) {
                distinctColors.add(color);  
            }
        }
    }
    List<String> colors = new ArrayList<String>(distinctColors);

    int colorIndex = 0;
    for(int i = 0; i < boxes.size(); i++) {
        Map<String, String> 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<String> 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<String, List<String>> 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<Map<String, String>> output = create(input);
    for(Map<String, String> e : output) {
        System.out.println(e);  
    }
}

点B

@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<String, List<String>> input = new LinkedHashMap<>();
    input.put("box1", Arrays.asList("blue", "red", "orange"));
    input.put("box2", Arrays.asList("blue", "red", "orange"));
    input.put("box3", Collections.<String>emptyList());

    List<Map<String, String>> output = create(input);
    for(Map<String, String> e : output) {
        System.out.println(e);  
    }
}

点C

@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<String, List<String>> 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<Map<String, String>> output = create(input);
    for(Map<String, String> e : output) {
        System.out.println(e);  
    }
}

输出A

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

输出B

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

输出C

{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<String> generationHistory) {
    String key = box + "=" + color;
    boolean notYetGenerated = ! generationHistory.contains(key);
    if(notYetGenerated) {
        generationHistory.add(key);
    }
    return notYetGenerated;
}

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

    Set<String> generationHistory = new LinkedHashSet<>();
    int colorIndex = 0;
    int index = boxes.size() > colors.size() ?  boxes.size() : colors.size();
    for(int i = 0; i < index; i++) {
        Map<String, String> 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<String> 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<String, List<String>> 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<Map<String, String>> 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<Map<String, String>> output) {
    StringWriter sw = new StringWriter();
    for(Map<String, String> 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}

2020-07-28