---
# System prepended metadata

title: 第K小的排列(Public)
tags: [計概詳解]

---

###### tags: `計概詳解`
# 第K小的排列(Public)
將 123456 的每個位數重新排列，可以得到 6!=7206!=720 個不同的數，其中最小的是 123456，最大的是 654321。現在輸入 K, (1≤K≤720)，請輸出第 K 小的數。

## 迴圈暴力解法
檢查123456~654321之間的每一個整數，如果這個數符合排列規定，cnt++。
當<code>(cnt == k)</code>時，印出答案，結束程式。
```c
int main()
{
    int k, cnt=0;
    scanf("%d", &k);
    for (int i=123456; i<=654321; i++){
        if (isPermu(i)){
            cnt++;
            if (cnt==k) {
                printf("%d", i);
                break;
            }
        }
    }
}
```
### 檢查排列的函數 int isPermu(int n)
用陣列 int a[7] 來紀錄1、2、3、4、5、6 出現幾次。
1. 取出n的個位數
2. 如果個位數不是1~6之間的數，return 0;
3. 如果個位數出現已經出現過， return 0;
4. 跑完迴圈表示n合格，return 1;

```c
int isPermu(int n)
{
    int d, a[7]={0};
    while(n){
        d = n%10;
        if (d<1 || d>6) return 0;
        if (a[d]) return 0;
        a[d]=1;
        n/=10;
    }
    return 1;
}
```

## 程式碼
```c=
#include <stdio.h>

int isPermu(int n);

int main()
{
    int k, cnt=0;
    scanf("%d", &k);
    for (int i=123456; i<=654321; i++){
        if (isPermu(i)){
            cnt++;
            if (cnt==k) {
                printf("%d", i);
                break;
            }
        }
    }
}

int isPermu(int n)
{
    int d, a[7]={0};
    while(n){
        d = n%10;
        if (d<1 || d>6) return 0;
        if (a[d]) return 0;
        a[d]=1;
        n/=10;
    }
    return 1;
}
```