I am working on a project in which I have three box (as of now) and each box will have some color of balls

So I am storing them in a `Map of String and List of String` as shown below.

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

```

Data in the above map can be like this - 

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

```

So possible combination of balls in the boxes can be - 

**(POINT A)** :: All boxes having same number of balls -

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

or

```

**(POINT B)** :: Any of the boxes doesn't have any balls. So let's say box3 doesn't have any balls - 

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

or

```

**(POINT C)** :: Some boxes have less number of balls. So let's say box2 has only two balls - 

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

or

```

**(POINT D)** :: Any of the boxes doesn't have any balls. So let's say box3 and box2 doesn't have any balls -

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

```

**ProblemStatement:-**

Basis on the above input, I need to return a mapping which will be `List<Map<String, String>>`, let's say for **(POINT A)**, below mapping would be return as an output - 

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

```

Here if you see, each row has alternate color of balls for each box - meaning `blue for box1`, `red for box2`, `orange for box3`. I cannot have same color of balls in each row. So this combination is not possible as it has same color of balls for two boxes.

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

```

And also, in the second row, I won't use those balls which have been used in the first row for that box. 

The output combination is getting generated basis on the input being passed as shown in **(POINT A)**.

Now, let's say for **(POINT B)** as an input in which `box3` doesn't have any balls, I will be returning another mapping as shown below which will be `List<Map<String, String>>` as well - 

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

```

In the above output, you can see there is no `box3` as there was no input for it but box1 and box2 in each row has alternate colors of ball.

Now, let's say for **(POINT C)** as an input in which `box2` only has two color of balls, I will be returning another mapping as shown below which will be `List<Map<String, String>>` as well - 

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

```

In the above output, you can see in the second row there is no `box2` as `box2` only has `red` and `blue` color of balls and to make the combination right, box2 is in first row and third row just to maintain the rule that each row will have alternate colors of ball.

Now I am not able to understand how would I write such method which can return me the mappings basis on the input I am passing for this problem?

**NOTE:-**

Here boxes will always be three for now but balls can vary as shown above in the input

Any suggestions will be of great help on this. Thanks.

**UPDATE:-**

My basic problem is given a input of balls and boxes as shown above - How would I return the mapping such that, in each row, boxes are using alternate/different color of balls and they need to make sure that in the previous row, those color of balls has not been used by the same box.

For **(POINT C)** as an input in which `box2` only has two color of balls, I would like to return mapping as shown below which will be `List<Map<String, String>>` as well - 

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

```

* Here in first row, `box1 has blue`, `box2 has red`, `box3 has orange` which has alternate color of balls.
* In second row, `box1 has red` why? bcoz `blue` was already used in the first row for box1 and box3 has blue and no `box2` in second row.
* Similarly for third row as well.

Solution which I had earlier but this assume that number of balls is always same in each boxes - 

```
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;
}

```

If we can modify this to start accepting my input as a Map and handle the use case when number of balls can be different, then it will become pretty easy for me

**UPDATE**

if I am trying on the below input combination, then I am getting output as empty which is wrong.

```
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);

```

But the output should come as below for the above input - 

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

```

And also, it doesn't work for the below input as well - 

```
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");

```

With the above input combination, I can see same color balls in the other rows for some boxes which violates third rule..

**UPDATE:-**

My rules are-

* In each row, boxes should have alternate colors of ball. If you see above, each row has alternate color of balls for each box - meaning `blue for box1`, `red for box2`, `orange for box3` in first row.
* Secondly, I cannot have same color of balls in each row. So the below combination is not possible as it has same color of balls for two boxes in one row.
`{box1=blue, box2=blue, box3=orange}`
* Thirdly, in the next row, I won't use those balls for the box which have been used in the earlier rows. So second row cannot have `blue` for `box1` as it was already used in first row by `box1`.

**Final Code:-**

SO final code should be like this - 

```
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;
}

```