全排列的非递归算法

import java.util.Arrays;

//全排列的非递归算法

public class FullPermutation {

// 翻转

static void reverse(int[] data, int start, int end) {

int t;

while (start < end) {

t = data[start];

data[start] = data[end];

data[end] = t;

start++;

end--;

}

}

// 交换

static void swap(int[] data, int i, int j) {

int t;

t = data[i];

data[i] = data[j];

data[j] = t;

}

// 查找下一个排列,找到返回true 找不到返回false

static boolean getNextPermutation(int[] data) {

int size = data.length;

// 后找

int i = size - 2;

while ((i >= 0) && (data[i] >= data[i + 1])) {

i--;

}

if (i < 0) {

return false;

}

// 小大

int j = size - 1;

while (data[j] <= data[i]) {

j--;

}

// 交换

swap(data, i, j);

// 翻转

reverse(data, i + 1, size - 1);

return true;

}

// 输出

static void print(int[] data) {

for (int i = 0; i < data.length; i++) {

System.out.print(data[i]);

}

System.out.println();

}

public static void main(String[] args) {

int data[] = { 1, 2, 3, 2 };

// 先排序

Arrays.sort(data);

int count = 1;

print(data);

while (getNextPermutation(data)) {

count++;

print(data);

}

System.out.println("全排列一共有" + count + "个！");

}

}

运行结果：

1223

1232

1322

2123

2132

2213

2231

2312

2321

3122

3212

3221

全排列一共有12个！