AcWing 842. 排列數字

題目描述

給定一個整數 𝑛，將數字 1～𝑛 排成一排，將會有很多種排列方法。

現在，請你按照字典序將所有的排列方法輸出。

輸入格式

共一行，包含一個整數 𝑛。

輸出格式

按字典序輸出所有排列方案，每個方案占一行。

數據范圍

1≤𝑛≤7

輸入樣例：

3

輸出樣例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

C++

#include <iostream>using namespace std;const int N = 10;
int n, path[N];
bool st[N]; // 狀態數組void dfs(int u) {if (u == n)// 遞歸到最后一個數字{for (int i = 0; i < n; i++) printf("%d ", path[i]); // 輸出保存的結果puts(" ");}for (int i = 1; i <= n; i++)if (!st[i]) // 沒有被用過的數{path[u] = i;st[i] = true; // i被用過dfs(u + 1);// 走到下一層st[i] = false;// 恢復現場}
}int main() {scanf("%d", &n);dfs(0);return 0;
}

#include <iostream>using namespace std;const int N = 10;int n;
int path[N];void dfs(int u, int state) {if (u == n) {for (int i = 0; i < n; i++) printf("%d ", path[i]);puts("");return;}for (int i = 0; i < n; i++)if (!(state >> i & 1)) {path[u] = i + 1;dfs(u + 1, state + (1 << i));}
}int main() {scanf("%d", &n);dfs(0, 0);return 0;
}

state變量通過位運算來跟蹤哪些數字已經被使用過。我們可以通過一個簡單的例子來詳細說明這一過程：

假設我們要找出 1 到 3 的所有排列。

初始化

• state初始化為 0（二進制表示為000），表示沒有任何數字被使用。

第一層遞歸

我們從數字 1 開始嘗試，直到數字 3。

• 嘗試數字 1:
  • 檢查數字 1 是否已使用：state >> 0 & 1 （即000 >> 0 & 1）結果為 0，表示數字 1 未使用。
  • 更新state：state + (1 << 0)（即000 + 001），現state變為001，表示數字 1 已使用。
  • 進入下一層遞歸。

第二層遞歸

此時，state為001，表示數字 1 已被使用。

• 嘗試數字 1:
  • 檢查數字 1 是否已使用：state >> 0 & 1 （即001 >> 0 & 1）結果為 1，跳過。
• 嘗試數字 2:
  • 檢查數字 2 是否已使用：state >> 1 & 1 （即001 >> 1 & 1）結果為 0，表示數字 2 未使用。
  • 更新state：state + (1 << 1)（即001 + 010），現state變為011，表示數字 1 和 2 已使用。
  • 進入下一層遞歸。

第三層遞歸

此時，state為011。

• 嘗試數字 1:
  • 檢查數字 1 是否已使用：state >> 0 & 1 （即011 >> 0 & 1）結果為 1，跳過。
• 嘗試數字 2:
  • 檢查數字 2 是否已使用：state >> 1 & 1 （即011 >> 1 & 1）結果為 1，跳過。
• 嘗試數字 3:
  • 檢查數字 3 是否已使用：state >> 2 & 1 （即011 >> 2 & 1）結果為 0，表示數字 3 未使用。
  • 更新state：state + (1 << 2)（即011 + 100），現state變為111，表示數字 1、2 和 3 已使用。
  • 找到排列：1 2 3。

回溯

完成當前分支后，遞歸函數將結束當前層的執行并返回上一層，同時state的值也會恢復到進入當前層之前的狀態（通過局部變量的作用域自然實現），這樣就可以繼續嘗試其他的數字組合。

Go

package mainimport ("bufio""fmt""os"
)const N = 10var (n      intpath   [N]intst     [N]boolwriter = bufio.NewWriter(os.Stdout)
)func dfs(u int) {if u == n {for i := 0; i < n; i++ {writer.WriteString(fmt.Sprintf("%d ", path[i]))}writer.WriteString("\n")return}for i := 1; i <= n; i++ {if !st[i] {path[u] = ist[i] = truedfs(u + 1)st[i] = false}}
}func main() {defer writer.Flush()reader := bufio.NewReader(os.Stdin)fmt.Fscan(reader, &n)dfs(0)
}

package mainimport ("bufio""fmt""os"
)const N = 10var (n      intpath   [N]intwriter = bufio.NewWriter(os.Stdout)
)func dfs(u int, state int) {if u == n {for i := 0; i < n; i++ {writer.WriteString(fmt.Sprintf("%d ", path[i]))}writer.WriteString("\n")return}for i := 0; i < n; i++ {if (state>>i)&1 == 0 {path[u] = i + 1dfs(u+1, state|(1<<i))}}
}func main() {defer writer.Flush()reader := bufio.NewReader(os.Stdin)fmt.Fscan(reader, &n)dfs(0, 0)
}