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.
