首页 > 搜索 > 回溯和剪枝 > 回溯(1)-字符串的全排列
2014
03-28

回溯(1)-字符串的全排列

全排列的概念:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

例如对于字符串ABC的全排列:
ABC, ACB, BAC, BCA, CAB, CBA

NewPermutation

下面是使用回溯的解决办法,也就是常用的递归

# include <stdio.h>
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* 打印字符串的全排列*/
void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //回溯
       }
   }
} 

/* 测试 */
int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

输出:

ABC
ACB
BAC
BCA
CBA
CAB

这个递归的写法虽然简单,但是输出的结果顺序不正确,因为在交换的交换的时候并没有考虑顺序问题。

还有两个常用的算法就是 康拓展开式 ,参考:康拓展开和逆康拓展开的应用  和 一个非递归的模拟算法。

下面介绍非递归的算法,先交换,再把后面的数组逆置就行了。具体解释可以看我下面的Java代码:

public class 全排列 {

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

	//修改arr为下一个排列, 返回是否还有下一个全排列
	static boolean next_permutation(int[] arr)
	{
		int n = arr.length; //有个元素
		int k = n-1;

		int cnt = 0;
		while( k > 0 && arr[k--] < arr[k]){ //找到第一个 递增的序列k
			cnt++;
		}
		if(cnt == n-1)
			return false;

		int minIndex = n-1;
		int min = Integer.MAX_VALUE;
		//找到第一个比 arr[k] 大的 minIndex
		for(int j=n-1; j>= k+1; j-- ){
			if( arr[j] > arr[k] && min > arr[j] ){
				min = arr[j];
				minIndex = j;
			}
		}

		swap(arr, k, minIndex); //交换。 

		//由于后面的是逆序的。 重新排成正需。 两两交换即可
		for(int i=0; i<(n-k)/2; i++){
			swap(arr, k+i+1, n-1-i);
		}
		return true;

	}

	public static void print_arr(int[] arr){
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i]);
		System.out.println();
	}

	static int[] arr = {1,2,3,4};

	public static void main(String[] args) {
		print_arr(arr);
		while(next_permutation(arr)){
			print_arr(arr);
		}
	}

}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。