public class Permutation {
public static void permulation(int[] list, int start, int length) {
int i
if (start == length) {
for (i = 0i <lengthi++)
System.out.print(list[i] + " ")
System.out.println()
} else {
for (i = starti <lengthi++) {
swap(list, start, i)
permulation(list, start + 1, length)
swap(list, start, i)
}
}
}
public static void swap(int[] list, int start, int i) {
int temp
temp = list[start]
list[start] = list[i]
list[i] = temp
}
public static void main(String[] args) {
int length = 3
int start = 0
int list[] = new int[length]
for (int j = 0j <lengthj++)
list[j] = j + 1
permulation(list, start, length)
}
}
思路:先有一个起始排列，如1234.从后面扫描，直到找到a[k],a[k]<a[k+1]再从后面扫描，直到找到a[j],这里有 a[k]<a[j]。交换a[k],a[j].再把a[k+1],...a[n-1]排序（从小到大），即得到了一个排列，再循环下去，直到找出所有的排序。用C语言的，参考下: http://user.qzone.qq.com/646203846/infocenter?ptlang=2052程序如下所示，输入格式为：
53 1 2 1 2
第一行是数字个数，第二行有n个数，表示待排列的数，输入假设待排序的数均为非负数。
import java.io.File
import java.io.FileNotFoundException
import java.util.Arrays
import java.util.Scanner
public class Main {
static final int maxn = 1000
int n // 数组元素个数
int[] a // 数组
boolean[] used // 递归过程中用到的辅助变量，used[i]表示第i个元素是否已使用
int[] cur // 保存当前的排列数
// 递归打印无重复全排列，当前打印到第idx位
void print_comb(int idx) {
if(idx == n) { // idx == n时，表示可以将cur输出
for(int i = 0 i < n ++i) {
if(i > 0) System.out.print(" ")
System.out.print(cur[i])
}
System.out.println()
}
int last = -1 // 因为要求无重复，所以last表示上一次搜索的值
for(int i = 0 i < n ++i) {
if(used[i]) continue
if(last == -1 || a[i] != last) { // 不重复且未使用才递归下去
last = a[i]
cur[idx] = a[i]
// 回溯法
used[i] = true
print_comb(idx + 1)
used[i] = false
}
}
}
public void go() throws FileNotFoundException
{
Scanner in = new Scanner(new File("data.in"))
// 读取数据并排序
n = in.nextInt()
a = new int[n]
for(int i = 0 i < n ++i) a[i] = in.nextInt()
Arrays.sort(a)
// 初始化辅助变量并开始无重复全排列
cur = new int[n]
used = new boolean[n]
for(int i = 0 i < n ++i) used[i] = false
print_comb(0)
in.close()
}
public static void main(String[] args) throws FileNotFoundException{
new Main().go()
}
}
客观来说，非递归的无重复全排列比较简单且高效。
![[C语言]cpp后缀的文件用c运行不了](/aiimages/%5BC%E8%AF%AD%E8%A8%80%5Dcpp%E5%90%8E%E7%BC%80%E7%9A%84%E6%96%87%E4%BB%B6%E7%94%A8c%E8%BF%90%E8%A1%8C%E4%B8%8D%E4%BA%86.png)
