给定n个盒子和x个球，找到组合
问题内容：
我正在一个项目中，我有三个盒子（截至目前），每个盒子都会有一些颜色的球
所以我将它们存储在一个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为什么呢？bcozblue已在第一行中用于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;
}
问题答案：
基本上，您将必须将所有具有所有可能颜色的框组合在一起。在每个新行中，一个框将获取分配给上一行中的下一个颜色。如果您编写了所有可能的方框/颜色组合并编写了所有索引，它将变得更加清晰。
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}
