public static void main(String[] args) throws Exception {
int arr[] = { 1, 2, 3 }
for (int i = 0 i < 3 i++)
System.out.print(arr[i])
System.out.println()
// 开始循环调用字典序算法,直至全排列排列完毕
// 返回false代表排列完毕,返回true代表仍有未排列完的数
while (fullSort(arr, 3))
}
final static boolean fullSort(int arr[], int n) {
int i = 0, j = 0, k = -1, l, temp
for (i = 0 i < n - 1 i++) { // 找最后的升序的位置
if (arr[i] < arr[i + 1])
k = i
}
if (k >= 0) {
l = -1
for (i = 0 i < n i++) { // 找到最后一个升序且是最大的数的下标
if (arr[k] < arr[i])
l = i
}
temp = arr[k]
arr[k] = arr[l]
arr[l] = temp
for (i = k + 1 i < n i++)// 将k+1的元素与末尾对调
{
j = n - i + k
if (i >= j)
break
{
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
if (k == -1)
return false
for (i = 0 i < n i++)
System.out.print(arr[i])
System.out.println()
return true
}
不要急于看代码,你心理要知道全排列的思路,不注重思路是很多程序员易犯的错误。全排列算法:
如果我求得固定第一位后的排列,那么全部排列就可以求出,固定第一位有10种可能,可以循环求得。
如果我求得固定第二位后的排列,固定第一位后的排列就可以求出,固定第二位有9种可能,可以循环求得。
。。。
如果我求得固定第10位后的排列,固定第9位后的排列就可以求出,固定第10位有1种可能,可以循环求得。
这很明显是递归的算法。
static void dfs(int start,int end,int num){//为全部排列的集合,start为数字的位置,end为最后一位,num多余的
if(start==end){//当前的数字位置为最后一位时,说明,一个序列已经生成
for(int i=1i<endi++)
System.out.print(a[i]+" ")//输出序列
System.out.println()
}
else{//序列没有生成时
for(int i=1i<endi++){
if(vis[i])//i是否在前面使用过
continue//如果是直接跳过
a[start]=i//确定start位置的数字,当start为1时就是确定第一位,有10种可能
vis[i]=true//设置i为已使用状态,避免下一位使用i
dfs(start+1,end,num)//求得确定start位后的全部序列
vis[i]=false//设置i为未使用状态
}
}
尽量用递归好理解一些,打个断点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)
}
}