Enumerating Gene Orders

Rearrangements Power Large-Scale Genomic Changes

Point mutations can create changes in populations of organisms from the same species, but they lack the power to create and differentiate entire species. This more arduous work is left to larger mutations called genome rearrangements, which move around huge blocks of DNA. Rearrangements cause major genomic change, and most rearrangements are fatal or seriously damaging to the mutated cell and its descendants (many cancers derive from rearrangements). For this reason, rearrangements that come to influence the genome of an entire species are very rare.
Because rearrangements that affect species evolution occur infrequently, two closely related species will have very similar genomes. Thus, to simplify comparison of two such genomes, researchers first identify similar intervals of DNA from the species, called synteny blocks; over time, rearrangements have created these synteny blocks and heaved them around across the two genomes (often separating blocks onto different chromosomes, see Figure 1.).	Figure 1. Similar regions in mouse and human chromosomes. Image credit: U.S. Department of Energy Human Genome Program
A pair of synteny blocks from two different species are not strictly identical (they are separated by the action of point mutations or very small rearrangements), but for the sake of studying large-scale rearrangements, we consider them to be equivalent. As a result, we can label each synteny block with a positive integer; when comparing two species’ genomes/chromosomes, we then only need to specify the order of its numbered synteny blocks.

Problem

A permutation of length nn is an ordering of the positive integers {1,2,…,n}{1,2,…,n}. For example, π=(5,3,2,1,4)π=(5,3,2,1,4) is a permutation of length 55.
Given: A positive integer n≤7n≤7.
Return: The total number of permutations of length nn, followed by a list of all such permutations (in any order).
Sample Dataset
3
Sample Output
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
语雀内容
参考代码：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    void backtrace(int idx, vector<int> &nums, vector<vector<int>> &res) {
        // 使用交换法进行枚举全排列
        if (idx == nums.size()) res.push_back(nums);
        for (int i = idx; i < nums.size(); ++i) {
            swap(nums[i], nums[idx]);  // 选择 [idx,n) 当当前第一个
            backtrace(idx + 1, nums, res);
            swap(nums[i], nums[idx]);  // 撤销选择
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        backtrace(0, nums, res);
        return res;
    }
};
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) nums[i] = i + 1;
    vector<vector<int>> res = Solution().permute(nums);
    cout << res.size() << endl;
    for (vector<int> &vec: res) {
        for (int num: vec) cout << num << " ";
        cout << endl;
    }
    return 0;
}