我有以下的二維數組：如何獲得二維數組可能的組合
String[M][]
String[0]
"1","2","3"
String[1]
"A", "B"
.
.
.
String[M-1]
"!"
所有可能的組合應在商店所得數組英寸例如：
combinations[0] == {"1A....!")
combinations[1] == {"2A....!")
combinations[2] == {"3A....!")
combinations[3] == {"1B....!")
請注意，數組的長度是可變的。輸出字符串中元素的順序無關緊要。我也不在乎是否有重複。
如果陣列是相同的長度，嵌套循環會做的伎倆，但他們都沒有了，我真的不知道該怎麼來解決這個問題。
你可以通過組合一個在像通過使用陣列來記錄每個內陣列的大小發條的時間，並且以跟蹤從每個陣列內使用的構件的計數器陣列迭代。這樣的方法的東西：
/**
* 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;
}
看到在全零的計數器陣列，使得第一串是通過取每個內部數組的零元素（第一個成員）。
要獲得下一個組合，計數器陣列會加1。所以最不重要的計數器指數增加1。如果這導致它的值等於它所表示的內部數組的長度，那麼索引被歸零，並且下一個更重要的索引被增加。一個單獨的大小數組存儲每個內部數組的長度，以便計數器數組循環知道索引何時達到其最大值。
例如，如果該尺寸數組是：
[3][3][2][1]
和計數器陣列是在：
[0][2][1][0]
然後增量將使至少顯著（最右側）指數等於1，這是它的最大值。因此，該指數被歸零，下一個更重要的指標（右起第二個）增加到2.但是這也是該指數的最大值，所以它被歸零，我們轉向下一個具有更大重要性的指標。這會增加到三，這是它的最大值，所以它被歸零，我們移動到最重要的（最左邊的）指數。這樣遞增的計數器陣列變成被增大到1，它是小於其最大：
[1][0][0][0]
這意味着下一個字符串組合是通過取第一內陣列的第二構件製成，並且所述第一構件接下來的三個內部陣列。
我剛纔在40分鐘左右寫到這，和它的半一個早上，這意味着，即使它似乎做的是需要什麼，有很可能的錯誤或可以被優化的代碼位。因此，如果其性能至關重要，請務必對其進行徹底的測試。
請注意，它返回一個List而不是一個String數組，因爲我認爲Java Collections在大多數情況下比使用數組更好。另外，如果你需要一個沒有重複的結果集，你可以簡單地將List更改爲一個Set，它會自動刪除重複項，併爲你留下一個唯一的集合。
如果您確實需要將結果作爲字符串數組，請不要忘記您可以使用List<String>.toArray(String[])方法將返回的List簡單地轉換爲您所需的。
這個問題有一個很好的遞歸結構（它也意味着它可能在內存中爆炸，正確的方式應該使用迭代器，如其他答案，但這個解決方案看起來更好，我們可以證明正確性感應，因爲的遞歸性質）。一個組合由第一個列表中的一個元素組成，該元素附加到由其餘（n-1）列表形成的所有可能組合中。遞歸工作在AllCombinationsHelper中完成，但您調用AllCombinations。注意測試空列表和更廣泛。
public static List<String> AllCombinations(List<List<Character>> aList) {
if(aList.size() == 0) { return new ArrayList<String>(); }
List<Character> myFirstSubList = aList.remove(0);
List<String> myStrings = new ArrayList<String>();
for(Character c : myFirstSubList) {
myStrings.add(c.toString());
}
return AllCombinationsHelper(aList, myStrings);
}
public static List<String> AllCombinationsHelper(List<List<Character>> aList,
List<String> aCollection) {
if(aList.size() == 0) { return aCollection; }
List<Character> myFirstList = aList.remove(0);
List<String> myReturnSet = new ArrayList<String>();
for(String s : aCollection) {
for(Character c : myFirstList) {
myReturnSet.add(c + s);
}
}
return AllCombinationsHelper(aList, myReturnSet);
}
應該直接做遞歸。
讓我重新修改一下，所以術語不那麼令人困惑。
我們將調用的String []作爲令牌名單，這是
現在你有令牌的目錄列表，你想從現有的每一記號表獲得一個令牌令牌的列表，並找出所有組合。
你需要做的是，給定TokenList
我只給一個僞代碼：
List<String> allCombinations(List<TokenList> listOfTokenList) {
if (length of strings == 1) {
return strings[0];
}
List<String> subListCombinations
= allCombination(listOfTokenList.subList(1)); // sublist from index 1 to the end
List<String> result;
for each (token in listOfTokenList[0]) {
for each (s in subListCombination) {
result.add(token + s);
}
}
return result;
}
我一直在這個問題一段時間掙扎。但我終於解決了它。我的主要障礙是我用於聲明每個變量的範圍。如果你沒有在正確的範圍內聲明你的變量，那麼這個變量將保留在前一次迭代中所做的更改。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class RecursiveAlgorithmTest {
private static int recursiveCallsCounter = 0;
public static ArrayList<ArrayList<String>> testCases = new ArrayList<ArrayList<String>>();
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
//set values for ArrayOfArrays
ArrayList<String> VariableA = new ArrayList<String>(Arrays.asList("red", "green"));
ArrayList<String> VariableB = new ArrayList<String>(Arrays.asList("A", "B", "C"));
ArrayList<String> VariableC = new ArrayList<String>(Arrays.asList("1", "2", "3", "4"));
ArrayList<ArrayList<String>> AofA = new ArrayList<ArrayList<String>>();
AofA.add(VariableA); AofA.add(VariableB); AofA.add(VariableC);
System.out.println("Array of Arrays: ToString(): " +AofA.toString());
ArrayList<String> optionsList = new ArrayList<String>();
//recursive call
recurse(optionsList, AofA, 0);
for (int i = 0 ; i < testCases.size() ; i++) {
System.out.println("Test Case " + (i+1) + ": " + testCases.get(i));
}
}//end main(String args[])
private static void recurse(ArrayList<String> newOptionsList,
ArrayList<ArrayList<String>> newAofA, int placeHolder){
recursiveCallsCounter++;
System.out.println("\n\tStart of Recursive Call: " + recursiveCallsCounter);
System.out.println("\tOptionsList: " + newOptionsList.toString());
System.out.println("\tAofA: " + newAofA.toString());
System.out.println("\tPlaceHolder: "+ placeHolder);
//check to see if we are at the end of all TestAspects
if(placeHolder < newAofA.size()){
//remove the first item in the ArrayOfArrays
ArrayList<String> currentAspectsOptions = newAofA.get(placeHolder);
//iterate through the popped off options
for (int i=0 ; i<currentAspectsOptions.size();i++){
ArrayList<String> newOptions = new ArrayList<String>();
//add all the passed in options to the new object to pass on
for (int j=0 ; j < newOptionsList.size();j++) {
newOptions.add(newOptionsList.get(j));
}
newOptions.add(currentAspectsOptions.get(i));
int newPlaceHolder = placeHolder + 1;
recurse(newOptions,newAofA, newPlaceHolder);
}
} else { // no more arrays to pop off
ArrayList<String> newTestCase = new ArrayList<String>();
for (int i=0; i < newOptionsList.size();i++){
newTestCase.add(newOptionsList.get(i));
}
System.out.println("\t### Adding: "+newTestCase.toString());
testCases.add(newTestCase);
}
}//end recursive helper
}// end of test class
老兄，你的代碼工作，非常感謝。但是我只是繼續看着它，不知道爲什麼，你能提供一些你使用的算法的一些解釋 - 基本步驟和關於每一步的一些細節，我只是沒有得到它背後的魔力。 – lekroif 2013-04-08 01:34:19
@lekroif從粗略的一瞥中，它看起來像計算你可以做的組合的總數，然後初始化一個計數器陣列，每個組合的數組一個 - 一端的計數器循環，每次它循環它遞增下一個，如果循環下一個遞增，依此類推。用杯子想一下公文包鎖。 – Patashu 2013-04-08 02:07:11
@lekroif我在代碼中添加了一個大塊，它貫穿了方法的工作方式。 Patashu是正確的：它就像一個數字刻度盤一樣，每次產生下一個組合的座標，直到它已經穿過每個可能的座標組合。我還修改了上面的代碼，以刪除我發佈的第一個版本中不必要的調零循環。 – Bobulous 2013-04-08 18:25:36