1. Introduction

1.绪论

In this article, we’ll look at how to create permutations of an array.

在这篇文章中，我们将看看如何创建数组的permutations。

First, we’ll define what a permutation is. Second, we’ll look at some constraints. And third, we’ll look at three ways to calculate them: recursively, iteratively, and randomly.

首先，我们将定义什么是排列组合。第二，我们将看一下一些约束条件。第三，我们将看一下计算它们的三种方法：递归、迭代和随机。

We’ll focus on the implementation in Java and therefore won’t go into a lot of mathematical detail.

我们将专注于在Java中的实现，因此不会涉及大量的数学细节。

2. What Is a Permutation?

2.什么是排列组合？

A permutation of a set is a rearrangement of its elements. A set which consists of n elements has n! permutations. Here n! is the factorial, which is the product of all positive integers smaller or equal to n.

一个集合的互换是其元素的重新排列。一个由n个元素组成的集合有n！种排列方式。这里n!是阶乘，即所有小于或等于n的正整数的乘积。

2.1. Example

2.1.例子

The array of integers [3,4,7] has three elements and six permutations:

整数阵列[3,4,7]有三个元素和六个排列组合。

n! = 3! = 1 x 2 x 3 = 6

n!= 3!= 1 x 2 x 3 = 6

Permutations: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

叠加。[3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Constraints

2.2.限制条件

The number of permutation increases fast with n. While it takes only a few seconds to generate all permutations of ten elements, it will take two weeks to generate all permutations of 15 elements:

变化的数量随着n快速增加。虽然生成10个元素的所有排列组合只需要几秒钟，但生成15个元素的所有排列组合则需要两周时间。

3. Algorithms

3.算法

3.1. Recursive Algorithm

3.1.递归算法

The first algorithm we look at is Heap’s algorithm. It’s a recursive algorithm which produces all permutations by swapping one element per iteration.

我们看的第一个算法是Heap的算法。这是一种递归算法，通过每次迭代交换一个元素来产生所有的排列组合。

The input array will be modified. If we don’t want that, we need to create a copy of the array before calling the method:

输入的数组将被修改。如果我们不希望这样，我们需要在调用该方法之前创建一个数组的副本。

public static <T> void printAllRecursive(
  int n, T[] elements, char delimiter) {

    if(n == 1) {
        printArray(elements, delimiter);
    } else {
        for(int i = 0; i < n-1; i++) {
            printAllRecursive(n - 1, elements, delimiter);
            if(n % 2 == 0) {
                swap(elements, i, n-1);
            } else {
                swap(elements, 0, n-1);
            }
        }
        printAllRecursive(n - 1, elements, delimiter);
    }
}

The method uses two helper methods:

该方法使用两个辅助方法。

private void swap(T[] input, int a, int b) {
    T tmp = input[a];
    input[a] = input[b];
    input[b] = tmp;
}

private void printArray(T[] input) {
    System.out.print('\n');
    for(int i = 0; i < input.length; i++) {
        System.out.print(input[i]);
    }
}

Here, we write the result to System.out, however, we can easily store the result in an array or in a list instead.

在这里，我们将结果写入System.out，然而，我们可以很容易地将结果存储在一个数组或一个列表中。

3.2. Iterative Algorithm

3.2.迭代算法

Heap’s algorithm can also be implemented using iterations:

Heap的算法也可以用迭代来实现：。

int[] indexes = new int[n];
int[] indexes = new int[n];
for (int i = 0; i < n; i++) {
    indexes[i] = 0;
}

printArray(elements, delimiter);

int i = 0;
while (i < n) {
    if (indexes[i] < i) {
        swap(elements, i % 2 == 0 ?  0: indexes[i], i);
        printArray(elements, delimiter);
        indexes[i]++;
        i = 0;
    }
    else {
        indexes[i] = 0;
        i++;
    }
}

3.3. Permutations in Lexicographical Order

3.3.词典中的排列组合

If the elements are comparable, we can generate permutations sorted by the natural order of the elements:

如果元素具有可比性，我们可以生成按元素的自然顺序排序的变异。

public static <T extends Comparable<T>> void printAllOrdered(
  T[] elements, char delimiter) {

    Arrays.sort(elements);
    boolean hasNext = true;

    while(hasNext) {
        printArray(elements, delimiter);
        int k = 0, l = 0;
        hasNext = false;
        for (int i = elements.length - 1; i > 0; i--) {
            if (elements[i].compareTo(elements[i - 1]) > 0) {
                k = i - 1;
                hasNext = true;
                break;
            }
        }

        for (int i = elements.length - 1; i > k; i--) {
            if (elements[i].compareTo(elements[k]) > 0) {
                l = i;
                break;
            }
        }

        swap(elements, k, l);
        Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length));
    }
}

This algorithm has a reverse operation in every iteration and therefore it is less efficient on arrays than Heap’s algorithm.

这个算法在每个迭代中都有一个反转操作，因此它在数组上的效率比Heap的算法低。

3.4. Randomized Algorithm

3.4.随机化算法

If n is big, we can generate a random permutation by shuffling the array:

如果n很大，我们可以通过洗牌产生一个随机的排列组合。

Collections.shuffle(Arrays.asList(elements));

We can do this several times to generate a sample of permutations.

我们可以这样做几次，以产生一个排列组合的样本。

We might create the same permutations more than once, however, for big values of n, the chances to generate the same permutation twice are low.

我们可能会创造相同的排列组合超过一次，然而，对于大的n值，产生相同排列组合两次的机会很低。

4. Conclusion

4.总结

There are many ways to generate all permutations of an array. In this article, we saw the recursive and iterative Heap’s algorithm and how to generate a sorted list of permutations.

有许多方法可以生成一个数组的所有排列组合。在这篇文章中，我们看到了递归和迭代Heap的算法，以及如何生成一个排序的排列组合列表。

It’s not feasible to generate all permutations for large arrays, therefore, we can generate random permutations instead.

对于大型数组来说，生成所有的排列组合是不可行的，因此，我们可以生成随机排列组合来代替。

The implementation of all code snippets in this article can be found in our Github repository.

本文中所有代码片段的实现都可以在我们的Github资源库中找到。