e446 - 排列生成

🔗 前往 ZeroJudge 原題

題目描述

題目要求生成從 1 到 N 的所有排列，並按照字典序輸出。輸入為一個正整數 N，輸出所有可能的排列，每個排列佔一行，數字之間用空格分隔。

解題思路

此題可以使用 std::next_permutation 函數直接生成排列。首先，建立一個包含從 1 到 N 的數字的陣列。然後，使用 std::next_permutation 函數迭代生成所有可能的排列，並將每個排列輸出。std::next_permutation 函數會修改陣列，使其成為下一個字典序的排列。如果不存在下一個排列，則返回 false，表示已經生成了所有排列。

複雜度分析

• 時間複雜度: O(N!)，因為需要生成 N! 個排列。
• 空間複雜度: O(N)，用於儲存包含 N 個元素的陣列。

程式碼

#include <iostream>  
#include <algorithm>   
int main(){  
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	int a;
	scanf("%d",&a);
	int b[a-1]={0};
    for(int i=0;i<a;i++)
    	b[i]=i+1;
    do{  
        for(int i=0;i<a;i++)
			printf("%d ",b[i]);
		printf("\n");
    }while(std::next_permutation(b,b+a));  
}