【每天一道算法题】（C语言参考解法）给定参数n,从1到n会有n个整数1，2，3，...,n这n个数组共有n!种排列，按照大小顺序升序排列出所有列的情况，并一一标记，给定n和k返回第k个值_有一个数组,包含 1 到 n 这 n 个整数,初始为一个从小到大的有序排列: {1, 2, 3, 4

本题为某厂机试题（本人亲历，未答出T_T），

参考声明

本文涉及到的代码重点参考：https://blog.csdn.net/umbrellalalalala/article/details/79792451

重点考察：

             **全排列**
1

核心算法:

枚举法，C的具体实现——通过迭代的方式，循环调用。

代码

需要细细品，思路还得再理理，晚些时候有新的理解再写。直接贴代码：

#include <stdio.h>
#include <stdlib.h>

int cur = 0;
long int j = 0;
#define MAX  9
int a[MAX] = {0};
//#define MAX_CNT 9*8*7*6*5*4*3*2*1
//char array[MAX_CNT*9];
void list_all_array(int n, char *full_array, int cur)
{    	
    if(cur == n) 
    {
        //printf("arrar addr is 0x%x\n", full_array);
        for(int i = 0; i < n; i++)
        {
            sprintf(full_array + j + i, "%d", a[i]);
            printf("%c", full_array[j+i]);
        }
        j += n;
        printf("\n");
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            int ok = 1;
            for(int k = 0 ; k < cur; k++)
                if(a[k] == i)
                {
                   ok = 0;
                   break;
                }
            if(ok)
            {
                a[cur] = i;
                //printf("\t%s : j = %d\n\n", __func__, j);                         
                list_all_array(n, full_array, cur+1);
             }
        }
    }
}   


int main()
{    
    int n = 0;
    long int k = 0;
    long int k_value = 1;           
    int i = 0;
retry1:    
    printf("input n :");     
    scanf("%d", &n);
    if(n < 1 || n > 9)
    {        
        printf("please retry!\n");        
        goto retry1;    
    }
    for(i = n; i > 0; i--)
    {        
        k_value *= i;
    }
    printf("%d! is %ld\n", n, k_value);
retry2:
    printf("input k :");    
    scanf("%ld", &k);
    if(k < 1 || k > k_value)
    {    
        printf("please retry k!\n");    
        goto retry2;
    }
    char *array = (char *)malloc(sizeof(char) * k_value * n);
    list_all_array(n, array, 0);
    printf("result is :\n");
    for(int m = 0; m < n; m++)
    {
        printf("%c", array[(k - 1) * n + m] );
    }       
    printf("\n");
    free(array);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

代码2020.7.15更新：
考虑到list_all_array中用到的数组a[MAX]为全局变量，可不作为输入形参，故删去了void list_all_array(int n, char* mid_array, char *full_array, int cur)中的char* mid_array这一输入形参。
最本质的思想还是通过递归调用list_all_array函数实现全排列枚举。