Thuật toán hoán vị mà không cần đệ quy? Java

Question

Tôi muốn nhận được tất cả sự kết hợp của một số mà không có bất kỳ sự lặp lại nào. Giống như 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. Tôi đã cố gắng tìm một sơ đồ dễ dàng, nhưng không thể. Tôi vẽ một đồ thị/cây cho nó và điều này hét lên để sử dụng đệ quy. Nhưng tôi muốn làm điều này mà không cần đệ quy, nếu điều này là có thể.

Có ai vui lòng giúp tôi làm điều đó không?

Answer 1

Nói chung, mọi thuật toán đệ quy luôn có thể được giảm xuống một thuật toán lặp lại thông qua việc sử dụng cấu trúc dữ liệu xếp chồng hoặc xếp hàng.

Đối với vấn đề cụ thể này, có thể có nhiều hướng dẫn hơn để xem thuật toán C++ STL std::next_permutation. Theo Thomas khách tại wordaligned.org, việc thực hiện cơ bản như sau:

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; 
     } 
    } 
} 

Lưu ý rằng nó không sử dụng đệ quy và là tương đối đơn giản để dịch sang một ngôn ngữ C-like như Java. Bạn có thể muốn đọc lên trên std::iter_swap, std::reverse và bidirectional iterators (số Iter cũng đại diện cho mã này).

Answer 2

Đây là một điều tra hoán vị chung mà tôi đã viết một năm trước đây. Nó cũng có thể tạo ra "sub-hoán vị":

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; 
} 

} 

Ý tưởng đằng sau thuật toán của tôi là bất kỳ hoán vị có thể được thể hiện dưới dạng một chuỗi độc đáo các lệnh swap. Ví dụ, đối với < A, B, C>, trình tự hoán đổi 012 để tất cả các mục tại chỗ, trong khi 122 bắt đầu bằng cách hoán đổi chỉ mục 0 với chỉ mục 1, sau đó hoán đổi 1 với 2, rồi hoán đổi 2 với 2 địa điểm). Điều này dẫn đến BCA hoán vị.

Biểu diễn này là đẳng cấu với biểu diễn hoán vị (nghĩa là mối quan hệ một đến một) và rất dễ "tăng" nó khi đi qua không gian hoán vị. Đối với 4 mục, nó bắt đầu từ(ABCD) và kết thúc bằng 3333 (DABC).

Answer 3

Dưới đây là các hoán vị hoán vị chung, kpermutation và kết hợp mà tôi đã viết dựa trên việc triển khai here và here. Các lớp của tôi sử dụng những lớp đó làm lớp bên trong. Họ cũng thực hiện Giao diện Iterable để được cho phép.

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); 
    } 

Lớp kết hợp:

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; 

     } 
    } 
} 

các hoán vị 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; 

     } 
    } 
} 

Và lớp KPermutations rằng thực sự sử dụng hoán vị và các lớp học kết hợp:

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(); 
      } 
     }; 
    } 


} 

Answer 4

Ở đây tôi có a solution in scala, mà có thể được sử dụng từ java, nhưng có thể - với mã nhiều hơn nữa - được thực hiện trong Java là tốt, để cho phép sử dụng một iterator cho đơn giản cho vòng lặp:

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

Để cho phép vòng lặp đơn giản hóa, chúng ta cần thực thi Iterable, có nghĩa là chúng ta phải cung cấp một phương thức trả về một Iterator, một giao diện khác, có nghĩa là chúng ta phải thực hiện 3 phương thức: hasNext(); kế tiếp(); và xóa();

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 chứa thêm, phương pháp công public List <T> get (final int code) đó là tiện dụng, nếu bạn muốn chọn một hoán vị nhất định bởi chỉ số, ví dụ bằng cách ngẫu nhiên. Bạn biết kích thước (cuối cùng) và do đó có thể có một hoán vị của phạm vi hợp lệ theo chỉ mục.

PermutationTắt có chứa một phương pháp 'invers' sẽ tạo ra điều ngược lại: Chỉ số của một hoán vị nhất định.

Bên trong, invers và được việc đệ quy, nhưng tất cả các hoán vị không được sản xuất một cách đệ quy, vì vậy đây không phải là một vấn đề ngay cả đối với hoán vị lớn. Lưu ý rằng đối với 21 phần tử, bạn vượt quá kích thước của thời lượng và 20 bước đệ quy không phải là vấn đề.

Answer 5

Điều này tất nhiên đã được thực hiện trước đó và một trong số đó là Thuật toán phép thuật Bells. Bạn tìm thấy một sollution here, nơi bạn có thể tìm thấy một sollution đệ quy trong Prolog và không đệ quy Bell Permutation Algorithm được viết bằng Pascal.

Để chuyển đổi chúng sang Java còn lại dưới dạng bài tập cho người đọc.

Answer 6

Bạn nên sử dụng thực tế là khi bạn muốn tất cả hoán vị của các số N có N! khả năng. Do đó, mỗi số x từ 1..N! mã hóa một hoán vị như vậy. Đây là một mẫu lặp đi lặp lại tất cả các hoán vị của một sting.

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); 
     } 
    } 

Answer 7

Thật dễ dàng để viết hoán vị đệ quy, nhưng nó yêu cầu xuất các hoán vị từ vòng lồng sâu. (Đó là một bài tập thú vị.) Tôi cần một phiên bản đã uốn dây cho đảo chữ cái. Tôi đã viết một phiên bản thực hiện Iterable<String> để nó có thể được sử dụng trong vòng foreach. Nó có thể dễ dàng được thích nghi với các loại khác như int[] hoặc thậm chí loại chung <T[]> bằng cách thay đổi hàm tạo và loại thuộc tính 'mảng'.

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(); 
      } 
     }; 
    } 
} 

Answer 8

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; 
} 
} 

Answer 9

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; 
} 

Answer 10

Hầu hết các ví dụ tôi đã nhìn thấy cho đến nay đã được một trong hai quá phức tạp, chỉ sử dụng Strings hoặc sử dụng giao dịch hoán đổi, vì vậy tôi figured tôi muốn làm cho một trong đó là lặp đi lặp lại, trực quan, chung chung và trao đổi miễn phí.

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; 
} 

Ví dụ: chúng tôi muốn tất cả các hoán vị của [a, b, c]
Chúng tôi thêm và nhận được [a] // [b, c] còn lại
Chúng tôi có một từ danh sách và thêm [ a, b] và [b, a] // [c] còn lại
Chúng tôi xóa [b, a] và chèn [b, a, c], [b, c, a], [c, b, a ] và sau đó chúng tôi xóa [a, b] và chèn [a, b, c], [a, c, b], [c, a, b]

Answer 11

Bạn có thể sử dụng Factoradics (bạn có thể thấy triển khai here) hoặc Knuth's L-Algorithm tạo tất cả các hoán vị ns. Sau đây là triển khai sau:

public class Perm { 
    public static void main(String... args) { 
     final int N = 5; 
     int[] sequence = new int[N]; 
     for (int i = 0; i < N; i++) { 
      sequence[i] = i + 1; 
     } 

     printSequence(sequence); 
     permutations(sequence); 
    } 

    private static int factorial(int n) { 
     int fact = 1; 
     for (int i = 1; i <= n; i++) { 
      fact *= i; 
     } 
     return fact; 
    } 

    private static void swap(int[] elements, int i, int j) { 
     int temp = elements[i]; 
     elements[i] = elements[j]; 
     elements[j] = temp; 
    } 

    /** 
    * Reverses the elements of an array (in place) from the start index to the end index 
    */ 
    private static void reverse(int[] array, int startIndex, int endIndex) { 
     int size = endIndex + 1 - startIndex; 
     int limit = startIndex + size/2; 
     for (int i = startIndex; i < limit; i++) { 
      // swap(array, i, startIndex + (size - 1 - (i - startIndex))); 
      swap(array, i, 2 * startIndex + size - 1 - i); 
     } 
    } 

    private static void printSequence(int[] sequence) { 
     for (int i = 0; i < sequence.length; i++) { 
      System.out.printf("%d, ", sequence[i]); 
     } 
     System.out.println(); 
    } 

    /** 
    * Implements the Knuth's L-Algorithm permutation algorithm 
    * modifying the collection in place 
    */ 
    private static void permutations(int[] sequence) { 
     final int N = sequence.length; 
     // There are n! permutations, but the first permutation is the array without 
     // modifications, so the number of permutations is n! - 1 
     int numPermutations = factorial(N) - 1; 

     // For every possible permutation 
     for (int n = 0; n < numPermutations; n++) { 

      // Iterate the array from right to left in search 
      // of the first couple of elements that are in ascending order 
      for (int i = N - 1; i >= 1; i--) { 
       // If the elements i and i - 1 are in ascending order 
       if (sequence[i - 1] < sequence[i]) { 
        // Then the index "i - 1" becomes our pivot index 
        int pivotIndex = i - 1; 

        // Scan the elements at the right of the pivot (again, from right to left) 
        // in search of the first element that is bigger 
        // than the pivot and, if found, swap it 
        for (int j = N - 1; j > pivotIndex; j--) { 
         if (sequence[j] > sequence[pivotIndex]) { 
          swap(sequence, j, pivotIndex); 
          break; 
         } 
        } 

        // Now reverse the elements from the right of the pivot index 
        // (this nice touch to the algorithm avoids the recursion) 
        reverse(sequence, pivotIndex + 1, N - 1); 
        break; 
       } 
      } 

      printSequence(sequence); 
     } 
    } 
}