[转]全排列 - 非递归实现
import java.math.BigInteger;public class PermutationGenerator { private int[] a; private BigInteger numLeft; private BigInteger total; public PermutationGenerator(int n) { if (n < 1) { throw new IllegalArgumentException("Min 1"); } a = new int[n]; total = getFactorial(n); reset(); } public void reset() { for (int i = 0; i < a.length; i++) { a[i] = i; } numLeft = new BigInteger(total.toString()); } public boolean hasMore() { return numLeft.compareTo(BigInteger.ZERO) == 1; } //得到组合的总数 private static 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; } public int[] getNext() { if (numLeft.equals(total)) { numLeft = numLeft.subtract(BigInteger.ONE); return a; } // Find largest index j with a[j] < a[j+1] int j = a.length - 2; while (a[j] > a[j + 1]) { j--; } //a[]从右向左，找index k，使得a[k]>a[j] int k = a.length - 1; while (a[j] > a[k]) { k--; } //a[j]a[k]互换 interchange(a, j, k); //如果j不是倒数第二个index，则将j+1到a结尾的所有元素，对称互换 int r = a.length - 1; int s = j + 1; while (r > s) { interchange(a, r, s); r--; s++; } numLeft = numLeft.subtract(BigInteger.ONE); return a; } private static int[] interchange(int[] arr, int indexA, int indexB) { int temp = arr[indexA]; arr[indexA] = arr[indexB]; arr[indexB] = temp; return arr; } //测试 public static void main(String[] args) { int[] indices; String[] elements = new String[]{"a", "b", "c"}; PermutationGenerator x = new PermutationGenerator(elements.length); StringBuffer permutation; while (x.hasMore()) { permutation = new StringBuffer("%"); indices = x.getNext(); for (int i = 0; i < indices.length; i++) { permutation.append(elements[indices[i]]).append("%"); } System.out.println(permutation.toString()); } }}OUTPUT:%a%b%c%%a%c%b%%b%a%c%%b%c%a%%c%a%b%%c%b%a%