Barrapunto

Es algo sencillo... las permutaciones de N elementos es lo mismo que, para cada elemento de los N, fijarlo como primer elemento de la combinación, y proceder de la misma forma (recursivamente) con el resto de los elementos.

Tal vez no sea la solución más rápida (en cuanto a ejecución puede referirse) ni tampoco la que menos memoria consuma... eso sí, seguramente sea la que más rápido escribas.

La recursividad es muy muy potente en algunos casos. Y ya al hilo de la conversación, aprender también algún lenguaje declarativo te permite buscar soluciones por otras vías. La solución que he propuesto sería la típica que haría un programador de prolog (en apenas 4 líneas). Portar una solución a un problema sencillo (como es este caso) a C, también es muy sencillo.

Saludos, y espero haberte ayudado.