打印组合

Question

说我有一个字符串，看起来像数组：

{{"blue", "red"}, {"1", "2", 3"}, {"dog","cat", "fish", "bird"}} 

我想打印阵列的组合：

蓝1狗
蓝1猫
...
...
红3鸟

但是我想jagge d数组具有用户指定的行和列。我如何创建一个similar approach但以动态和迭代的方式？另外我正在处理数组而不是ArrayList，因为作为初学者，我想在学习ArrayList之前先看看我能用数组做什么。我的代码如下：

Scanner input = new Scanner(System.in); 
System.out.print("Enter number of arrays: "); 
int arrays = input.nextInt(); 
String [][] array = new String[arrays][]; 

for(int i = 0; i < x; i++){ 
    System.out.print("Enter number of elements for array: "); 
    int elements = input.nextInt(); 
    input.nextLine(); 
    arrays[i] = new String[elements]; 

    for(int j = 0; j < elements ; j++){ 
     System.out.print("Enter string: "); 
     String word = input.nextLine(); 
     arrays[i][j] = word; 
    } 
}  

Answer 1

这个答案将打印所有组合，不使用递归的，但如果组合的总数超过Long.MAX_VALUE将失败。由于打印许多行永远不会结束，这不是一个真正的问题。

要按顺序打印组合，请考虑一个递增数字，其中数字的每个数字都是相应子列表的索引。

实例（使用来自问题列表的列表）：

000: blue 1 dog 
001: blue 1 cat 
002: blue 1 fish 
003: blue 1 bird 
010: blue 2 dog 
... 
121: red 3 cat 
122: red 3 fish 
123: red 3 bird 

每个“数字”将翻转，当它到达相应的子列表，例如端最后一个子列表只有4个元素，所以数字从3翻到0.

注意：“数字”可以计数高于9.以十六进制表示这种情况。

现在，数字的数量也是动态的，即外部列表的大小。用简单的循环来做到这一点的一种方法是计算组合的总数（2 * 3 * 4 = 24），然后使用除法和余数来计算数字。

实施例：

Combination #10 (first combination is #0): 
    10 % 4     = 2 (last digit) 
    10/4 % 3  = 2 % 3 = 2 (middle digit) 
    10/4/3 % 2 = 0 % 2 = 0 (first digit) 
    Digits: 022 = blue 3 fish 

为了解决这个问题，我们首先建立除数，例如阵列div[] = { 12, 4, 1 }，并找到组合的总数（24）。

long[] div = new long[array.length]; 
long total = 1; 
for (int i = array.length - 1; i >= 0; i--) { 
    div[i] = total; 
    if ((total *= array[i].length) <= 0) 
     throw new IllegalStateException("Overflow or empty sublist"); 
} 

现在我们可以通过组合循环，并打印出结果：

for (long combo = 0; combo < total; combo++) { 
    for (int i = 0; i < array.length; i++) { 
     int digit = (int) (combo/div[i] % array[i].length); 
     if (i != 0) 
      System.out.print(' '); 
     System.out.print(array[i][digit]); 
    } 
    System.out.println(); 
} 

与问题输入：

String[][] array = {{"blue", "red"}, {"1", "2", "3"}, {"dog","cat", "fish", "bird"}}; 

我们得到以下的输出：

blue 1 dog 
blue 1 cat 
blue 1 fish 
blue 1 bird 
blue 2 dog 
blue 2 cat 
blue 2 fish 
blue 2 bird 
blue 3 dog 
blue 3 cat 
blue 3 fish 
blue 3 bird 
red 1 dog 
red 1 cat 
red 1 fish 
red 1 bird 
red 2 dog 
red 2 cat 
red 2 fish 
red 2 bird 
red 3 dog 
red 3 cat 
red 3 fish 
red 3 bird 

它可以处理e子阵列的任何组合，例如，与尺寸2，3，2 4子阵列，和2：

String[][] array = {{"small", "large"}, {"black", "tan", "silver"}, {"lazy", "happy"}, {"dog", "cat"}}; 

small black lazy dog 
small black lazy cat 
small black happy dog 
small black happy cat 
small tan lazy dog 
small tan lazy cat 
small tan happy dog 
small tan happy cat 
small silver lazy dog 
small silver lazy cat 
small silver happy dog 
small silver happy cat 
large black lazy dog 
large black lazy cat 
large black happy dog 
large black happy cat 
large tan lazy dog 
large tan lazy cat 
large tan happy dog 
large tan happy cat 
large silver lazy dog 
large silver lazy cat 
large silver happy dog 
large silver happy cat 

Answer 2

我的想法如下。假设我们有这个2-d array

String[][] strings = {{"blue", "red"}, 
         {"1", "2", "3"}, 
         {"dog", "cat", "bird", "fish"}}; 

我们可以生成一个阵列内，但有些条件包括置换。

所以首先我们在表格中找到最大线length。

int max = 0; 
for (int i = 0; i < strings.length; i++) { 
    if(max < strings[i].length) { 
     max = strings[i].length; 
    } 
} 

然后我们就产生了排列

int[] permutations = new int[strings.length]; 

void permute(int k) { 
    for(int i = 0; i < max; i++) { 
     permutations[k] = i; 
     if(valid(k)) { 
      if(k == strings.length - 1) { 
       printSolution(); 
      } else { 
       permute(k + 1); 
      } 
     } 
    } 
} 

valid功能检查i位置，这个数字是在我们的表ith线不是那么length不高。

boolean valid(int k) { 
    for(int i = 0; i < k; i++) { 
     if(permutations[i] >= strings[i].length) return false; 
    } 
    return true; 
} 

打印溶液的方法：

void printSolution() { 
    for(int i = 0; i < strings.length; i++) { 
     System.out.print(strings[i][permutations[i]] + " "); 
    } 
    System.out.println(); 
} 

和结果：

blue 1 dog 
blue 1 cat 
blue 1 bird 
blue 1 fish 
blue 2 dog 
blue 2 cat 
blue 2 bird 
blue 2 fish 
blue 3 dog 
blue 3 cat 
blue 3 bird 
blue 3 fish 
red 1 dog 
red 1 cat 
red 1 bird 
red 1 fish 
red 2 dog 
red 2 cat 
red 2 bird 
red 2 fish 
red 3 dog 
red 3 cat 
red 3 bird 
red 3 fish 

Answer 3

下面是一个使用整数索引的阵列，以模拟的可变数量的嵌套for循环的另一种方法：

Scanner input = new Scanner(System.in); 
    System.out.print("Enter number of arrays: "); 
    int arrays = input.nextInt(); 
    String[][] array = new String[arrays][]; 

    for (int i = 0; i < arrays; i++) { 
     System.out.print("Enter number of elements for array #" + i + ": "); 
     int elements = input.nextInt(); 
     input.nextLine(); 
     array[i] = new String[elements]; 

     for (int j = 0; j < elements; j++) { 
      System.out.print("Enter string: "); 
      String word = input.nextLine(); 
      array[i][j] = word; 
     } 
    } 

    int[] indices = new int[array.length]; 
    while (indices[0] < array[0].length) { 
     StringBuilder sb = new StringBuilder(); 
     for (int i = 0; i < indices.length; ++i) { 
      if (i > 0) { 
       sb.append(' '); 
      } 
      sb.append(array[i][indices[i]]); 
     } 
     System.out.println(sb.toString()); 
     for (int i = indices.length - 1; i >= 0; --i) { 
      if (++indices[i] < array[i].length) { 
       break; 
      } 
      if (i != 0) { 
       indices[i] = 0; 
      } 
     } 
    }