Module: Iterando sobre permutações


Problem

1 /4


Todas as permutações

Theory Click to read/hide

Uma permutação de comprimento n é uma coleção ordenada sem repetições dos números 1, 2, ..., n. Por exemplo, [3, 1, 2] e [5, 4, 3, 2, 1] são permutações, mas [1, 2, 1, 3] e [1, 2, 4] não são.

Se a tarefa for reduzida ao fato de que é necessário iterar sobre todas as permutações de comprimento n, então você pode usar um mecanismo conveniente em C ++, chamado "next_permutation".

Você pode ler mais sobre isso em documentação, mas o ponto é que esta função altera o array passado à permutação subseqüente na ordem lexicográfica (que geralmente é clara e seu nome).

Para usar next_permutation, você precisa incluir a biblioteca de algoritmos (ou seja, escreva #include <algorithm> no início do programa)

Exemplos: vetor arr; arr = { 1, 2, 3 }; // matriz é [1, 2, 3] next_permutation(arr.begin(), arr.end()); // passa todo o array para a função // array agora é [1, 3, 2] arr = { 2, 3, 1 }; // matriz é [2, 3, 1] next_permutation(arr.begin(), arr.end()); // passa todo o array para a função // array agora é [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // é possível aplicar uma função a uma parte de um array, mas na prática isso raramente é necessário // array agora é [3, 2, 1]
Neste caso, a função tem um valor de retorno booleano que é true se a próxima permutação foi gerada e false se não houve próxima (caso em que a permutação máxima em ordem lexicográfica é passada para a função).
Isso torna possível usar a função em um loop, o que nos permitirá iterar todas as permutações de uma só vez. Devido à indexação 0, na prática muitas vezes é mais conveniente trabalhar com uma permutação de números de 0 a n - 1, embora uma permutação contenha formalmente números de 1 a n. Mas, felizmente, isso não leva a sobreposições adicionais no código, porque a função next_permutation é adaptada para permutações indexadas a 0 (e até elementos duplicados em uma matriz, mas você pode descobrir mais por conta própria).

Em geral, o código para iterar todas as permutações se parece com isto:   int; // tamanho da permutação vetorperm(n); // perm é a abreviação de "permutação", ou seja, "permutação" para (int i = 0; i < n; i++) perm[i] = i; // inicializa a permutação inicial 0, 1, ..., n - 1 fazer { // dentro do loop processamos a permutação atual } while (next_permutation(perm.begin(), perm.end())); // se não houver próxima permutação, então finalize o loop

Esse código é executado em O(n! * f(n)), onde f(n) é o tempo que você leva para processar uma permutação específica.

Problem

Você recebe um número natural n. Imprima todas as permutações de tamanho n em ordem lexicográfica.

Entrada:
A primeira linha contém um número natural n (1 <= n <= 7).

Saída:
Imprima todas as permutações em ordem crescente na ordem lexicográfica. Cada um em uma linha separada. Os números na permutação devem ser separados por espaços.

Exemplo:
 
Entrada Saída
3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1