Tag Archives: Prolog

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.

Família Simpsons em Prolog

Os Simpsons no sofá

% Fatos.
homer.
marge.
bart.
lisa.
maggie.
mona.
jacqueline.
patty.
abraham.
clancy.
hugo.
louise.
herb.
 
mulher(marge).
mulher(maggie).
mulher(lisa).
mulher(mona).
mulher(jacqueline).
mulher(selma).
mulher(patty).
mulher(louise).
 
homem(homer).
homem(bart).
homem(abraham).
homem(clancy).
homem(hugo).
homem(herb).
homem(clancy).
 
progenitor(homer,bart).
progenitor(homer,lisa).
progenitor(homer,maggie).
progenitor(marge,bart).
progenitor(marge,lisa).
progenitor(marge,maggie).
 
progenitor(abraham, homer).
progenitor(mona, homer).
 
progenitor(clancy, marge).
progenitor(clancy, patty).
progenitor(clancy, selma).
progenitor(jacqueline, marge).
progenitor(jacqueline, patty).
progenitor(jacqueline, selma).
 
progenitor(abraham, herb).
 
progenitor(herb, hugo).
progenitor(louise, hugo).
 
% Regras
pai(A,B) :- homem(A), progenitor(A,B).
mãe(A,B) :- mulher(A), progenitor(A,B).
 
é_pai(A) :- pai(A,_).
é_mãe(A) :- mãe(A,_).
 
filho(A,B):- homem(A), progenitor(B,A).
filha(A,B):- mulher(A), progenitor(B,A).
 
irmaos(X,Y) :-
	progenitor(Z,X),
	progenitor(Z,Y),
	X\=Y.
 
irmao_completos(A,B) :-
	pai(P,A), pai(P,B),
	mãe(M,A), mãe(M,B),
	A\=B.
 
tio(T,A) :-
	homem(T),
	irmaos(T,X), progenitor(X,A).
 
tia(T,A) :-
	mulher(T),
	irmaos(T,X), progenitor(X,A).
 
primo(A,B) :-
	homem(A),
	progenitor(X,A),
	progenitor(Y,B),
	irmaos(X,Y).
 
prima(A,B) :-
	mulher(A),
	progenitor(X,A),
	progenitor(Y,B),
	irmaos(X,Y).
 
avô(A,B) :- pai(A,X), pai(X,B).
avó(A,B) :- pai(A,X), pai(X,B).

Referências: