Java 没有递归的置换算法？爪哇

Permutation algorithm without recursion? Java

提问by Andreas Hornig

I would like to get all combination of a number without any repetition. Like 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. I tried to find an easy scheme, but couldn't. I drew a graph/tree for it and this screams to use recursion. But I would like to do this without recursion, if this is possible.

我想获得一个数字的所有组合而没有任何重复。像 0.1.2、0.2.1、1.2.0、1.0.2、2.0.1、2.1.0。我试图找到一个简单的方案，但不能。我为它画了一个图/树，这尖叫着要使用递归。但如果可能的话，我想不递归地做到这一点。

Can anyone please help me to do that?

任何人都可以帮我做到这一点吗？

回答by bobbymcr

In general, any recursive algorithm can always be reduced to an iterative one through the use of stack or queue data structures.

通常，通过使用堆栈或队列数据结构，任何递归算法总是可以简化为迭代算法。

For this particular problem, it might be more instructive to look at the C++ STL algorithm std::next_permutation. According to Thomas Guest at wordaligned.org, the basic implementation looks like this:

对于这个特定问题，查看 C++ STL 算法可能更有启发性std::next_permutation。根据wordaligned.org上的 Thomas Guest 的说法，基本实现如下所示：

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;

    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

Note that it does not use recursion and is relatively straightforward to translate to another C-like language like Java. You may want to read up on std::iter_swap, std::reverse, and bidirectional iterators(what Iterrepresents in this code) as well.

请注意，它不使用递归，并且相对简单地转换为另一种类似 C 的语言，如 Java。您可能还想阅读std::iter_swap、std::reverse和双向迭代器（Iter此代码中表示的内容）。

回答by Eyal Schneider

Here is a generic permutation enumerator I wrote a year ago. It can also produce "sub-permutations":

这是我一年前编写的通用排列枚举器。它还可以产生“子排列”：

public class PermUtil <T> {
 private T[] arr;
 private int[] permSwappings;

 public PermUtil(T[] arr) {
  this(arr,arr.length);
 }

 public PermUtil(T[] arr, int permSize) {
  this.arr = arr.clone();
  this.permSwappings = new int[permSize];
  for(int i = 0;i < permSwappings.length;i++)
   permSwappings[i] = i;
 }

 public T[] next() {
  if (arr == null)
   return null;

  T[] res = Arrays.copyOf(arr, permSwappings.length);
  //Prepare next
  int i = permSwappings.length-1;
  while (i >= 0 && permSwappings[i] == arr.length - 1) {
   swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
   permSwappings[i] = i;
   i--;
  }

  if (i < 0)
   arr = null;
  else {   
   int prev = permSwappings[i];
   swap(i, prev);
   int next = prev + 1;
   permSwappings[i] = next;
   swap(i, next);
  }

  return res;
 }

 private void swap(int i, int j) {
  T tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
 }

}

The idea behind my algorithm is that any permutation can be expressed as a uniquesequence of swap commands. For example, for <A,B,C>, the swap sequence 012 leaves all items in place, while 122 starts by swapping index 0 with index 1, then swaps 1 with 2, and then swaps 2 with 2 (i.e. leaves it in place). This results in the permutation BCA.

我的算法背后的想法是，任何排列都可以表示为唯一的交换命令序列。例如，对于 <A,B,C>，交换序列 012 将所有项目留在原地，而 122 开始时将索引 0 与索引 1 交换，然后将 1 与 2 交换，然后将 2 与 2 交换（即，将其留在地方）。这导致排列BCA。

This representation is isomorphic to the permutation representation (i.e. one to one relationship), and it is very easy to "increment" it when traversing the permutations space. For 4 items, it starts from 0123 (ABCD) and ends with 3333(DABC).

这种表示与置换表示同构（即一对一的关系），在遍历置换空间时很容易“递增”它。对于 4 个项目，它从 0123（ABCD）开始，以 3333（DABC）结束。

回答by hrzafer

Here is the generic and iterative permutation, kpermutation and combination generator classes that I wrote based on the implementations hereand here. My classes use those as inner classes. They also implement Iterable Interface to be foreachable.

这是我根据此处和此处的实现编写的通用和迭代排列、kpermutation 和组合生成器类。我的课程使用这些作为内部课程。它们还实现了可 foreachable 的 Iterable 接口。

 List<String> objects = new ArrayList<String>();
    objects.add("A");
    objects.add("B");
    objects.add("C");

    Permutations<String> permutations = new Permutations<String>(objects);
    for (List<String> permutation : permutations) {
        System.out.println(permutation);
    }

    Combinations<String> combinations = new Combinations<String>(objects, 2);
    for (List<String> combination : combinations) {
        System.out.println(combination);
    }

    KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
    for (List<String> kPermutation : kPermutations) {
        System.out.println(kPermutation);
    }

The Combinations class:

组合类：

public class Combinations<T> implements Iterable<List<T>> {

    CombinationGenerator cGenerator;
    T[] elements;
    int[] indices;

    public Combinations(List<T> list, int n) {
        cGenerator = new CombinationGenerator(list.size(), n);
        elements = (T[]) list.toArray();
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {

            int pos = 0;

            public boolean hasNext() {
                return cGenerator.hasMore();
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                indices = cGenerator.getNext();
                List<T> combination = new ArrayList<T>();
                for (int i = 0; i < indices.length; i++) {
                    combination.add(elements[indices[i]]);
                }
                return combination;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    private final class CombinationGenerator {

        private int[] a;
        private int n;
        private int r;
        private BigInteger numLeft;
        private BigInteger total;

        //------------
        // Constructor
        //------------
        public CombinationGenerator(int n, int r) {
            if (n < 1) {
                throw new IllegalArgumentException("Set must have at least one element");
            }
            if (r > n) {
                throw new IllegalArgumentException("Subset length can not be greater than set length");
            }
            this.n = n;
            this.r = r;
            a = new int[r];
            BigInteger nFact = getFactorial(n);
            BigInteger rFact = getFactorial(r);
            BigInteger nminusrFact = getFactorial(n - r);
            total = nFact.divide(rFact.multiply(nminusrFact));
            reset();
        }

        //------
        // Reset
        //------
        public void reset() {
            for (int i = 0; i < a.length; i++) {
                a[i] = i;
            }
            numLeft = new BigInteger(total.toString());
        }

        //------------------------------------------------
        // Return number of combinations not yet generated
        //------------------------------------------------
        public BigInteger getNumLeft() {
            return numLeft;
        }

        //-----------------------------
        // Are there more combinations?
        //-----------------------------
        public boolean hasMore() {
            return numLeft.compareTo(BigInteger.ZERO) == 1;
        }

        //------------------------------------
        // Return total number of combinations
        //------------------------------------
        public BigInteger getTotal() {
            return total;
        }

        //------------------
        // Compute factorial
        //------------------
        private BigInteger getFactorial(int n) {
            BigInteger fact = BigInteger.ONE;
            for (int i = n; i > 1; i--) {
                fact = fact.multiply(new BigInteger(Integer.toString(i)));
            }
            return fact;
        }

        //--------------------------------------------------------
        // Generate next combination (algorithm from Rosen p. 286)
        //--------------------------------------------------------
        public int[] getNext() {

            if (numLeft.equals(total)) {
                numLeft = numLeft.subtract(BigInteger.ONE);
                return a;
            }

            int i = r - 1;
            while (a[i] == n - r + i) {
                i--;
            }
            a[i] = a[i] + 1;
            for (int j = i + 1; j < r; j++) {
                a[j] = a[i] + j - i;
            }

            numLeft = numLeft.subtract(BigInteger.ONE);
            return a;

        }
    }
}

The Permutations Class:

排列类：

public class Permutations<T> implements Iterable<List<T>> {

    PermutationGenerator pGenerator;
    T[] elements;
    int[] indices;

    public Permutations(List<T> list) {
        pGenerator = new PermutationGenerator(list.size());
        elements = (T[]) list.toArray();
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {

            int pos = 0;

            public boolean hasNext() {
                return pGenerator.hasMore();
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                indices = pGenerator.getNext();
                List<T> permutation = new ArrayList<T>();
                for (int i = 0; i < indices.length; i++) {
                    permutation.add(elements[indices[i]]);
                }
                return permutation;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }

    private final class PermutationGenerator {

        private int[] a;
        private BigInteger numLeft;
        private BigInteger total;

        //-----------------------------------------------------------
        // Constructor. WARNING: Don't make n too large.
        // Recall that the number of permutations is n!
        // which can be very large, even when n is as small as 20 --
        // 20! = 2,432,902,008,176,640,000 and
        // 21! is too big to fit into a Java long, which is
        // why we use BigInteger instead.
        //----------------------------------------------------------
        public PermutationGenerator(int n) {
            if (n < 1) {
                throw new IllegalArgumentException("Set must have at least one element");
            }
            a = new int[n];
            total = getFactorial(n);
            reset();
        }

        //------
        // Reset
        //------
        public void reset() {
            for (int i = 0; i < a.length; i++) {
                a[i] = i;
            }
            numLeft = new BigInteger(total.toString());
        }

        //------------------------------------------------
        // Return number of permutations not yet generated
        //------------------------------------------------
        public BigInteger getNumLeft() {
            return numLeft;
        }

        //------------------------------------
        // Return total number of permutations
        //------------------------------------
        public BigInteger getTotal() {
            return total;
        }

        //-----------------------------
        // Are there more permutations?
        //-----------------------------
        public boolean hasMore() {
            return numLeft.compareTo(BigInteger.ZERO) == 1;
        }

        //------------------
        // Compute factorial
        //------------------
        private BigInteger getFactorial(int n) {
            BigInteger fact = BigInteger.ONE;
            for (int i = n; i > 1; i--) {
                fact = fact.multiply(new BigInteger(Integer.toString(i)));
            }
            return fact;
        }

        //--------------------------------------------------------
        // Generate next permutation (algorithm from Rosen p. 284)
        //--------------------------------------------------------
        public int[] getNext() {

            if (numLeft.equals(total)) {
                numLeft = numLeft.subtract(BigInteger.ONE);
                return a;
            }

            int temp;

            // Find largest index j with a[j] < a[j+1]

            int j = a.length - 2;
            while (a[j] > a[j + 1]) {
                j--;
            }

            // Find index k such that a[k] is smallest integer
            // greater than a[j] to the right of a[j]

            int k = a.length - 1;
            while (a[j] > a[k]) {
                k--;
            }

            // Interchange a[j] and a[k]

            temp = a[k];
            a[k] = a[j];
            a[j] = temp;

            // Put tail end of permutation after jth position in increasing order

            int r = a.length - 1;
            int s = j + 1;

            while (r > s) {
                temp = a[s];
                a[s] = a[r];
                a[r] = temp;
                r--;
                s++;
            }

            numLeft = numLeft.subtract(BigInteger.ONE);
            return a;

        }
    }
}

And the KPermutations class that actually using Permutations and Combinations classes:

以及实际使用 Permutations 和 Combinations 类的 KPermutations 类：

public class KPermutations<T> implements Iterable<List<T>> {
    Combinations<T> combinations;

    public KPermutations(List<T> list, int k) {
        if (k<1){
            throw new IllegalArgumentException("Subset length k must me at least 1");
        }
        combinations = new Combinations<T>(list, k);
    }

    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            Iterator<List<T>> it = combinations.iterator();
            Permutations<T> permutations = new Permutations<T>(combinations.iterator().next());

            // Has more combinations but no more permutation for current combination
            public boolean hasNext() {
                if (combinations.iterator().hasNext() && !permutations.iterator().hasNext()){
                    permutations = new Permutations<T>(combinations.iterator().next());
                    return true;
                }
                //Has more permutation for current combination
                else if (permutations.iterator().hasNext()){
                    return true;
                }
                // No more combination and permutation
                return false;
            }

            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return permutations.iterator().next();
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }


}

回答by user unknown

Here I have a solution in scala, which could be used from java, but can be - with much more code - been implemented in Java as well, to allow to use an iterator for the simplified for-loop:

在这里，我在 scala 中有一个解决方案，它可以从 java 中使用，但可以 - 用更多的代码 - 在 Java 中实现，以允许使用迭代器进行简化的 for 循环：

for (List<Integer> list: permutations) 
    doSomething (list);

To allow for the simplified for-loop, we need to implement Iterable, which means we have to provide a method which returns an Iterator, which happens to be another interface, which means we have to implement 3 methods: hasNext (); next (); and remove ();

为了允许简化的for循环，我们需要实现Iterable，这意味着我们必须提供一个返回Iterator的方法，它恰好是另一个接口，这意味着我们必须实现3个方法：hasNext()；下一个 （）; 并删除 ();

import java.util.*;

class PermutationIterator <T> implements Iterator <List <T>> {

    private int  current = 0;
    private final List <T> lilio;
    public final long last;

    public PermutationIterator (final List <T> llo) {
        lilio = llo;
        long product = 1;
        for (long p = 1; p <= llo.size (); ++p) 
            product *= p; 
        last = product;
    }

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private long fac (long l) 
    {
        for (long i = l - 1L; i > 1L; --i)
            l *= i; 
        return l;
    }
    /**
        new version, which produces permutations in increasing order:
    */
    private List <T> get (final long code, final List <T> list) {
        if (list.isEmpty ()) 
            return list;
        else
        {
            int len = list.size ();     // len = 4
            long max = fac (len);       // max = 24
            long divisor = max / len;   // divisor = 6
            int i = (int) (code / divisor); // i = 2
            List <T> second = new ArrayList <T> (list.size ());
            second.addAll (list);
            T el = second.remove (i);
            List <T> tt = new ArrayList <T> ();
            tt.add (el);
            tt.addAll (get (code - divisor * i, second));
            return tt;
        }
    }

    public List <T> get (final int code) 
    {
        return get (code, lilio);
    }
}

class PermutationIterable <T> implements Iterable <List <T>> {

    private List <T> lilio; 

    public PermutationIterable (List <T> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new PermutationIterator <T> (lilio);
    }

    private long invers (final List <T> pattern, final List <T> matcher)
    {
        if (pattern.isEmpty ())
            return 0L;
        T first = pattern.get (0);
        int idx = matcher.indexOf (first);
        long l = (pattern.size () - 1L) * idx;
        pattern.remove (0);
        matcher.remove (idx);
        return l + invers (pattern, matcher);
    }
    /**
      make a deep copy, since the called method will destroy the parameters
    */
    public long invers (final List <T> lt)
    {
        List <T> copy = new ArrayList <T> (lilio.size ());
        copy.addAll (lilio);
        return invers (lt, copy); 
    }   
}

class PermutationIteratorTest {

    public static List <Integer> genList (int... a) {
        List <Integer> li = new ArrayList <Integer> ();
        for (int i: a) 
            li.add (i);
        return li;
    }

    public static void main (String[] args) {
        List <Integer> il = new ArrayList <Integer> ();
        // autoboxing, add '0' to 'z' as Character: 
        for (int c = 0; c < 3; ++c)
        {
            il.add (c);
        }
        PermutationIterable <Integer> pi = new PermutationIterable <Integer> (il);
        for (List<Integer> li: pi)
            show (li);
        System.out.println ("-again-");
        // do it a second time: 
        for (List <Integer> li: pi)
            show (li);
        // test the inverse:
        System.out.println ("for (2,1,0) expecting 5 ?= " + pi.invers (genList (2, 1, 0)));
        System.out.println ("for (2,0,1) expecting 4 ?= " + pi.invers (genList (2, 0, 1)));
        System.out.println ("for (1,0,2) expecting 3 ?= " + pi.invers (genList (1, 2, 0)));
        System.out.println ("for (1,2,0) expecting 2 ?= " + pi.invers (genList (1, 0, 2)));
        System.out.println ("for (0,2,1) expecting 1 ?= " + pi.invers (genList (0, 2, 1)));
        System.out.println ("for (0,1,2) expecting 0 ?= " + pi.invers (genList (0, 1, 2)));
        Random r = new Random ();
        PermutationIterator <Integer> pitor = (PermutationIterator  <Integer>) pi.iterator ();
        for (int i = 0; i < 10; ++i)
        {
            int rnd = r.nextInt ((int) pitor.last); 
            List <Integer> rli = pitor.get (rnd);
            show (rli);
        }
    }

    public static void show (List <?> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o);
        System.out.println (")");
    }
}

PermutationIterator contains the additional, public method public List <T> get (final int code)which is handy, if you like to pick a certain permutation by index, for example by random. You know the size (last) and can therefore take a permutation of the valid range by index.

PermutationIterator 包含额外的公共方法public List <T> get (final int code)，如果您喜欢按索引（例如随机）选择某个排列，则该方法 很方便。您知道大小（最后一个），因此可以按索引对有效范围进行排列。

PermutationIterable contains a method 'invers' which will generate the opposite: The index of a certain permutation.

PermutationIterable 包含一个方法“invers”，它会生成相反的结果：某个排列的索引。

Internally, inversand getwork recursively, but all the permutations aren't produced recursively, so this shouldn't be a problem even for big permutations. Note, that for 21 elements, you exceed the size of longs, and 20 steps of recursion shouldn't be a problem at all.

在内部，INVERS和获得工作递归，但所有的排列不递归生产的，所以这不应该是即使大排列的一个问题。请注意，对于 21 个元素，您超出了 long 的大小，并且 20 步递归根本不应该是问题。

回答by Anders

This has of course been done before, and one sollution is Bells Permutation Algorithm. You find a sollution here, where you can find a recursive sollution in Prolog and the non-recursive Bell Permutation Algorithm written in Pascal.

这当然以前已经完成了，一种解决方案是Bells Permutation Algorithm。您可以在此处找到解决方案，您可以在其中找到 Prolog 中的递归解决方案以及用 Pascal 编写的非递归 Bell Permutation Algorithm。

To convert them to Java is left as an exercise for the reader.

将它们转换为 Java 留给读者作为练习。

回答by Filip Nguyen

You should use the fact that when you want all permutations of N numbers there are N! possibilities. Therefore each number x from 1..N! encodes such a permutation. Here is a sample that iteratively prints out all permutations of a sting.

您应该使用这样一个事实，即当您想要 N 个数字的所有排列时，有 N 个！可能性。因此每个数字 x 来自 1..N！编码这样的排列。这是一个迭代打印出刺痛的所有排列的示例。

private static void printPermutationsIterative(String string){
        int [] factorials = new int[string.length()+1];
        factorials[0] = 1;
        for (int i = 1; i<=string.length();i++) {
            factorials[i] = factorials[i-1] * i;
        }

        for (int i = 0; i < factorials[string.length()]; i++) {
            String onePermutation="";
            String temp = string;
            int positionCode = i;
            for (int position = string.length(); position > 0 ;position--){
                int selected = positionCode / factorials[position-1];
                onePermutation += temp.charAt(selected);
                positionCode = positionCode % factorials[position-1];
                temp = temp.substring(0,selected) + temp.substring(selected+1);
            }
            System.out.println(onePermutation);
        }
    }

回答by dickf

It is easy to write the recursive permutation, but it requires exporting the permutations from deeply nested loops. (That is an interesting exercise.) I needed a version that permuted strings for anagrams. I wrote a version that implements Iterable<String>so it can be used in foreach loops. It can easily be adapted to other types such as int[]or even a generic type <T[]>by changing the constructor and the type of attribute 'array'.

编写递归排列很容易，但它需要从深度嵌套的循环中导出排列。（这是一个有趣的练习。）我需要一个版本来排列字谜的字符串。我写了一个实现的版本，Iterable<String>所以它可以在 foreach 循环中使用。通过更改构造函数和属性“数组”的类型，它可以很容易地适应其他类型，例如int[]甚至是泛型类型<T[]>。

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * An implicit immutable collection of all permutations of a string with an 
 * iterator over the permutations.<p>  implements Iterable&ltString&gt
 * @see #StringPermutation(String)
 */
public class StringPermutation implements Iterable<String> {

    // could implement Collection<String> but it's immutable, so most methods are essentially vacuous

    protected final String string;

    /**
     * Creates an implicit Iterable collection of all permutations of a string
     * @param string  String to be permuted
     * @see Iterable
     * @see #iterator
     */
    public StringPermutation(String string) {
        this.string = string;
    }

    /**
     * Constructs and sequentially returns the permutation values 
     */
    @Override
    public Iterator<String> iterator() {

        return new Iterator<String>() {

            char[] array = string.toCharArray(); 
            int length = string.length();
            int[] index = (length == 0) ? null : new int[length];

            @Override
            public boolean hasNext() {
                return index != null;
            }

            @Override
            public String next() {

                if (index == null) throw new NoSuchElementException();

                for (int i = 1; i < length; ++i) {
                    char swap = array[i];
                    System.arraycopy(array, 0, array, 1, i);
                    array[0] = swap;
                    for (int j = 1 ; j < i; ++j) {
                        index[j] = 0;
                    }
                    if (++index[i] <= i) {
                        return  new String(array);
                    }
                    index[i] = 0;                    
                }
                index = null;
                return new String(array);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(); 
            }
        };
    }
}

回答by ArK

import java.io.*;
class Permutation
{
String w;

public void accept() throws IOException 
{ BufferedReader ak=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter a word"); w=ak.readLine(); }

public void permute()
{
int l,s,m,p,k,t,x,n,r;
s=m=0;p=t=k=1;
l=w.length();
for(x=1;x<=l;x++)
{
p*=x; s+=x; t*=10;
}
System.out.println("\n"+"The "+p+" possible permutations of the word are:"+"\n");
for(x=t/10;x

public boolean isUnique(int n) {
int a[]={0,0,0,0,0,0,0,0,0,0};
int r;
while(n!=0)
{
r=n%10;
if(a[r]!=0 || r==0)
return false;
else
a[r]++;
n/=10;
}
return true;
}
}

回答by Vladimir

IEnumerable<IEnumerable<int>> generatePermutations(int length)
{
    if (length <= 0) throw new ArgumentException();

    var resultCollection = new List<IEnumerable<int>> { new [] { 0 } };

    for (var index = 1; index < length; index++)
    {
        var newResultCollection = new List<IEnumerable<int>>();
        foreach (var result in resultCollection)
        {
            for (var insertIndex = index; insertIndex >= 0; insertIndex--)
            {
                var list = new List<int>(result);
                list.Insert(insertIndex, index);
                newResultCollection.Add(list);
            }
        }
        resultCollection = newResultCollection;
    }

    return resultCollection;
}

回答by Mattias F

Most examples I've seen so far has either been too complicated, only using Strings or using swaps, so I figured I'd make one which is iterative, intuitive, generic and swap free.

到目前为止我看到的大多数例子要么太复杂，要么只使用字符串，要么使用交换，所以我想我会做一个迭代的、直观的、通用的和无交换的。

public static <T> List<List<T>> permutations(List<T> es){

  List<List<T>> permutations = new ArrayList<List<T>>();

  if(es.isEmpty()){
    return permutations;
  }

  // We add the first element
  permutations.add(new ArrayList<T>(Arrays.asList(es.get(0))));

  // Then, for all elements e in es (except from the first)
  for (int i = 1, len = es.size(); i < len; i++) {
    T e = es.get(i);

    // We take remove each list l from 'permutations'
    for (int j = permutations.size() - 1; j >= 0; j--) {
      List<T> l = permutations.remove(j);

      // And adds a copy of l, with e inserted at index k for each position k in l
      for (int k = l.size(); k >= 0; k--) {
        ArrayList<T> ts2 = new ArrayList<>(l);
        ts2.add(k, e);
        permutations.add(ts2);
      }
    }
  }
  return permutations;
}

Example: we want all permutations of [a,b,c]
We add a and get [a] // [b,c] remaining
We take a from the list and adds [a,b] and [b,a] // [c] remaining
We remove [b,a], and inserts [b,a,c], [b,c,a], [c,b,a] and then we remove [a,b], and inserts [a,b,c], [a,c,b], [c,a,b]

示例：我们想要 [a,b,c] 的所有排列
我们添加 a 并得到 [a] // [b,c] 剩余
我们从列表中取出 a 并添加 [a,b] 和 [b,a] / / [c] 剩余
我们移除 [b,a]，并插入 [b,a,c], [b,c,a], [c,b,a] 然后我们移除 [a,b]，并插入[a,b,c], [a,c,b], [c,a,b]