Permutations This article demonstrates a method for generating all permutations of a set of numbers using depth-first search (DFS).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100010;

int size, sequence[MAX_SIZE];
bool visited[MAX_SIZE];

void generatePermutations(int position) {
    if (position > size) {
        for (int i = 1; i <= size; i++) {
            cout << sequence[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= size; i++) {
        if (!visited[i]) {
            visited[i] = true;
            sequence[position] = i;
            generatePermutations(position + 1);
            visited[i] = false;
            sequence[position] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> size;
    generatePermutations(1);
    return 0;
}

This DFS approahc provides an alternative to built-in permutation functions like next_permutation, offering more control over the generation process.

The method can be applied to problems like P1088 [NOIP2004 Popularization Group] Martian - Luogu.

It's also possible to generate permutations starting from a given initial order:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100010, MAX_M = 20;

int size, target, mars[MAX_SIZE], result;
bool stop, visited[MAX_SIZE];
int sequence[MAX_SIZE];

void generatePermutations(int position) {
    if (stop) return;
    
    if (position > size) {
        result++;
        if (result == target + 1) {
            stop = true;
            for (int i = 1; i <= size; i++) {
                cout << sequence[i] << " ";
            }
        }
        return;
    }
    
    for (int i = 1; i <= size; i++) {
        if (!result) {
            i = mars[position]; // Start from given order
        }
        
        if (!visited[i]) {
            visited[i] = true;
            sequence[position] = i;
            generatePermutations(position + 1);
            sequence[position] = 0;
            visited[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> size >> target;
    for (int i = 1; i <= size; i++) {
        cin >> mars[i];
    }
    
    generatePermutations(1);
    return 0;
}

Combinations

For combinations, we can use a similar DFS approach with a constraint on the selection range:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100010, MAX_M = 20;

int total, select, combination[MAX_SIZE];
bool stop, visited[MAX_SIZE];

void generateCombinations(int position, int start) {
    if (position > select) {
        for (int i = 1; i <= select; i++) {
            cout << combination[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = start; i <= total; i++) {
        if (!visited[i]) {
            visited[i] = true;
            combination[position] = i;
            generateCombinations(position + 1, i + 1);
            visited[i] = false;
            combination[position] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> total >> select;
    generateCombinations(1, 1);
    return 0;
}

This combintaion generation method can be applied to problems like P1157 Combination Output - Luogu.