Java：寻找排列算法

Question

假设我有一个数组。

String[] arr = {"a", "b", "c"};

我需要获取所有可能的组合，例如：

a
a b
a c
a b c
a c b
b
b a
b c
b a c
b c a
c
c a
c b
c a b
c b a

我应该使用哪种快速算法来获取所有组合？

更新:

public static void permute(List<Integer> done, List<Integer> remaining {
    remaining.removeAll(Collections.<Integer>singletonList(null));
    done.removeAll(Collections.<Integer>singletonList(null));
    System.out.println(done);
    if (remaining.size() == 0) {
        return;
    }
    for (int i = 0; i < remaining.size(); i++) {
        Integer e = remaining.get(i);
        done.add(e);
        remaining.set(i, null);
        permute(done, remaining);
        remaining.add(e);
        done.set(i, null);
    }
}

输出

    []
    [1]
    [1, 2]
    [1, 2, 3]
    [1, 2, 3, 4]
    [2, 3, 4, 3]
    [2, 3, 4, 3, 4]
    [4, 3, 4, 3]
    [4, 3, 4, 3, 4]
    [4, 3, 4, 3, 4, 2]
    [3, 4, 3, 4, 2, 4]
    [3, 4, 3, 4, 2, 4, 2]
    [3, 4, 2, 4, 2, 3]
    [3, 4, 2, 4, 2, 3, 2]
    [3, 4, 2, 4, 2, 3, 2, 4]
    [4, 2, 4, 2, 3, 2, 4, 2]
    [4, 2, 4, 2, 3, 2, 4, 2, 4]
    [2, 3, 2, 4, 2, 4, 2]
    [2, 3, 2, 4, 2, 4, 2, 4]
    [2, 3, 2, 4, 2, 4, 2, 4, 3]
    [2, 3, 2, 4, 2, 4, 2, 4, 3, 1]
    [3, 2, 4, 2, 4, 2, 4, 3, 1, 3]
    [3, 2, 4, 2, 4, 2, 4, 3, 1, 3, 1]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3, 1]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4]
    [2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4, 1]
    [2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1]
    [4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4]
    [4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2]
    [1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4]
    [1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1]
    [4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2]
    [4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2]
    [3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1]
    [3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4]
    [1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1]
    [1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2]
    [4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4]
    [4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4]
    [2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4, 2]
    [2, 4

, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4, 2, 4]

更新3

我找到了一些代码并对其进行了重新设计。于是我得到了这个：

public class Permutations {

    public static void main(String[] args) {
        Set<String> combos = new Permutations().combos("1", "2", "3", "4", "5");
        for (String combo : combos) {
            for (char e : combo.toCharArray()){
                System.out.printf("[%s]", e);
            }
            System.out.println();
        }
    }

    public Set<String> combos(String... input) {
        Set<String> set = new TreeSet<>();
        combos(input, set, input.length, new StringBuffer());
        return set;
    }

    private void combos(String[] input, Set<String> set, int len, StringBuffer buf) {
        if (len == 0) {
            String elem = unique(buf.toString());
            set.add(elem);
        } else {
            for (String t : input) {
                buf.append(t);
                combos(input, set, len - 1, buf);
                buf.deleteCharAt(buf.length() - 1);
            }
        }
    }

    private String unique(String input) {
        StringBuilder unique = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            String si = input.substring(i, i + 1);
            if (unique.indexOf(si) == -1)
                unique.append(si);
        }
        return unique.toString();
    }

}

它能够正常工作。

- barbara

---

你目前有什么进展？ - ultranaut

@ultranaut 您是指实现吗？ - barbara

是的，你尝试过任何东西吗？如果尝试了，它不起作用吗？ - ultranaut

我的实现不起作用。 - barbara

看起来你需要的是所有有序子集，而不是排列。你应该使用递归算法。 - Nayuki

Answer 1

我最近编写了一个Java类，用于生成任何Comparable对象的排列组合。请查看我的github页面上的代码（此处），以及一些示例，以了解如何使用它。

以下是其中一个示例的复制/粘贴：

public static void main(final String[] args) {
    Permutation<Integer> permutation = new Permutation<>(1, 2, 3);
    do {
        System.out.println(permutation);
    } while (permutation.nextPermutation());
}

这将打印出1, 2, 3数组的所有排列组合。

从您的问题中，我了解到您需要：给定集合的每个子集的所有排列组合。

获取给定集合的所有排列组合部分已经完成 - 使用Permutation类。现在我们需要知道如何获取给定集合的所有子集。在下面的代码中，我使用了位掩码来完成这个操作。

请查看以下一些链接，以了解如何使用位掩码生成给定集合的所有子集：

• 打印列表的所有可能子集
• http://www.ugrad.cs.ubc.ca/~cs490/sec202/notes/intro/bitmask.pdf

以下是所需内容：

public static void main(final String[] args) {
  List<String> list = Arrays.asList("a", "b", "c");
  int numberOfSubsets = 1 << list.size();

  for (int mask = 0; mask < numberOfSubsets; mask++) {
    List<String> subset = new ArrayList<>();
    int N = mask;

    for (int i = 0; i < list.size(); i++) {
      if (N % 2 == 1)
        subset.add(list.get(i));
      N /= 2;
    }

    Permutation<String> permutation = new Permutation<>(subset);
    do {
      System.out.println(permutation);
    } while (permutation.nextPermutation());
  }

}

我们将给定集合的每个子集都包装在 Permutation 类周围，让它完成工作。

- Herman Zvonimir Došilović

---

太复杂了。我提供的算法非常简单。这个算法需要依赖另一个库（或该代码的副本），并且不能处理超过32个整数。不过它的优点是懒惰。 - Programmer Person

Answer 2

一般的排列生成算法应该可以使用，你只需要进行微调以打印排列的前缀即可。

我最近提供了一个关于排列的答案，但它是用Python编写的。转换为Java应该很容易。

以下是添加了前缀打印的代码：

def permute(done, remaining):

  print done  # Move this to the if below to print only full permutations.

  if not remaining:
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

def main():
  permute([], range(1,4))

if __name__ == "__main__":
  main()

这是输出结果：

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
[2, 3]
[2, 3, 1]
[3]
[3, 1]
[3, 1, 2]
[3, 2]
[3, 2, 1]

这是相同的算法的Java版本，对我有效，看起来你的尝试存在错误（例如从完成列表中删除，而不是将其设置为null）。

class Permutation {
  public static void print(ArrayList<Integer> array) {
    System.out.print("[");
    for (Integer elem: array) {
      System.out.print(elem.toString());
    }
    System.out.println("]");
  }

  public static void Permute(ArrayList<Integer> done,
                             ArrayList<Integer> remaining) {
    print(done);
    if (remaining.size() == 0) {
      return;
    }

    ArrayList<Integer> sorted = new ArrayList<Integer>(remaining);
    Collections.sort(sorted);
    for (int j = 0; j < remaining.size(); j++) {
      Integer c = sorted.get(j);
      remaining.remove(c);
      done.add(c);
      Permute(done, remaining);
      done.remove(c);
      remaining.add(0, c);
    }
  }

  public static void main(String[] args) {
    ArrayList<Integer> remaining =
      new ArrayList<Integer>(Arrays.asList(1,2,3,4));
    ArrayList<Integer> done = new ArrayList<Integer>();
    Permute(done, remaining);
  }
}

- Programmer Person

---

我添加了一个py文件代替java文件，因为我强烈怀疑这可能是一份作业。此外，py文件很方便地可用... - Programmer Person

@barbara：在我看来，询问作业是可以的。只是不想破坏你的学习体验，以防万一，我的意思并不是指责你什么。事实上，我很高兴看到你正在与回答你问题的人互动！我看到很多人只是问一个问题，却不费心去感谢那些试图帮助他们的人所付出的努力。 - Programmer Person

请注意，Java的print方法假设数字（为了消除讨厌的滚动条而设计）。 - Programmer Person

似乎你的解决方案不起作用。尝试使用new ArrayList<String>(Arrays.asList("A", "B", "C"))运行它。它会打印出[] [A] [AB] [ABC] [AC] [ACB] [C] [CA] [CAB] [CB] [CBA] [A] [AC] [ACB] [AB] [ABC]。 - barbara

@barbara：看起来我放了一个旧版本。这一行 Integer c = remaining.get(j) 必须改为 Integer c = sorted.get(j)。已修复。 - Programmer Person

是的，现在它运行良好。感谢您的纠正。 - barbara