Gerando permutações

Muitas vezes para resolver uma única instância de um problema é mais rápido ataca-lo com força bruta do que encontrar um algoritmo geral com uma boa ordem de complexidade. Permutações são de grande utilidade nesse tipo de abordagem.

Permutações em Prolog:

Esse é um código em Prolog que o Wladimir Araujo passou na cadeira de IA.

select(X, [X|Xs], Xs).
select(X, [Y|Ys], [Y|Zs]) :- select(X, Ys, Zs).

permutar([], []).
permutar(Xs, [Z|Zs]) :-
    select(Z, Xs, Ys),
    permutar(Ys, Zs).

Permutações em Python:
Esse é um código de um certo Michael Davies que eu tirei daqui. Ele gera uma lista com todas as permutações de uma lista. Muito bonitinho. 🙂

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]

Um exemplo de uso:

>>> for p in all_perms(['a','b','c']):
	print p
['a', 'b', 'c']
['b', 'a', 'c']
['b', 'c', 'a']
['a', 'c', 'b']
['c', 'a', 'b']
['c', 'b', 'a']

Outras implementações:
Em outras linguagens o código para gerar permutações geralmente é muito grande, então eu preferi deixar alguns links.

• Permutações em C
• Permutações em Java
• Permutações em Ruby