Find the combinations, given n number of box with

问题:

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

回答1:

Basically you will have to combine all boxes with all possible colors. In each new row a box gets the next color assigned to that it had in the previous row. It becomes a bit clearer if you write all the possible box/color combinations and write all the indices. PointA is a perfect example:

For the input

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

All combination for the above input are (with boxIndex , colorIndex in front):

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}

You are looking for the following output:

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

Thus the indices you are looking for are the following :

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

Now when you know what you are looking for, it becomes easy to write some loops (disclaimer: As far as I have correctly understood your question / Not fully tested!!!):

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

Here is some testings using some of the inputs you have provided:

PointA

@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);  
    }
}

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

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

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}

Hope this helps or at least give you some hints in your way finding a solution.

EDIT

You could replace the outer for loop

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

with

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

This way the generation is oriented after the number of colors not that of the boxes. If this doesn't help with other combinations then you might want to add a check before adding a combination to a row:

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

EDIT 2

Here is a sample implementation of 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 the set in the create method an pass it to that method.

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

Test for 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}

回答2:

You might consider the following strategy (code not presented because this is "homework"):

1. Create a Ball class that has color
2. Create a Box class that has a count method for the number of balls, and an addBall method
3. Create a "choose" method in Box that you give an Array of balls and it will pull a ball out of hte box that does NOT match any of the colors on the ball array input or null.

Start working on your output by creating columns (with a size of the max number of balls in a box), then for row 1 pull a ball from box 1 that does not have a ball color from previously pulled balls) for row 2 pull a ball from box 2 that does not have a color in the column) ...

回答3:

If I understand the question correctly, what you could do is the following:

1. sort the boxes by the number of balls they have in it (ascending, from the smallest to the largest box).
2. while there are colors left
3. loop over the sorted list of boxes
4. in each iteration pick a color from the box (if there is one left), that is not already picked in the current iteration (of the while loop)

Hope this helps. No code, have to sleep.

EDIT: here is the pseudocode:

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)
}