寻找Java中的给定数组的所有可能的组合 [英] Finding all possible combinations of a given array in Java
本文介绍了寻找Java中的给定数组的所有可能的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我工作中的Java的一个问题，找到所有可能的组合给出的任意起始点阵列，由直到每个索引处达到值1在阵列中的每个项目的时间递减值中的一个。
我已经开始在下面的测试案例，但没有得到很远。
我想解决我的问题，请一些帮助。
进口org.junit.Assert;
进口org.junit.Test;公共类ComboTest
{
@测试
公共无效测试（）
{
INT [] [] =答案{
{4,3，2}，{3,3，2}，{2，3,2}，{1，3,2}，
{4,2，2}，{3,2，2}，{2，2,2}，{1，2，2}，
{4,1，2}，{3,1，2}，{2，1,2}，{1，1，2}， {4,3，1}，{3,3，1}，{2，3，1}，{1，3，1}，
{4,2，1}，{3,2，1}，{2,2，1}，{1，2，1}，
{4,1，1}，{3,1，1}，{2，1,1}，{1，1，1}，
};
INT []开始= {4,3，2}; INT昏暗= 1;
的for（int i = 0; I＆LT; start.length;我++）
{
*黯淡开始= [I]
} INT [] [] =连击新INT [暗淡] [start.length]; 的for（int i = 0; I＆LT;连击[0]。长度;我+ +）
{
连击[0] [i] =启动[I]
} 的for（int i = 1; I＆LT; combos.length;我++）
{
对于（INT J = 0; J＆LT;连击[I]。长度; J ++）
{
INT K =连击[我 - 1] [J] - 1; 如果（K＆。1）
{
K =启动[J]。
} 连击[I] [J] = K;
}
} 的for（int i = 0; I＆LT; combos.length;我++）
{
对于（INT J = 0; J＆LT;连击[I]。长度; J ++）
{
Assert.assertEquals（答案[I] [J]，组合技[I] [J]）;
}
}
}
}
解决方案
这是一个简单的状态搜索问题。你有一个起始状态，并且可以扩展它（创建其子）以下的一些标准。在你的情况下，由递减值之一，但不低于一定下限。
如果你不熟悉DFS或BFS，我建议您阅读这些。在此期间，这里的code（也许该解决方案是不是在你期望的格式，但你可以在它的工作：D）：
公共类ComboTest {
公共静态类组合{
私人整数[]值; 公共组合（整数[]值）{
this.values =值;
} @覆盖
公众诠释哈希code（）{
最终诠释黄金= 31;
INT结果= 1;
结果=黄金*结果+ Arrays.hash code（值）;
返回结果;
} @覆盖
公共布尔等于（obj对象）{
如果（这种== OBJ）{
返回true;
}
如果（OBJ == NULL）{
返回false;
}
如果（！（OBJ的instanceof组合））{
返回false;
}
组合其他=（组合）目标文件;
如果（！满足Arrays.equals（值，other.values））{
返回false;
}
返回true;
} @覆盖
公共字符串的toString（）{
返回Arrays.toString（值）;
} } 公共静态设置＆LT;＆二合一GT;组合（组合开始，诠释下界）{
SET＆LT;＆二合一GT;答案=新的HashSet＆LT;＆二合一GT;（）; 计算（启动，下界，答案）; 返回的答案;
} 私有静态无效计算（组合开始，诠释下界，集＆LT;＆二合一GT;答案）{
双端＆LT;＆二合一GT; dfsStack =新ArrayDeque＆LT;＆二合一GT;（）; dfsStack.push（启动）; 而（！dfsStack.isEmpty（））{
组合电流= dfsStack.pop（）;
answers.add（电流）; 对（组合下一个：扩大（目前，下界））{
如果（！answers.contains（下））{
dfsStack.push（下）;
}
}
}
} 私人静态列表＆LT;＆二合一GT;扩大（目前的组合，诠释下界）{
清单＆LT;＆二合一GT;的nextS =新的ArrayList＆LT;＆二合一GT;（）; 的for（int i = 0; I＆LT; current.values.length;我++）{
如果（current.values [Ⅰ]≥下界）{
整数[] = copyCurrent Arrays.copyOf（current.values，current.values.length）;
copyCurrent [Ⅰ] - ;
nexts.add（新组合（copyCurrent））;
}
} 返回的nextS;
} 公共静态无效的主要（字串[] args）{
组合开始=新的组合（新的整数[] {4，3，2}）;
SET＆LT;＆二合一GT;连击=连击（启动，1）; 对（组合组合：组合）{
的System.out.println（组合）;
} 的System.out.println（combos.size（））;
}}
输出：
[4，3,1]
[2，1，1]
并[3,2，1]
[1，1,2]
[2，2,2]
[3,3，2]
[4，3，2]
[4，2,1]
[3,1，1]
[2，1,2]
[3，2，2]
[4，1,1]
[4，2,2]
[3，1,2]
[4，1,2]
[1，3,1]
并[1,2，1]
并[2,3，1]
[1，3,2]
[1，1，1]
[2，2，1]
[3,3，1]
并[1,2，2]
[2，3，2]
24
I'm working on a problem in Java to find all possible combinations given an arbitrary starting array, by decrementing the values one at a time of each item in the array until the value 1 is reached at each index.
I've started on the below test case but haven't got very far. I would like some help in solving my problem please.
import org.junit.Assert;
import org.junit.Test;
public class ComboTest
{
@Test
public void test()
{
int[][] answers = {
{4, 3, 2}, {3, 3, 2}, {2, 3, 2}, {1, 3, 2},
{4, 2, 2}, {3, 2, 2}, {2, 2, 2}, {1, 2, 2},
{4, 1, 2}, {3, 1, 2}, {2, 1, 2}, {1, 1, 2},
{4, 3, 1}, {3, 3, 1}, {2, 3, 1}, {1, 3, 1},
{4, 2, 1}, {3, 2, 1}, {2, 2, 1}, {1, 2, 1},
{4, 1, 1}, {3, 1, 1}, {2, 1, 1}, {1, 1, 1},
};
int[] start = {4, 3, 2};
int dim = 1;
for (int i = 0; i < start.length; i++)
{
dim *= start[i];
}
int[][] combos = new int[dim][start.length];
for (int i = 0; i < combos[0].length; i++)
{
combos[0][i] = start[i];
}
for (int i = 1; i < combos.length; i++)
{
for (int j = 0; j < combos[i].length; j++)
{
int k = combos[i - 1][j] - 1;
if (k < 1)
{
k = start[j];
}
combos[i][j] = k;
}
}
for (int i = 0; i < combos.length; i++)
{
for (int j = 0; j < combos[i].length; j++)
{
Assert.assertEquals(answers[i][j], combos[i][j]);
}
}
}
}
解决方案
This is a simple state search problem. You have a starting state, and you can expand it (create its children) following some criteria. In your case, by decrementing one of the values, but not below some lower bound.
If you're not familiar with DFS or BFS, I suggest reading on those. In the meantime, here's the code (perhaps the solution is not in the format you're expecting, but you can work on it :D):
public class ComboTest {
public static class Combo {
private Integer[] values;
public Combo(Integer[] values) {
this.values = values;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode(values);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof Combo)) {
return false;
}
Combo other = (Combo) obj;
if (!Arrays.equals(values, other.values)) {
return false;
}
return true;
}
@Override
public String toString() {
return Arrays.toString(values);
}
}
public static Set<Combo> combos(Combo start, int lowerBound) {
Set<Combo> answers = new HashSet<Combo>();
compute(start, lowerBound, answers);
return answers;
}
private static void compute(Combo start, int lowerBound, Set<Combo> answers) {
Deque<Combo> dfsStack = new ArrayDeque<Combo>();
dfsStack.push(start);
while (!dfsStack.isEmpty()) {
Combo current = dfsStack.pop();
answers.add(current);
for (Combo next : expand(current, lowerBound)) {
if (!answers.contains(next)) {
dfsStack.push(next);
}
}
}
}
private static List<Combo> expand(Combo current, int lowerBound) {
List<Combo> nexts = new ArrayList<Combo>();
for (int i = 0; i < current.values.length; i++) {
if (current.values[i] > lowerBound) {
Integer[] copyCurrent = Arrays.copyOf(current.values, current.values.length);
copyCurrent[i]--;
nexts.add(new Combo(copyCurrent));
}
}
return nexts;
}
public static void main(String[] args) {
Combo start = new Combo(new Integer[] { 4, 3, 2 });
Set<Combo> combos = combos(start, 1);
for (Combo combo : combos) {
System.out.println(combo);
}
System.out.println(combos.size());
}
}
Output:
[4, 3, 1]
[2, 1, 1]
[3, 2, 1]
[1, 1, 2]
[2, 2, 2]
[3, 3, 2]
[4, 3, 2]
[4, 2, 1]
[3, 1, 1]
[2, 1, 2]
[3, 2, 2]
[4, 1, 1]
[4, 2, 2]
[3, 1, 2]
[4, 1, 2]
[1, 3, 1]
[1, 2, 1]
[2, 3, 1]
[1, 3, 2]
[1, 1, 1]
[2, 2, 1]
[3, 3, 1]
[1, 2, 2]
[2, 3, 2]
24
这篇关于寻找Java中的给定数组的所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
