java - 复杂的 Java 排列生成问题

Question

我正在尝试找出最好的方法来为一个序列生成所有可能的排列，该序列是固定数量的数字并且每个数字都有不同的字母表。

我有许多整数数组，每个数组可以有不同的长度，在生成排列时，只有数组的值可以占据最终结果中的位置。

一个具体的例子是一个名为 conditions 的 int 数组，其中包含以下数据:

conditions1 = {1,2,3,4}
conditions2 = {1,2,3}
conditions3 = {1,2,3}
conditions4 = {1,2}
conditions5 = {1,2} 

我想创建一个包含所有可能排列的 5 列表 - 本例为 144 (4x3x3x2x2)。第1列只能使用conditions1的值，第2列只能使用conditions2的值，等等。

输出将是:

1,1,1,1,1
1,1,1,1,2
1,1,1,2,1
1,1,1,2,2
1,1,2,1,1
.
.
through to 
4,3,3,2,2

自从我完成任何这些工作以来已经太久了，我发现的大部分信息都与所有字段具有相同字母表的排列有关。我可以使用它，然后在删除所有具有无效值但听起来效率低下的列的排列后运行测试。

如果有任何帮助，我将不胜感激。

Z.

Answer 1

你看，不需要递归。

Iterator<int[]> permutations(final int[]... conditions) {
  int productLengths = 1;
  for (int[] arr : conditions) { productLengths *= arr.length; }
  final int nPermutations = productLengths;
  return new Iterator<int[]>() {
    int index = 0;
    public boolean hasNext() { return index < nPermutations; }
    public int[] next() {
      if (index == nPermutations) { throw new NoSuchElementException(); }
      int[] out = new int[conditions.length];
      for (int i = out.length, x = index; --i >= 0;) {
        int[] arr = conditions[i];
        out[i] = arr[x % arr.length];
        x /= arr.length;
      }
      ++index;
      return out;
    }
    public void remove() { throw new UnsupportedOperationException(); }
  };
}

将其包装在 Iterable<int[]> 中将使它更容易与 for (... : ...) 一起使用环形。您可以通过取消迭代器接口(interface)并仅将要填充的数组作为参数来摆脱数组分配。