Todas las permutaciones de una string usando iteración.

Una permutación, también llamada «número de arreglo» u «orden», es un reordenamiento de los elementos de una lista ordenada S en una correspondencia uno a uno con S mismo. ¡Una string de longitud n tiene n! permutación ( Fuente: Mathword )

A continuación se muestran las permutaciones de la string ABC.
ABC ACB BAC BCA CBA CABINA

Hemos discutido diferentes enfoques recursivos para imprimir permutaciones aquí y aquí .

¿Cómo imprimir todas las permutaciones iterativamente?
Una solución simple para usar permutaciones de n-1 elementos para generar permutaciones de n elementos.

Por ejemplo, veamos cómo generar permutaciones de tamaño 3 usando permutaciones de tamaño 2.

Las permutaciones de dos elementos son 1 2 y 2 1. Las
permutaciones de tres elementos se pueden obtener insertando 3 en diferentes posiciones en todas las permutaciones de tamaño 2.
Insertar 3 en diferentes posiciones de 1 2 conduce a 1 2 3, 1 3 2 y 3 1 2.
Insertar 3 en diferentes posiciones de 2 1 conduce a 2 1 3, 2 3 1 y 3 2 1.

Para generar permutaciones de tamaño cuatro, consideramos las seis permutaciones anteriores de tamaño tres e insertamos 4 en diferentes posiciones en cada permutación.

Una solución eficiente es utilizar el algoritmo de Johnson y Trotter para generar todas las permutaciones de forma iterativa.