没有递归的排列算法？爪哇

Question

我想得到一个数字的所有组合，没有任何重复。 如 0.1.2、0.2.1、1.2.0、1.0.2、2.0.1、2.1.0。 我试图找到一个简单的方案，但找不到。我为它画了一个图/树，这尖叫着使用递归。 但如果可能的话，我想在不使用递归的情况下执行此操作。

谁能帮我做到这一点吗？

Answer 1

这是一个简单的 Java 函数，用于打印所有可能的排列（包括较小的排列直至空字符串“”）。如果您只需要打印相同长度的排列，只需在打印之前添加 if 语句即可。

其思想与递归相同。但不是堆叠方法调用。我们使用数据结构（如本例中的列表）来堆叠排列。

import java.util.LinkedList;
import java.util.List;


    public class Permutations {

        public void perm(String input) {
            List<String[]> buffer = new LinkedList<>();
            buffer.add(new String[]{input, ""});
            while (!buffer.isEmpty()) {
                String[] perm = buffer.remove(0);
                System.out.println(perm[1]);
                for (int i = 0; i < perm[0].length(); i++) {
                    buffer.add(new String[]{perm[0].substring(0, i) + perm[0].substring(i + 1), perm[1] + perm[0].charAt(i)});
                }
            }
        }

    }

Answer 2

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 3

您应该利用这样一个事实：当您想要 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);
        }
    }

Answer 4

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

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

}

我的算法背后的想法是任何排列都可以表示为唯一交换命令序列。例如，对于 ，交换序列 012 将所有项目保留在原位，而 122 首先将索引 0 与索引 1 交换，然后将 1 与 2 交换，然后将 2 与 2 交换（即保留到位）。这导致了排列 BCA。

这种表示与排列表示同构（即一对一关系），并且在遍历排列空间时很容易“递增”它。对于 4 项，从 0123 (ABCD) 开始，到 3333(DABC) 结束。

Answer 5

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

对于这个特定问题，查看 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;
        }
    }
}

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

Answer 6

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

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<String>
 * @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 7

到目前为止，我见过的大多数示例要么太复杂，要么只使用字符串，要么使用交换，所以我想我应该制作一个迭代、直观、通用且无交换的示例。

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

示例：我们想要 [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]

Answer 8

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

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

Combinations 类：

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;

        }
    }
}

Permutations 类：

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;

        }
    }
}

以及实际使用 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();
            }
        };
    }


}

Answer 9

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

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

为了简化for循环，我们需要实现Iterable，这意味着我们必须提供一个返回Iterator的方法，而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 包含附加的公共方法 public List; get (final int code) 如果您想通过索引（例如随机）选择某个排列，这会很方便。您知道大小（最后一个），因此可以按索引对有效范围进行排列。

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

在内部，invers 和 get 递归地工作，但所有排列都不是递归生成的，因此即使对于大排列，这也不应该成为问题。请注意，对于 21 个元素，您超出了 long 的大小，并且 20 步递归根本不应该成为问题。

Answer 10

您可以使用 Factoradics （您可以看到一个实现此处) 或 Knuth 的 L 算法，生成所有排列。下面是后者的实现：

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

Answer 11

这当然以前已经做过，一种解决方案是贝尔排列算法。
您可以在此处找到一个解决方案，在这里您可以找到 Prolog 中的递归解决方案和非递归贝尔排列用 Pascal 编写的算法。

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

Answer 12

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 13

@Filip Nyugen JS 解决方案，适合那些想要 JS 答案的人

function printPermutationsIterative(string) {
    const factorials = [];
    factorials[0] = 1;
    for (let i = 1; i <= string.length; i++) {
        factorials[i] = factorials[i - 1] * i;
    }

    for (let i = 0; i < factorials[string.length]; i++) {
        let onePermutation = "";
        let temp = string;
        let positionCode = i;
        for (let position = string.length; position > 0; position--) {
            let selected = positionCode / factorials[position - 1];
            onePermutation += temp.charAt(selected);
            positionCode = positionCode % factorials[position - 1];
            temp = temp.substring(0, selected) + temp.substring(selected + 1);
        }
        console.log(onePermutation);
    }
}