查找组合框给出n个用球的x个 [英] Find the combinations, given n number of box with x number of balls
问题描述
我工作的一个项目中，我有三个框（截至目前），每个盒子中都会有球的一些颜色
所以我将其存储在一个地图字符串和字符串列表，如下图所示。
地图＆LT;字符串列表与LT;字符串＆GT;＆GT; boxBallMap =新的LinkedHashMap＆LT;字符串列表与LT;字符串＆GT;＆GT;（）;
在上面的地图数据，可就是这样 -
{BOX1 = [蓝，红，橙]}
{BOX2 = [蓝色，红色]}
{BOX3 = [蓝，红，橙]}
球在拖曳所以可能的组合可以是 -
（点A） ::所有箱有球数相同 -
{BOX1 = [蓝，红，橙]}
{BOX2 = [蓝，红，橙]}
{BOX3 = [蓝，红，橙]}
要么
（B点） ::所有的箱子没有任何球。所以我们可以说BOX3没有任何球 -
{BOX1 = [蓝，红，橙]}
{BOX2 = [蓝，红，橙]}
{BOX3 = []}
要么
（C点） ::一些箱子有球的数量较少。所以我们可以说BOX2只有两个球 -
{BOX1 = [蓝，红，橙]}
{BOX2 = [蓝色，红色]}
{BOX3 = [蓝，红，橙]}
要么
（点D） ::所有的箱子没有任何球。所以我们可以说BOX3和BOX2没有任何球 -
{BOX1 = [蓝，红，橙]}
{BOX2 = []}
{BOX3 = []}
ProblemStatement： -
以上投入基础上，我需要返回一个映射，这将是名单，其中，地图＆LT;字符串，字符串＆GT;＆GT; ，比方说，（POINT A），以下映射将返回为输出 -
[{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}，
{BOX1 =红色，BOX2 =橙，BOX3 =蓝}，
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}]
如果你在这里看到，每行有球的每个盒子的替代颜色 - 这意味着蓝色BOX1 ，红色BOX2 ，橙色BOX3 。我不能让球，每一行中的相同的颜色。所以这种组合不可能，因为它有滚珠的两个盒子相同的颜色。
{BOX1 =蓝色，BOX2 =蓝色，BOX3 =橙}
而且，在第二行中，我将不使用已为该框第一行中被使用的那些球。
输出组合如何产生的基础上，输入被传递，如图中的（点A）
现在，让我们说对于（B点）作为输入，其中 BOX3 没有任何的球，我会回来的另一如下面的映射，这将是名单，其中，地图＆LT;字符串，字符串＆GT;＆GT; 以及 -
[{BOX1 =蓝色，BOX2 =红}，
{BOX1 =红色，BOX2 =橙}，
{BOX1 =橙，BOX2 =蓝}]
在上面的输出，你可以看到有没有 BOX3 ，因为没有输入，但BOX1和BOX2每一行中有球的替代颜色。
现在，让我们说对于（C点）作为输入，其中 BOX2 只有两个颜色的球，我会回来的另一如下面的映射，这将是名单，其中，地图＆LT;字符串，字符串＆GT;＆GT; 以及 -
[{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}，
{BOX1 =红色，BOX3 =蓝}，
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}]
在上面的输出，你可以在第二排看有没有 BOX2 为 BOX2 只有球并且使组合正当红和蓝色的颜色，BOX2是在第一行和第三行只是为了维持规则每一行都会有球的替代颜色。
现在我不能够理解我怎么会写这样它可以在输入我传递了这个问题回到了我的映射基础的方法？
注： -
下面框将永远是三为，但现在球可以有所不同，在输入上面显示
任何建议将是这个伟大的帮助。谢谢你。
更新： -
我的基本问题是给定的球框的输入如上所示 - 我将如何回报，使得每行中，框使用备用/不同颜色的球的映射，他们需要确保，在previous行，球的那些颜色未被使用由相同的框
对于（C点）作为输入，其中 BOX2 只有两个颜色的球，我想回映射，如下图所示这将是名单，其中，地图＆LT;字符串，字符串＆GT;＆GT; 以及 -
[{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}，
{BOX1 =红色，BOX3 =蓝}，
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}]
- 在这里，在第一行，
BOX1有蓝色，BOX2已经红，BOX3有橙色有球的替代颜色。 - 在第二行中，
BOX1有红为什么？ bcoz蓝色已使用的第一个行中BOX1和BOX3有蓝色的，没有BOX2在第二排。 - 同样，对于第三排为好。
解决方案，我前面，但这个假设的球始终是在每个盒子一样的 -
公开名单＆LT;地图＆LT;字符串，字符串＆GT;＆GT; createMappings（名单＆LT;字符串＆GT;框，列表＆LT;字符串＆GT;球）{
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;结果=新的ArrayList＆LT;地图＆LT;字符串，字符串＆GT;＆GT;（）;
的for（int i = 0; I＆LT; balls.size（）;我++）{
地图＆LT;字符串，字符串＆GT;行=新的HashMap＆LT;字符串，字符串＆GT;（）;
对于（INT J = 0; J＆LT; boxes.size（）; J ++）{
字符串框= boxes.get（J）;
INT ballIndex =（J + I）％balls.size（）;
串球= balls.get（ballIndex）;
row.put（盒，球）;
}
result.add（行）;
}
返回结果;
}
如果我们可以修改此开始接受我的输入作为一个地图和处理用例时，球的数量可以是不同的，那么这将成为pretty的容易的，我
更新
如果我想在下面的输入组合，然后我得到的输出为空，这是不对的。
名单，其中，字符串＆GT;球类等= Arrays.asList（）;
名单＆LT;字符串＆GT; balls2 = Arrays.asList（）;
名单＆LT;字符串＆GT; balls3 = Arrays.asList（红，蓝）;
地图＆LT;字符串列表与LT;字符串＆GT;＆GT;图=新的LinkedHashMap＆LT;字符串列表与LT;字符串＆GT;＆GT;（）;
maps.put（BOX3，balls3）;
maps.put（BOX2，balls2）;
maps.put（BOX1，球类等）;
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;映射= generateMappings（图）
//下面映射即将为空某种程度上这是错误的
的System.out.println（映射）;
但输出应该如下对于上述输入 -
[{BOX3 =红}，{BOX3 =蓝}]
而且，它不会为以下输入工作，以及 -
名单，其中，字符串＆GT;球类等= Arrays.asList（红，蓝，橙色）;
名单＆LT;字符串＆GT; balls2 = Arrays.asList（红，蓝，橙色）;
名单＆LT;字符串＆GT; balls3 = Arrays.asList（红，蓝，橙色，紫色，粉）;
通过上面的输入组合，我可以看到相同颜色的球在其他行的一些箱子违反第三条规则。
更新： -
我的规则 -
- 在每行，盒子应该有球的替代颜色。如果你在上面看到，每行有球的每个盒子的替代颜色 - 这意味着
蓝色BOX1，红色BOX2，橙在第一行BOX3。 - 其次，我不能让球，每一行中的相同的颜色。所以在下面的组合是不可能的，因为它有滚珠的两个盒子中一行相同的颜色。
{BOX1 =蓝色，BOX2 =蓝色，BOX3 =橙} - 第三，下一行中，我将不使用那些球对于已较早的行中被使用的框。因此，第二行不能有
蓝色为BOX1因为它已经在第一行被BOX1。
最后code： -
SO最后code应该是这样的 -
公共静态列表＆LT;地图＆LT;字符串，字符串＆GT;＆GT;创建（地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入）{
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=新的ArrayList＆LT;地图＆LT;字符串，字符串＆GT;＆GT;（）;
//找到所有盒
名单＆LT;字符串＆GT;盒=新的ArrayList＆LT;字符串＆GT;（input.keySet（））;
//找到所有的颜色
设置＆LT;字符串＆GT; distinctColors =新LinkedHashSet＆LT;字符串＆GT;（）;
对于（名单＆LT;字符串＆GT; E：input.values（））{
对（串色：E）{
如果（！distinctColors.contains（颜色））{
distinctColors.add（颜色）;
}
}
}
名单＆LT;字符串＆GT;颜色=新的ArrayList＆LT;字符串＆GT;（distinctColors）;
设置＆LT;字符串＆GT; generationHistory =新LinkedHashSet＆LT;字符串＆GT;（）;
INT colorIndex = 0;
的for（int i = 0; I＆LT; colors.size（）;我++）{
地图＆LT;字符串，字符串＆GT;行=新的LinkedHashMap＆LT;字符串，字符串＆GT;（）;
output.add（行）;
colorIndex =我;
对于（INT J = 0; J＆LT; colors.size（）; J ++）{
INT boxIndex = j的;
如果（boxIndex＆GT; = boxes.size（））{
boxIndex = 0;
}
字符串框= boxes.get（boxIndex）;
名单＆LT;字符串＆GT; boxColors = input.get（箱）;
如果（colorIndex＆GT; = colors.size（））{
colorIndex = 0;
}
串色= colors.get（colorIndex ++）;
//组合仅产生如果实际
//颜色确实存在实际盒
//它尚未产生我所有的previous行
如果（boxColors.contains（彩色）及和放大器; isNotYetGenerated（彩盒，彩，generationHistory））{
row.put（彩盒，彩）;
}
}
}
返回输出;
}
私有静态布尔isNotYetGenerated（字符串框中，串色，设置＆LT;字符串＆GT; generationHistory）{
字符串键=盒+=+颜色;
！布尔notYetGenerated = generationHistory.contains（密钥）;
如果（notYetGenerated）{
generationHistory.add（键）;
}
返回notYetGenerated;
}
基本上，你将拥有所有的箱子结合所有可能的颜色。在每一个新的行的盒获取分配给它有previous行中的下一个颜色。它，如果你写的所有可能的盒/颜色组合，并写所有的指数变得有点清晰。 PointA 是一个很好的例子：
有关输入
{BOX1 = [蓝，红，橙]}
{BOX2 = [蓝，红，橙]}
{BOX3 = [蓝，红，橙]}
所有组合上面的输入（有 boxIndex，colorIndex 在前面）：
0,0 {BOX1 =蓝}
0,1 {BOX1 =红}
0,2 {BOX1 =橙}
1,0 {BOX2 =蓝}
1,1 {BOX2 =红}
1,2 {BOX2 =橙}
2,0 {BOX3 =蓝}
2,1 {BOX3 =红}
2,2 {BOX3 =橙}
您正在寻找以下的输出：
{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}
{BOX1 =红色，BOX2 =橙，BOX3 =蓝}
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}
因此，你正在寻找的指标如下：
ROW1 0,0 1,1 2,2
ROW2 0,1 1,2 2,0
ROW3 0,2 1,0 2,1
现在，当你知道你在找什么，就很容易写一些环（免责声明：据我已经正确地理解你的问题/不完全测试！）：
公开名单＆LT;地图＆LT;字符串，字符串＆GT;＆GT;创建（地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入）{
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=新的ArrayList＆LT;＆GT;（）;
//找到所有盒
名单＆LT;字符串＆GT;盒=新的ArrayList＆LT;＆GT;（input.keySet（））;
//找到所有的颜色
设置＆LT;字符串＆GT; distinctColors =新LinkedHashSet＆LT;＆GT;（）;
对于（名单＆LT;字符串＆GT; E：input.values（））{
对（串色：E）{
如果（！distinctColors.contains（颜色））{
distinctColors.add（颜色）;
}
}
}
名单＆LT;字符串＆GT;颜色=新的ArrayList＆LT;字符串＆GT;（distinctColors）;
INT colorIndex = 0;
的for（int i = 0; I＆LT; boxes.size（）;我++）{
地图＆LT;字符串，字符串＆GT;行=新的LinkedHashMap＆LT;＆GT;（）;
output.add（行）;
colorIndex =我;
对于（INT J = 0; J＆LT; colors.size（）; J ++）{
INT boxIndex = j的;
如果（boxIndex＆GT; = boxes.size（））{
boxIndex = 0;
}
字符串框= boxes.get（boxIndex）;
名单＆LT;字符串＆GT; boxColors = input.get（箱）;
如果（colorIndex＆GT; = colors.size（））{
colorIndex = 0;
}
串色= colors.get（colorIndex ++）;
//组合仅产生如果实际
//颜色确实存在实际盒
如果（boxColors.contains（颜色））{
row.put（彩盒，彩）;
}
}
}
返回输出;
}
下面是使用一些你所提供的输入一些testings：
PointA
@Test
公共无效createFromPointA（）{
// {BOX1 = [蓝，红，橙]}
// {BOX2 = [蓝，红，橙]}
// {BOX3 = [蓝，红，橙]}
// [{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}，
// {BOX1 =红色，BOX2 =橙，BOX3 =蓝}，
// {BOX1 =橙，BOX2 =蓝色，BOX3 =红}]
// 0,0 {BOX1 =蓝}
// 0,1 {BOX1 =红}
// 0,2 {BOX1 =橙}
// 1,0 {BOX2 =蓝}
// 1,1 {BOX2 =红}
// 1,2 {BOX2 =橙}
// 2,0 {BOX3 =蓝}
// 2,1 {BOX3 =红}
// 2,2 {BOX3 =橙}
// 0,0 1,1 2,2
// 0,1 1,2 2,0
// 0,2 1,0 2,1
地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入=新的LinkedHashMap＆LT;＆GT;（）;
input.put（BOX1，Arrays.asList（蓝，红，橙色））;
input.put（BOX2，Arrays.asList（蓝，红，橙色））;
input.put（BOX3，Arrays.asList（蓝，红，橙色））;
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=创建（输入）;
对于（地图＆LT;字符串，字符串＆GT; E：输出）{
的System.out.println（E）;
}
}
PointB
@Test
公共无效createFromPointB（）{
// {BOX1 = [蓝，红，橙]}
// {BOX2 = [蓝，红，橙]}
// {BOX3 = []}
// [{BOX1 =蓝色，BOX2 =红}，
// {BOX1 =红色，BOX2 =橙}，
// {BOX1 =橙，BOX2 =蓝}]
// 0,0 {BOX1 =蓝}
// 0,1 {BOX1 =红}
// 0,2 {BOX1 =橙}
// 1,0 {BOX2 =蓝}
// 1,1 {BOX2 =红}
// 1,2 {BOX2 =橙}
// 2，X {BOX3 =蓝}
// 2，X {BOX3 =红}
// 2，X {BOX3 =橙}
// 0,0 1,1 2中，x
// 0,1 1,1 2中，x
// 0,2 1,0 2中，x
地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入=新的LinkedHashMap＆LT;＆GT;（）;
input.put（BOX1，Arrays.asList（蓝，红，橙色））;
input.put（BOX2，Arrays.asList（蓝，红，橙色））;
input.put（BOX3，集合＆LT;字符串＆GT;的emptyList（））;
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=创建（输入）;
对于（地图＆LT;字符串，字符串＆GT; E：输出）{
的System.out.println（E）;
}
}
PointC
@Test
公共无效createFromPointC（）{
// {BOX1 = [蓝，红，橙]}
// {BOX2 =蓝色，红色]}
// {BOX3 = [蓝，红，橙]}
// [{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}，
// {BOX1 =红色，BOX3 =蓝}，
// {BOX1 =橙，BOX2 =蓝色，BOX3 =红}]
// 0,0 {BOX1 =蓝}
// 0,1 {BOX1 =红}
// 0,2 {BOX1 =橙}
// 1,0 {BOX2 =蓝}
// 1,1 {BOX2 =红}
// 1，X {BOX2 =橙}
// 2,0 {BOX3 =蓝}
// 2,1 {BOX3 =红}
// 2,2 {BOX3 =橙}
// 0,0 1,1 2,2
// 0,1 1，X 2,0
// 0,2 1,0 2,1
地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入=新的LinkedHashMap＆LT;＆GT;（）;
input.put（BOX1，Arrays.asList（蓝，红，橙色））;
input.put（BOX2，Arrays.asList（蓝，红））;
input.put（BOX3，Arrays.asList（蓝，红，橙色））;
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=创建（输入）;
对于（地图＆LT;字符串，字符串＆GT; E：输出）{
的System.out.println（E）;
}
}
OUTPUTA
{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}
{BOX1 =红色，BOX2 =橙，BOX3 =蓝}
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}
OUTPUTB
{BOX1 =蓝色，BOX2 =红}
{BOX1 =红色，BOX2 =橙}
{BOX1 =橙，BOX2 =蓝}
OutputC
{BOX1 =蓝色，BOX2 =红色，BOX3 =橙}
{BOX1 =红色，BOX3 =蓝}
{BOX1 =橙，BOX2 =蓝色，BOX3 =红}
希望这有助于或至少给你找到一个解决方案，在你途中的一些线索。
修改
您可以取代外循环
的for（int i = 0; I＆LT; boxes.size（）;我++）{
与
的for（int i = 0; I＆LT; colors.size（）;我++）{
此方式的色数后的产生取向不是的箱子。如果这样做没有帮助其他的组合，那么你可能想增加一个组合，一个行之前增加一个检查：
如果（boxColors.contains（彩色）及和放大器; notYetGenerated（））{
row.put（彩盒，彩）;
}
编辑2
下面是 isNotYetGenerated
私人布尔isNotYetGenerated（字符串框中，串色，
设置＆LT;字符串＆GT; generationHistory）{
字符串键=盒+=+颜色;
布尔notYetGenerated =！ generationHistory.contains（键）;
如果（notYetGenerated）{
generationHistory.add（键）;
}
返回notYetGenerated;
}
创建集在创建的方法将它传递给该方法。
设置＆LT;字符串＆GT; generationHistory =新LinkedHashSet＆LT;＆GT;（）;
INT colorIndex = 0;
INT指数= boxes.size（）＆GT; colors.size（）？ boxes.size（）：colors.size（）;
的for（int i = 0; I＆LT;指数;我++）{
地图＆LT;字符串，字符串＆GT;行=新的LinkedHashMap＆LT;＆GT;（）;
output.add（行）;
colorIndex =我;
对于（INT J = 0; J＆LT;指数; J ++）{
INT boxIndex = j的;
如果（boxIndex＆GT; = boxes.size（））{
boxIndex = 0;
}
字符串框= boxes.get（boxIndex）;
名单＆LT;字符串＆GT; boxColors = input.get（箱）;
如果（colorIndex＆GT; = colors.size（））{
colorIndex = 0;
}
串色= colors.get（colorIndex ++）;
//组合仅产生如果实际
//颜色确实存在实际盒
//它尚未产生我所有的previous行
如果（boxColors.contains（彩色）及和放大器; isNotYetGenerated（彩盒，彩，generationHistory））{
row.put（彩盒，彩）;
}
}
}
测试PonitF
@Test
公共无效createFromPointF（）{
// {BOX1 =红色，BOX2 =蓝色，BOX3 =橙}
// {BOX1 =蓝色，BOX2 =橙，BOX3 =紫色}
// {BOX1 =红色，BOX3 =粉}
// {BOX3 =红色，BOX1 =橙}
// {BOX3 =蓝}
// 0,0 {BOX1 =红}
// 0,1 {BOX1 =蓝}
// 0,2 {BOX1 =橙}
// 0，X {BOX1 =紫色}
// 0，X {BOX1 =粉}
//
// 1,0 {BOX2 =红}
// 1,1 {BOX2 =蓝}
// 1,2 {BOX2 =橙}
// 1，X {BOX2 =紫色}
// 1，X {BOX2 =粉}
//
// 2,0 {BOX3 =红}
// 2,1 {BOX3 =蓝}
// 2,2 {BOX3 =橙}
// 2,3 {BOX3 =紫色}
// 2,4 {BOX3 =粉}
// 0,0 1,1 2,2
// 0,1 1,2 2,3
// 0，X 1，X 2,0
// 0，X 1,0 2,1
地图＆LT;字符串列表与LT;字符串＆GT;＆GT;输入=新的LinkedHashMap＆LT;＆GT;（）;
input.put（BOX1，Arrays.asList（红，蓝，橙色））;
input.put（BOX2，Arrays.asList（红，蓝，橙色））;
input.put（BOX3，Arrays.asList（红，蓝，橙色，紫色，粉））;
列表与LT;地图＆LT;字符串，字符串＆GT;＆GT;输出=创建（输入）;
Assert.assertEquals（
{BOX1 =红色，BOX2 =蓝色，BOX3 =橙} \ r \ N+
{BOX1 =蓝色，BOX2 =橙，BOX3 =紫色} \ r \ N+
{BOX1 =橙，BOX3 =粉} \ r \ N+
{BOX3 =红} \ r \ N+
{BOX2 =红色，BOX3 =蓝} \ r \ N的toString（输出））;
}
私人字符串的toString（名单＆LT;地图＆LT;字符串，字符串＆GT;＆GT;输出）{
StringWriter的SW =新的StringWriter（）;
对于（地图＆LT;字符串，字符串＆GT; E：输出）{
sw.write（e.toString（））;
sw.write（\ r \ N）;
}
返回sw.toString（）;
}
OuputF
{BOX1 =红色，BOX2 =蓝色，BOX3 =橙}
{BOX1 =蓝色，BOX2 =橙，BOX3 =紫色}
{BOX1 =橙，BOX3 =粉}
{BOX3 =红}
{BOX2 =红色，BOX3 =蓝}
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 orangewhich has alternate color of balls. - In second row,
box1 has redwhy? bcozbluewas already used in the first row for box1 and box3 has blue and nobox2in 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 box3in 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
blueforbox1as it was already used in first row bybox1.
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;
}
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}
这篇关于查找组合框给出n个用球的x个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
