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.
|