7 java algorithm combinations list map
我正在开发一个项目,其中我有三个盒子(截至目前),每个盒子都有一些颜色的球
所以我将它们存储在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}
而且,在第二行中,我不会使用第一行中用于该盒子的那些球.
输出组合是在传递的输入上生成的,如(点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的输入并在球的数量可以不同时处理用例,那么对我来说它将变得非常容易
UPDATE
如果我尝试下面的输入组合,那么我输出为空,这是错误的.
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}blue,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();
}
输出F
{box1=red, box2=blue, box3=orange}
{box1=blue, box2=orange, box3=purple}
{box1=orange, box3=pink}
{box3=red}
{box2=red, box3=blue}