数字排列

06 Sep 2024 in Algorithm Pageviews

blabla

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

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

数据范围

1 ≤ n ≤ 7

输入样例

3

输出样例

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

实现如下:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void dfs(vector<int> nums, int left, int right)
    {
        if (left == right) {
            res.emplace_back(nums);
        }
        
        for (int i = left; i <= right; i++) {
            swap(nums[left], nums[i]); // 可以直接交换
            dfs(nums, left + 1, right);
        }
    }

    vector<vector<int>> permulate(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        dfs(nums, 0, nums.size() - 1);
        return res;
    }

    vector<vector<int>> res;
};

int main()
{
    int n = 0;
    cin >> n;
    vector<int> nums(n);
    std::generate(nums.begin(), nums.end(), [i = 1]() mutable {return i++;});

    Solution sol;
    vector<vector<int>> ans = sol.permulate(nums);
    [&]() {
        for (const auto &v : ans) {
            for (const auto &t : v) {
                cout << t << " ";
            }
            cout << endl;
        }
    }();
    return 0;
}