如何获得2D数组可能的组合 [英] How to get 2D array possible combinations
问题描述
我有以下2D数组：
String [M] []
String [ 0]
1，2，3
字符串[1]
A，B
。
。
。
String [M-1]
！
所有可能的组合应存储在结果数组中
String []组合。例如：
组合[0] == {1A ....！）
组合[ 1] == {2A ....！）
组合[2] == {3A ....！）
组合[3] == {1B ... 。！）
请注意，数组的长度可变。输出String中元素的顺序无关紧要。我也不在乎是否有重复。
如果数组长度相同，嵌套循环就可以了，但它们不是，我真的不喜欢我不知道如何处理这个问题。
你可以通过使用数组一次一个地迭代这些组合记录每个内部数组的大小，以及一个计数器数组，用于跟踪每个内部数组中使用的成员。类似这样的方法：
/ **
*生成一个List< String>其中包含
*的每个组合，它是通过从
*中提供的二维String数组中的每个内部String数组中获取一个String。
* @param twoDimStringArray一个二维String数组，其中包含
*可变长度的String数组。
* @return一个List，其中包含每个String，可以通过从指定的二维
*数组中的每个String数组中获取
*一个String来形成。
* /
public static List< String> combination（String [] [] twoDimStringArray）{
//跟踪每个内部String数组的大小
int sizeArray [] = new int [twoDimStringArray.length];
//跟踪每个内部String数组的索引，将使用
//来进行下一个组合
int counterArray [] = new int [twoDimStringArray.length ]。
//发现每个内部数组的大小并填充sizeArray。
//还使用
//内部String数组大小计算可能的组合总数。
int totalCombinationCount = 1;
for（int i = 0; i< twoDimStringArray.length; ++ i）{
sizeArray [i] = twoDimStringArray [i] .length;
totalCombinationCount * = twoDimStringArray [i] .length;
}
//将组合存储在String对象列表中
List< String> combinationList = new ArrayList< String>（totalCombinationCount）;
StringBuilder sb; //串联效率高于串联
for（int countdown = totalCombinationCount; countdown> 0; --countdown）{
//运行内部数组，从中获取成员index
//由counterArray为每个内部数组指定，并构建
//组合字符串。
sb = new StringBuilder（）;
for（int i = 0; i< twoDimStringArray.length; ++ i）{
sb.append（twoDimStringArray [i] [counterArray [i]]）;
}
combinationList.add（sb.toString（））; //添加新组合到列表
//现在我们需要递增counterArray，以便在此循环的下一次迭代中获取下一个
//组合。
for（int incIndex = twoDimStringArray.length - 1; incIndex> = 0; --incIndex）{
if（counterArray [incIndex] + 1< sizeArray [incIndex]）{
++ counterArray [incIndex];
//更高有效性的索引都不需要增加
//，所以此时跳出此for循环。
休息;
}
//此位置的索引处于其最大值，因此为零
//并继续此循环以增加索引，这比
//更重要这个。
counterArray [incIndex] = 0;
}
}
返回combinationList;
}
方法如何运作
如果你想象计数器数组就像一个数字时钟读数那么第一个字符串组合看到计数器数组全为零，所以第一个字符串是由每个内部数组的零元素（第一个成员）产生的。 / p>
为了获得下一个组合，计数器数组加1。因此，最不重要的反指数增加1。如果这导致其值变得等于它表示的内部数组的长度，那么索引被归零，并且下一个更重要的索引会增加。一个单独的大小数组存储每个内部数组的长度，以便计数器数组循环知道索引何时达到其最大值。
例如，如果size数组是：
[3] [3] [2] [1]
且计数器数组位于：
[0] [2] [1] [0]
然后增量将变得最不重要（最右边） ）index等于1，这是它的最大值。因此，索引变为零，下一个更重要的索引（右起第二个）增加到2.但这也是该索引的最大值，因此它变为零，我们移动到下一个更重要的索引。这会增加到3，这是它的最大值，因此它变为零，我们移动到最重要（最左边）的索引。它增加到1，小于其最大值，因此递增的计数器数组变为：
[1] [0] [ 0] [0]
这意味着下一个字符串组合是通过获取第一个成员的第二个成员内部数组，以及接下来的三个内部数组的第一个成员。
直接警告和注释
我写的现在大约四十分钟，这是早上的一半，这意味着即使它似乎完全符合要求，但很可能存在可以优化的错误或代码。因此，如果性能至关重要，请务必对其进行彻底的单元测试。
请注意，它返回的是List而不是String数组，因为我认为Java Collections远远优于它在大多数情况下使用数组。此外，如果您需要一个没有重复项的结果集，您只需将列表更改为一个Set，它将自动删除重复项并为您留下一个唯一的设置。
如果你真的需要将结果作为一个String数组，不要忘记你可以使用 List< String> .toArray（String []）方法简单地将返回的List转换为你需要什么。
I have the following 2D array:
String[M][]
String[0]
"1","2","3"
String[1]
"A", "B"
.
.
.
String[M-1]
"!"
All the possible combinations should be in store in a resulting array
String[] combinations. So for example:
combinations[0] == {"1A....!")
combinations[1] == {"2A....!")
combinations[2] == {"3A....!")
combinations[3] == {"1B....!")
Notice that that the arrays are of variable length. Order of the elements in the output String doesn't matter. I also don't care if there are duplicates.
If the arrays were the same length, nested loops would do the trick, but they are not, and I really don't know how to approach the problem.
You can iterate through the combinations one at a time like clockwork by using an array to record the size of each inner array, and a counter array which keeps track of which member to use from each inner array. Something like this method:
/**
* Produce a List<String> which contains every combination which can be
* made by taking one String from each inner String array within the
* provided two-dimensional String array.
* @param twoDimStringArray a two-dimensional String array which contains
* String arrays of variable length.
* @return a List which contains every String which can be formed by taking
* one String from each String array within the specified two-dimensional
* array.
*/
public static List<String> combinations(String[][] twoDimStringArray) {
// keep track of the size of each inner String array
int sizeArray[] = new int[twoDimStringArray.length];
// keep track of the index of each inner String array which will be used
// to make the next combination
int counterArray[] = new int[twoDimStringArray.length];
// Discover the size of each inner array and populate sizeArray.
// Also calculate the total number of combinations possible using the
// inner String array sizes.
int totalCombinationCount = 1;
for(int i = 0; i < twoDimStringArray.length; ++i) {
sizeArray[i] = twoDimStringArray[i].length;
totalCombinationCount *= twoDimStringArray[i].length;
}
// Store the combinations in a List of String objects
List<String> combinationList = new ArrayList<String>(totalCombinationCount);
StringBuilder sb; // more efficient than String for concatenation
for (int countdown = totalCombinationCount; countdown > 0; --countdown) {
// Run through the inner arrays, grabbing the member from the index
// specified by the counterArray for each inner array, and build a
// combination string.
sb = new StringBuilder();
for(int i = 0; i < twoDimStringArray.length; ++i) {
sb.append(twoDimStringArray[i][counterArray[i]]);
}
combinationList.add(sb.toString()); // add new combination to list
// Now we need to increment the counterArray so that the next
// combination is taken on the next iteration of this loop.
for(int incIndex = twoDimStringArray.length - 1; incIndex >= 0; --incIndex) {
if(counterArray[incIndex] + 1 < sizeArray[incIndex]) {
++counterArray[incIndex];
// None of the indices of higher significance need to be
// incremented, so jump out of this for loop at this point.
break;
}
// The index at this position is at its max value, so zero it
// and continue this loop to increment the index which is more
// significant than this one.
counterArray[incIndex] = 0;
}
}
return combinationList;
}
How the method works
If you imagine the counter array being like a digital clock reading then the first String combination sees the counter array at all zeroes, so that the first String is made by taken the zero element (first member) of each inner array.
To get the next combination the counter array is incremented by one. So the least-significant counter index is increased by one. If this causes its value to become equal to the length of the inner array it represents then the index is zeroed, and the next index of greater significance is increased. A separate size array stores the length of each inner array, so that the counter array loop knows when an index has reached its maximum.
For example, if the size array was:
[3][3][2][1]
and the counter array was at:
[0][2][1][0]
then the increment would make the least significant (right-most) index equal to 1, which is its maximum value. So that index gets zeroed and the next index of greater significance (the second-from-right) gets increased to 2. But that is also the maximum of that index, so it gets zeroed and we move to the next index of greater significance. That gets increased to three, which is its maximum value so it gets zeroed and we move to the most significant (left-most) index. That gets increased to 1, which is less than its maximum so the incremented counter array becomes:
[1][0][0][0]
Which means the next String combination is made by taking the second member of the first inner array, and the first member of the next three inner arrays.
Dire warnings and notes
I wrote this just now in about forty minutes, and it's half-one in the morning, which means that even though it seems to do exactly what is needed, there are very likely bugs or bits of code which could be optimised. So be sure to unit test it thoroughly if its performance is critical.
Note that it returns a List rather than a String array because I think that Java Collections are vastly preferable to using arrays in most cases. Also, if you need a result set with no duplicates, you can simply change the List to a Set which will automatically drop duplicates and leave you with a unique set.
If you really need the result as a String array, don't forget you can use the List<String>.toArray(String[]) method to simply convert the returned List to what you need.
这篇关于如何获得2D数组可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
