Java，与数组的组合算法

Question

我正在尝试实现一种算法来计算数组的所有组合，其中一个字符被“*”替换，而不更改数组条目的顺序。

例如以下包含两个条目的数组:

{"A", "B"}

应该重现这个输出:

[A, B]
[*, B]
[A, *]
[*, *]

我当前的代码是:

public class TestCombination {

   public static void combinations(List<String[]> values, String[] attr, String all, int iteration) {
      String[] val = new String[attr.length];
      for (int i = 0; i < attr.length; i++) {
         val[i] = attr[i];
      }
      if (iteration < attr.length) {
         val[iteration] = all;
      }

      values.add(val);
      iteration = iteration + 1;

      if (Math.pow(attr.length, 2) != iteration) {
         combinations(values, attr, all, iteration);
      }
   }

   public static void main() {
      String[] values = new String[] {"A", "B"};
      List<String[]> resultValues = new ArrayList<String[]>();
      combinations(resultValues, values, "*", 0);

      for (String[] res : resultValues) {
         System.out.println(Arrays.deepToString(res));
      }
   }

}

我得到的输出是:

[*, B]
[A, *]
[A, B]
[A, B]

这尤其是因为这个不正确的代码:

if (iteration < attr.length) {
    val[iteration] = all;
}

我不知道如何计算下一个可能的索引以用“*”替换该索引处的数组值。

你能给我一些提示吗？

Answer 1

一种简单的方法是使用长度为n 的位掩码。迭代所有 n 位二进制数，然后对每个 n 位置执行以下操作:

• 如果位置i有一个，输出一个星号*
• 如果位置 i 为零，则输出原始值。

这将涵盖所有组合。

String[] a = new String[] {"A", "B", "C"};
for (int mask = 0 ; mask != 1<<a.length ; mask++) {
    for (int i = 0 ; i != a.length ; i++) {
        if ((mask & 1<<i) != 0) {
            System.out.print("* ");
        } else {
            System.out.print(a[i]+" ");
        }
    }
    System.out.println();
}

Demo.