精华内容
下载资源
问答
  • 递归输出全排列的一种新方法(C语言描述...输出1到n的全排列。每种排列占一行,数字间无空格。排列的输出顺序为字典序。 输入样例: 3 输出样例: 123 132 213 231 312 321 在网上搜索了一下,网上的思路要么很复杂,要

    递归输出全排列的一种新方法(C语言描述)

    本文同时也发表在我的个人网站:www.wendev.site,欢迎前往我的个人网站阅读。

    前言

    最近在数据结构的作业题中,出现了这样一道题目:

    7-2 输出全排列 (20 分)

    请编写程序输出前n个正整数的全排列(n<10),并通过9个测试用例(即n从1到9)观察n逐步增大时程序的运行时间。

    输入格式:

    输入给出正整数n(n<10)。

    输出格式:

    输出1到n的全排列。每种排列占一行,数字间无空格。排列的输出顺序为字典序。

    输入样例:

    3
    

    输出样例:

    123
    132
    213
    231
    312
    321
    

    在网上搜索了一下,网上的思路要么很复杂,要么不能得出正确结果,要么没有使用递归。

    经过一番思考后,我发现了一种新方法。

    先给出此种方法的优缺点,以供参考:

    • 优点:代码极短,核心代码的长度仅有13行,容易阅读与理解。
    • 缺点:存在费时费力的操作,整个算法的时间复杂度较高,执行过程麻烦。

    注意:这种方法虽然在本地可以成功运行并正确输出,但并未在PTA平台上进行试验,不一定可以AC。

    思路

    如何将问题转化为递归

    输出全排列实际上可以看做一个递归问题。
    假设有一个由0~n组成的数组arr,其元素为0, 1, 2, ... , n。那么这个数组本身其实就是全排列的第一项。
    如果要得到全排列的第二项,就需要把第n个元素和第n - 1个元素进行互换,并在互换后输出。
    如果要得到第三项,就要先得到第n - 2n - 1n项的全排列。
    ……以此类推,得到n个数的全排列就可以归结为得到n - 1个数的全排列,最终归结为得到2个数的全排列。而得到2个数的全排列的方法就是:先将两个数输出,再将两个数交换后输出。

    这很显然可以用递归来求解,因为问题规模是逐渐减小的,最终总能减小到一个特定的情况(递归边界),而且后一次的问题规模严格小于前一次,这也是递归类问题的典型思路。

    如何减小问题规模

    前面提到了,需要让问题的规模逐渐减小。这里我们以输出4的全排列为例,来谈谈如何逐步减小问题规模,以及如何用代码来描述这个过程。

    按字典序输出4的全排列,应该为:

    1234
    1243
    1324
    1342
    1423
    1432
    2134
    2143
    2314
    2341
    2413
    2431
    3124
    3142
    3214
    3241
    3412
    3421
    4123
    4132
    4213
    4231
    4312
    4321
    

    从中我们不难看出如下规律:

    • 1~4轮流出现在排列的首位
    • 排列的第二位从小到大,由1~4中除了首位的数轮流出现
    • 排列的第三位和第四位相当于对两个数进行交换输出(递归边界)

    所以我们可以用以下方法逐步减小这个问题的规模:

    1. 循环扫描一个由1~n组成的数组(计数变量为i),每次把第i个数放入数组的最前面,并保证其他元素的位置相对不变(如:1234=>3124
    2. i + 1~n的部分进行递归,在递归中再次扫描这个数组,仍然进行上述变换(如3124=>3214
    3. i + 1 == n时只剩两个数,达到递归边界,输出这个数组
    4. 交换最后两个数的位置,再输出一次,再交换回来
    5. 递归结束,返回上一层递归,将变动过的数字放回去(3214=>31243124=>1234
    6. 扫描完从1~n的部分后,全排列输出完成,问题解决

    伪代码如下:

    void Perm(int ground, int sky) {
        if (ground + 1 == sky) {
            输出数组
            交换最后两数
            输出数组
            交换最后两数
        } else {
            for (int i = ground; i <= sky; i++) {
                    对数组进行变换
                    Perm(ground + 1, sky);
                    将变换后的数组还原
            } // for
        } // if
    } // Perm
    

    因为这个数组要一直被使用、一直被变换,所以可以定义成全局变量。

    完整代码

    完整代码如下,如果gcc编译不通过可以把对循环变量的初始化放在for括号的外面:

    #include <stdio.h>
    
    
    int arr[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    
    void Perm(int, int);
    void Swap(int*, int*);
    void PrintArr(int);
    void GetArr(int, int);
    void BackArr(int, int);
    
    
    int main() {
        int n;
    
        scanf("%d", &n);
        Perm(1, n);
    
        return 0;
    } // main
    
    
    /**
     * 本程序的核心函数:递归函数Perm()
     *
     * @param ground 要处理的数组元素下标的下界
     * @param sky    要处理的数组元素下标的上界
     */
    void Perm(int ground, int sky) {
        if (ground + 1 == sky) {    // 递归边界,将最后两数先输出,再交换后输出,得到一组解
            PrintArr(sky);
            Swap(&arr[ground], &arr[sky]);
            PrintArr(sky);
            Swap(&arr[ground], &arr[sky]);
        } else {                    // 其他情况,遍历、变换数组,并继续递归求解
            for (int i = ground; i <= sky; i++) {
                GetArr(i, ground);
                Perm(ground + 1, sky);  // 递归
                BackArr(ground, i);
            }
        }
    } // Perm
    
    
    // 利用地址交换两个元素的值
    void Swap(int* x, int* y) {
        int temp;
        temp = *x;
        *x = *y;
        *y = temp;
    } // Swap
    
    
    void PrintArr(int pos) {
        for (int i = 1; i <= pos; i++) {
            printf("%d", arr[i]);
        }
        putchar('\n');
    } // PrintArr
    
    
    // 对数组进行变换:把位置为nowPos的元素放到targetPos上
    void GetArr(int nowPos, int targetPos) {    // nowPos > targetPos
        int elem = arr[nowPos];
        for (int i = nowPos; i >= targetPos; i--) {
            arr[i] = arr[i - 1];
        }
        arr[targetPos] = elem;
    } // GetArr
    
    
    // 将变换后的数组还原:把位置为nowPos的元素放回targetPos
    void BackArr(int nowPos, int targetPos) {   // targetPos > nowPos
        int elem = arr[nowPos];
        for (int i = nowPos; i < targetPos; i++) {
            arr[i] = arr[i + 1];
        }
        arr[targetPos] = elem;
    } // BackArr
    
    
    展开全文
  • c语言 全排列

    2018-11-29 20:40:15
    输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 输入格式: n(1≤n≤9) 输出格式: 由1~n组成的所有不重复的数字序列,每行一个序列。每个数字保留5个常宽。 ...

    题目描述
    输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

    输入格式:
    n(1≤n≤9)

    输出格式:
    由1~n组成的所有不重复的数字序列,每行一个序列。每个数字保留5个常宽。

    输入样例#1:
    3
    输出样例#1:
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

    #include <stdio.h> 
    #define MAX 1000000 
    int first[MAX]; 
    int last[MAX]; 
    int N; 
     
    void print()
        { 
            int i; 
            for(i = 0; i < N-1; i++){
            printf("%d ", last[i]); 
        }
            printf("%d", last[i]);
            printf("\n"); 
        } 
    void cal(int step)
        { 
            int i; 
            if(step == N) 
            print(); 
            else
                { 
                    for(i = 0; i < N; i++)
                        { 
                            if(!first[i])
                                { 
                                    first[i] = 1; 
                                    last[step] = i + 1; 
                                    cal(step + 1); 
                                    first[i] = 0; 
                                } 
                        } 
                } 
    } 
     
    int main()
        { 
            scanf("%d", &N); 
            cal(0); 
        } 
    
    展开全文
  • C语言 全排列的实现

    千次阅读 2018-04-08 20:08:50
    -----------------------------------------------------------------------------------------------------------------请编写程序输出n个正整数的全排列n&lt;10),并通过9个测试用例(即n1到...
    首先是一维数组的全排列,半个多月前在PAT上做了一个题,深有体会,可以深入理解递归这东西。

    -----------------------------------------------------------------------------------------------------------------

    请编写程序输出前n个正整数的全排列(n<10),并通过9个测试用例(即n从1到9)观察n逐步增大时程序的运行时间。

    输入格式:

    输入给出正整数n<10)。

    输出格式:

    输出1到n的全排列。每种排列占一行,数字间无空格。排列的输出顺序为字典序,即序列a1,a2,,an排在序列b1,b2,,bn之前,如果存在k使得a1=b1,,ak=bk 并且 ak+1<bk+1

    输入样例:

    3
    

    输出样例:

    123
    132
    213
    231
    312
    321

    以下代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    //指针变量相当于一个新的变量,在函数中必须建一个指针变量指向这个指针变量才能改变这个变量的值
    
    
    void Print(int*a, int n) {
    	for (int i = 1; i <= n; i++) {
    		if (i == n)	printf("%d\n", a[i]);
    		else printf("%d ", a[i]);
    	}
    }
    void perm(int*a, int*b,int n,int Index) {
    	if (Index== n+1) {
    		static int cnt = 0;
    		printf("第%03d次排序为:", ++cnt);
    		Print(a, n);
    		return;
    	}
    	for (int i = 1; i <= n; i++) {
    		if (!b[i]) {
    			a[Index] = i;
    			b[i] = 1;
    			perm(a, b, n, Index + 1);
    			b[i] = 0;
    		}
    	}
    	return;
    }
    int main() {
    	int n;
    	int a[51], b[51] = { 0 };
    	printf("输入n:\n");
    	//可最大计算出50个数的全排列
    	//其中a是输出数列,b是索引数列,它的索引用来锁定和输入a的数值
    	scanf("%d", &n);
    	//输入n来全排列1~n的数组
    	perm(a, b, n, 1);
    	return 0;
    }

    通过数组b的0,1值和递归来对数组a进行全排列的赋值

    --------------------------------------------------------------------------------------------------------------------------

    接下来是字符的全排列
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    //全排列字符数组
    void permChar(char*a,int start) {
    	int i;
    	static int cnt = 0;
    	if (!a[start]) {
    		printf("第%d次排序:", ++cnt);
    		for (i = 0; i < start; i++) {
    			printf("%c", a[i]);
    		}
    		printf("\n");
    	}
    	for (i=start; a[i]; i++) {
    		char temp = a[i];
    		a[i] = a[start];
    		a[start] = temp;
    		permChar(a, start+ 1);
    		temp = a[i];
    		a[i] = a[start];
    		a[start] = temp;
    	}
    }
    int main() {
    	char a[50] = "Miku";
    	permChar(a, 0);
    	return 0;
    }

    通过start索引上的字符是否为'\0'来进行判定。

    --------------------------------------------------------------------------------------------------------------------

    字符串数组的全排列:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    //字符串二维数组的全排列(多维数组排列可据此叠加)
    void swap1(char**a, char**b) {
    	char*temp = *a;
    	*a = *b;
    	*b = temp;
    }
    void swap2(char*a[],char*b[],int len) {
    	for (int i = 0; i < len; i++) {
    		swap1(a + i, b + i);
    	}
    }//只是让其内部的字符串指针产生改变
    //并不是取字符串数组的指针来改变字符串数组的位置
    void permStr(char*a[][4], int length,int len,int start) {
    	static int cnt;
    	if (start == length) {
    		printf("\n第%d次排序:\n",++cnt);
    		for (int i = 0; i < length; i++) {
    			for (int j = 0; j < len; j++) {
    				printf("%s ", a[i][j]);
    			}
    			printf("\n");
    		}
    	}
    	for (int i = start; i < length; i++) {
    		swap2(a[start], a[i],len);
    		permStr(a, length, len, start + 1);
    		swap2(a[start], a[i], len);
    	}
    }
    int main() {
    	char*str[][4] = {
    		{"C","Y","F","E"},
    		{"cherish","you","for","ever"},
    		{"crying","yet","for","everything"}
    	};
    	int length = 3;
    	permStr(str, length, 4, 0);
    }

    当时试想着实现的,其实全排列模板都一样,就是二维数组在全排列的交换函数有所区别。

    有利于对指针更深层次的理解:指针变量在这里相当于一个新的变量,在函数中必须建一个指针变量指向这个指针变量才能改变这个变量的值

    展开全文
  • C语言全排列

    千次阅读 2018-06-02 09:40:24
    输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 Input 包含多组测试数据,每组测试数据包含一个正整数n(1≤n≤9)。 Output 由1~n组成的所有不重复的数字序列,每...

    全排列问题
    Description
    输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
    Input
    包含多组测试数据,每组测试数据包含一个正整数n(1≤n≤9)。
    Output
    由1~n组成的所有不重复的数字序列,每行一个序列。
    Sample Input
    3
    Sample Output
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

     

     

    思路:建立函数时传一个n用来进行计算其循环到次数,即全排已经排好的或者说还可以排的次数;
    然后每次循环从1到n找,但要有一个标记数组用来标记哪一个是已经被选中了,如果没有选中说明可以继续选,选中过了的,则跳过去找其他的,每次选中的都存到一个数组中,如果之后直接输出这个数组(这个方法告诉我们了,对于输出一个序列的问题时,如果其中序列的元素不是同时得到的时候,则可以通过存入到一个数组中,然后输出数组的操作);别忘了,每次结束一个序列的输出后,再依次退出递归的时候要紧接着将上一个使用的数值给再标记为没有被选中;这样才能进行其他的;
     
    #include<stdio.h>
    #include<string.h>
    void dfs(int );
    int queue_number[10];
    int tag[9]={0};
    int n;
    int main()
    {
        while(scanf("%d",&n)!=EOF){
            dfs(n);
        }
        return 0;
    }
    
    void dfs(int t)
    {
        if(t==0)
        {
            for(int i=0;i<n;++i){
                printf("%d",queue_number[i]);
                if(i!=n-1)  printf(" ");
                else printf("\n");
            }
            return;
        }
        for(int i=1;i<=n;++i){
            if(tag[i]==0){
                queue_number[n-t]=i;
                tag[i]=1;
                dfs(t-1);//递归是这个表示的是还可以选中的数的个数
                tag[i]=0;
            }
        }
    }

     

    展开全文
  • 全排列C语言

    千次阅读 多人点赞 2018-06-23 17:48:36
    输入一个数n,输出1-n的全排列,这里我们将其形象化,举个例子,加入有编号1、2、3的3张扑克牌分别放在3个盒子里面,并且每个盒子有且只能放一张扑克牌。那么一共有多少种放法呢? 好,第一步:小张手拿三张扑克牌...
  • ** 7-2 输出全排列 (20 分) ...输出1到n的全排列。每种排列占一行,数字间无空格。排列的输出顺序为字典序,即序列a​1​​,a​2​​,⋯,a​n​​排在序列b​1​​,b​2​​,⋯,b​n​​之前,如...
  • C语言递归实现全排列

    千次阅读 2016-12-06 20:57:56
    全排列:从m个数据中取出n个数据,输出其全部组合可能性 例如:ABC中取出2个数据,输出其全部可能性 AB AC BA BC CA CB 我们将ABC进行编号,并且存放一个名为used[]数组中去,在开始时将其赋值为0表示...
  • 全排列c语言

    2019-12-04 11:05:06
    输入一个数字n,输出1到n的所有排列方式。 准备 设置n+1个盒子(box),第1个盒子置于第1步,第2个盒子置第2步... ... 设置n张扑克牌(poker),上面分别记有数字1到n。 举例 假设求3张牌放入3个盒子的所有排列方式。...
  • C语言作业|全排列(升序)

    千次阅读 2017-04-09 19:26:59
    Description 输入一个整数 n(1 Input 3 ...输出的顺序按第一个数从小大排列,若第一个数相同,则按第二个数排列,以此类推。使用递归 #include int n; int ary[9]; void swapAry(int x
  • 按照从小顺序输出所有方案,每行1个。 首先,同一行相邻两个数用一个空格隔开。 其次,对于两个不同行,对应下标数一一比较,字典序较小排在前面。 数据范围 1n≤9 输入样例: 3 输出样例...
  • 全排列问题之递归调用(C语言) 题目如下: 给一个数字n,求1到n之间的...对于每个n,输出1到n的全排列 按字典序输出全排列 每个排列一行 相邻两个数字之间隔一个空格 Sample Input: 3 Sa...
  •  下面的一个小实例实现了输入一个09的数n,输出这个数的从1-n的所有全排序结果。它体现了深度优先搜索的设计思想和实现方法。  好了,下面附上C语言实现的代码:   #include "stdio.h" /** * ...
  • n 的全排列。 思路分析   这里我们先将这个问题形象化, 举个例子,假如有编号为1 、2、3 的3 张扑克牌和编号为1 、2、3 的3 个盒子。现在需要将这3 张扑克牌分别放3 个盒子里面, 并且每个盒子有且只能放一张...
  • 输出自然数 1 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。 样例输入: 3 样例输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 先上代码: C语言描述带回溯DFS #include&...
  • 全排列问题(1到n的排列组合)2.八皇后问题求解二维迷宫(1)只输走出迷宫解的个数(2)输出解的个数和路径 0.闲话 ​ 才学习数据结构的dfs,做一下笔记记录一下,加深理解-.- ​ 我这里就简单讲一下我的理解和一下...
  • 全排列问题(1到n的排列组合)2.八皇后问题求解3.二维迷宫(1)只输走出迷宫解的个数(2)输出解的个数和路径0.闲话​ 才学习数据结构的dfs,做一下笔记记录一下,加深理解-.-​ 我这里就简单讲一下我的理解和一下例子​ ...
  • 多样排列

    2020-04-15 15:29:19
    在高中数学中,我们经常接触排列问题——给定n个不重复的数,从中挑出m个进行排列(等价于给定m个数位,每个数位可以从n个数中选1个,且不能与其他数位的数相同) 当n=m时,即为线性代数中所提到的全排列问题 ...
  • 1~N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是: 如果区间[L, R] 里的所有元素(即此排列的第L个第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间。 当N很...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

c语言输出1到n的全排列

c语言 订阅