Dada una string str , la tarea es generar todas las permutaciones distintas de la string dada de forma iterativa.
Ejemplos:
Entrada: str = “bba”
Salida:
abb
bab
bbaEntrada: str = “abc”
Salida:
abc
acb
bac
bca
cab
cba
Enfoque: El número de permutaciones para una string de longitud n es n!. El siguiente algoritmo también se puede extender a arrays de objetos arbitrarios. Aquí solo se cubre el caso de generar permutaciones de strings.
El algoritmo los genera de forma iterativa y es el siguiente:
Seguiremos los pasos utilizando la string de entrada de ejemplo «abca».
El primer paso del algoritmo asigna cada letra a un número y almacena el número de ocurrencias de cada letra. Para eso, primero se ordena la string.
String de entrada modificada: «aabc»
Ahora las letras se mapearían de la siguiente manera:
(first: mapped Number, second: Count) a : 0, 2 b : 1, 1 c : 2, 0
La base del sistema numérico que usamos sería 3 (igual al número de caracteres distintos en la string de entrada).
Ahora, una array contendría los valores asignados de cada letra. La idea básica es incrementar la array como un número combinado en el sistema numérico con una base igual al número de caracteres distintos.
Entonces, inicialmente, la array sería [0, 0, 1, 2]
Agregamos 1 a esto y la nueva array es [0, 0, 2, 0] (El sistema numérico es 3: simplemente agregamos 0012 y 1 en el sistema de base 3 )
Verificamos el número de ocurrencias de cada número en la array y lo verificamos con las ocurrencias de cada letra en la array de referencia original. En este caso, [0, 0, 2, 0] es una secuencia inválida ya que cuenta(0) > número de ceros (o ‘a’, el carácter asignado a 0) en la string original
Repetimos el proceso hasta que nuestra array sea igual a [2, 1, 0, 0], es decir, el mayor número válido que se puede generar y, por lo tanto, agotar todas las permutaciones.
Este enfoque se ejecuta con una complejidad de O(n (n + 1) ) .
Optimización del algoritmo
La premisa básica sigue siendo la misma. Ahora, sin embargo, el algoritmo trata de evitar muchos estados o permutaciones irrelevantes e inútiles.
La función generar permutación (string) prepara la tabla de referencia (vector de referencia en el código) que almacena el carácter asignado para cada índice y sus ocurrencias. También prepara la palabra de enteros mapeados. (array de enteros a permutar).
La función llama a la función getNext(args…) que altera la array a la siguiente permutación. Cuando hay desbordamiento (todas las permutaciones generadas), la función devuelve FIN. De lo contrario, devuelve VÁLIDO.
Por lo tanto, para obtener el siguiente estado, primero incrementamos la array en 1 como se hizo en el enfoque anterior. Hacemos un seguimiento del rango de índices que se cambiaron debido a la adición.
Ejemplo:
Incrementar [0, 2, 2, 2] da [1, 0, 0, 0] con el rango de índices modificados {1, 2, 3} o [1, 3]. Después de eso, comenzamos desde el índice más a la izquierda y verificamos si es un número válido.
El número es válido si la substring anterior a la izquierda, es decir, [0, izquierda] tiene instancias del valor a[izquierda] estrictamente menores que n, donde n es el número de ocurrencias de a[izquierda] en la array original.
- Compruebe la validez de la izquierda.
- Si no hay conflicto, incremente a la izquierda, vaya al paso 1. Rompa si queda == último índice de la array.
- De lo contrario, incremente a[left], si a[left] < base (número de elementos distintos), vaya al paso 1.
- De lo contrario, agregue 1 al subarreglo [0, izquierda] y obtenga el nuevo índice izquierdo que inicia el rango de partes modificadas. Vaya al paso 1.
La función devuelve VÁLIDO si la permutación generada es válida, FIN si se produce un desbordamiento.
La comprobación de validez se realiza mediante la función auxiliar hasConflict(args…) que simplemente comprueba el subarreglo [0, izquierda) en busca de apariciones de a[izquierda].
Si el número de ocurrencias es estrictamente menor que las ocurrencias de a[left] en la array original, devuelve verdadero; de lo contrario, es falso.
Al verificar y agregar índices a la izquierda primero, omitimos muchos estados que de otro modo se habrían colado en el algoritmo.
El algoritmo pasa por un máximo de O(n) estados para cada estado.
Por lo tanto, Complejidad de tiempo: O(n * n!)
Complejidad de espacio: O(n)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// No more permutations can be generated
#define END -1
// Permutation is valid
#define VALID 1
// Utility function to print the
// generated permutation
void printString(vector<int>& word,
vector<pair<char, int> >& ref)
{
for (int i = 0; i < word.size(); i++) {
cout << ref[word[i]].first;
}
cout << "\n";
}
// Function that checks for any conflict present
// in the word/string for the index
bool hasConflict(vector<int>& word,
vector<pair<char, int> >& ref, int index)
{
// Check number of instances where value of
// the character is equal to the
// value at checking index
int conflictCount = 0;
for (int i = 0; i < index; i++) {
if (word[i] == word[index])
conflictCount++;
}
// If the number of instances are greater
// than the number of occurrences of the
// character then conflict is present
if (conflictCount < ref[word[index]].second) {
return false;
}
return true;
}
// Function that returns the validity of the
// next permutation generated and makes
// changes to the word array
int getNext(vector<int>& word,
vector<pair<char, int> >& ref, int mod)
{
int left, right, carry;
right = word.size() - 1;
carry = 1;
// Simply add 1 to the array word following
// the number system with base mod
// generates a new permutation
for (left = right; left >= 0; left--) {
if (left == 0 && word[left] + carry >= mod) {
return END; // overflown
}
if (word[left] + carry >= mod) {
word[left] = (word[left] + carry) % mod;
}
else {
word[left] = word[left] + carry;
break;
}
}
// All the values between left and right (inclusive)
// were changed and therefore need to be
// adjusted to get a valid permutation
while (left <= right) {
while (hasConflict(word, ref, left) && word[left] < mod) {
// Increment till conflict between substring [0, i)
// is resolved or word[left] goes above mod
word[left]++;
}
if (word[left] >= mod) {
// The value for left has crossed mod therefore
// all the values for word with [0, left)
// constant have been converted therefore add 1
// to the substring [0, left) to get a new value
// of left which represents all affected parts.
// Repeat the process of conflict resolvation
// and validity checking from this new left
word[left] %= mod;
int carry = 1;
left--;
while (left >= 0) {
if (left == 0 && word[left] + carry >= mod) {
// Overflow
return END;
}
if (word[left] + carry >= mod) {
word[left] = (word[left] + carry) % mod;
left--;
}
else {
word[left] = (word[left] + carry);
break;
}
}
}
else {
// Increment left if conflict is resolved
// for current index and do conflict
// resolution for the next index
left++;
}
}
return VALID;
}
// Iterative function to generate all the
// distinct permutations of str
void generatePermutations(string str)
{
if (str.size() == 0)
return;
// First sort the string to assign mapped values
// and occurrences to each letter
// Sorting needs to handle letters
// with multiple occurrences
sort(str.begin(), str.end());
// Reference vector to store the mapping of
// its index to its corresponding char
// and the number of occurrences of the character
// as the second element of the pair
vector<pair<char, int> > ref(str.size());
// Assign each character its index and the
// number of occurrences
int count = 0;
ref[count] = make_pair(str[0], 1);
for (int i = 1; i < str.size(); i++) {
// Increment occurrences if character is repeated
// Else create new mapping for the next character
if (str[i] == str[i - 1]) {
ref[count].second++;
}
else {
count++;
ref[count] = make_pair(str[i], 1);
}
}
// Size may differ in case of multiple
// occurrences of characters
ref.resize(count + 1);
// Construct the word
// Word stores the mapped values for every letter
// in a permuted sequence i.e. say for "abc"
// word would be initially [0, 1, 2] or "aba", [0, 1, 0]
vector<int> word;
for (int i = 0; i < ref.size(); i++) {
for (int j = 0; j < ref[i].second; j++)
word.push_back(i);
}
// mod is the number of distinct letters in string
int mod = ref.size();
int flag = VALID;
while (flag != END) {
// If the permutation sent by getNext
// is valid then print it
printString(word, ref);
// Get the next permutation, validity
// stored in flag
flag = getNext(word, ref, mod);
}
}
// Driver code
int main()
{
string str = "abc";
generatePermutations(str);
return 0;
}
abc acb bac bca cab cba
Publicación traducida automáticamente
Artículo escrito por HariomNarang y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA