全排列算法有两个比较常见的实现:递归排列和字典序排列。
(1)递归实现
从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。算法实现如下:
private static void perm(int nt,String[] permu) {
// TODO Auto-generated method stub
if(nt==n)
{
permu[t]="";
for(int i=1;i<=n;i++)
permu[t]=permu[t]+A[i];
t++;
return;
}
for(int i=nt;i<=n;i++)
{
int temp=A[nt];
A[nt]=A[i];
A[i]=temp;
perm(nt+1,permu);
temp=A[nt];
A[nt]=A[i];
A[i]=temp;
}
}
(2)字典序排列
把升序的排列(当然,也可以实现为降序)作为当前排列开始,然后依次计算当前排列的下一个字典序排列。对当前排列从后向前扫描,
找到一对为升序的相邻元素,记为i和j(i <
j)。如果不存在这样一对为升序的相邻元素,则所有排列均已找到,算法结束;否则,重新对当前排列从后向前扫描,找到第一个大于i的元素k,交换i和k,
然后对从j开始到结束的子序列反转,则此时得到的新排列就为下一个字典序排列。这种方式实现得到的所有排列是按字典序有序的,这也是C++
STL算法next_permutation的思想。算法实现如下:
private static void sortperm(int n, int count) {
// TODO Auto-generated method stub
while (true) {
int i;
for (i = n - 1; i >= 1; i--) {
if (A[i] < A[i + 1])
break;
}
int k;
for (k = n; k > i; k--) {
if (A[k] > A[i])
break;
}
int temp = A[i];
A[i] = A[k];
A[k] = temp;
reverse(i + 1);
t++;
if (t == count) {
for (int m = 1; m <= n; m++)
System.out.print(A[m]);
System.out.println();
break;
}
}
}
private static void reverse(int t) {
// TODO Auto-generated method stub
int i, j;
for (i = t, j = n; i < j; i++, j--) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
阅读(476) | 评论(0) | 转发(0) |