Combinazioni consentite degli elementi di un elenco - Prolog

Question

Come posso generare tutte le combinazioni possibili degli elementi di un elenco?

Ad esempio, data la lista [1,2,3], voglio progettare un predicato con la forma comb([1,2,3], L). che dovrebbe restituire il seguente risposta per L:
[1]
[2]
[3]
[1,2]
[2,1]
[1,3]
[3,1]
[2,3]
[3,2]
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Answer 1

Ciò che si richiede riguarda entrambe le combinazioni (selezione di un sottoinsieme) e permutazioni (riorganizzazione dell'ordine) di un elenco.

L'output di esempio implica che la lista vuota non è considerata una soluzione valida, quindi la escluderemo nell'implementazione che segue. Riconsiderare se questa è stata una svista. Anche questa implementazione produce le soluzioni in un ordine diverso rispetto all'output di esempio.

comb(InList,Out) :- 
    splitSet(InList,_,SubList), 
    SubList = [_|_],  /* disallow empty list */ 
    permute(SubList,Out). 

splitSet([ ],[ ],[ ]). 
splitSet([H|T],[H|L],R) :- 
    splitSet(T,L,R). 
splitSet([H|T],L,[H|R]) :- 
    splitSet(T,L,R). 

permute([ ],[ ]) :- !. 
permute(L,[X|R]) :- 
    omit(X,L,M), 
    permute(M,R). 

omit(H,[H|T],T). 
omit(X,[H|L],[H|R]) :- 
    omit(X,L,R). 

Testato con Amzi! Prolog:

?- comb([1,2,3],L). 

L = [3] ; 

L = [2] ; 

L = [2, 3] ; 

L = [3, 2] ; 

L = [1] ; 

L = [1, 3] ; 

L = [3, 1] ; 

L = [1, 2] ; 

L = [2, 1] ; 

L = [1, 2, 3] ; 

L = [1, 3, 2] ; 

L = [2, 1, 3] ; 

L = [2, 3, 1] ; 

L = [3, 1, 2] ; 

L = [3, 2, 1] ; 
no 

Answer 2

Suggerimento: Questo è facile da fare se avete scritto un predicato inselt(X,Y,Z), che detiene eventuale inserimento di Y in X dà Z:

inselt([E|X], Y, [E|Z]) :- inselt(X,Y,Z). 
inselt(X, Y, [Y|X]). 

Poi comb/3 possono essere codificati in modo ricorsivo utilizzando inselt/3.

Answer 3

v'è un predicato predefinito denominato permutazione ...

1 ?- permutation([1,2,3],L). 
L = [1, 2, 3] ; 
L = [2, 1, 3] ; 
L = [2, 3, 1] ; 
L = [1, 3, 2] ; 
L = [3, 1, 2] ; 
L = [3, 2, 1] . 

2 ?- listing(permutation). 
lists:permutation([], [], []). 
lists:permutation([C|A], D, [_|B]) :- 
     permutation(A, E, B), 
     select(C, D, E). 

lists:permutation(A, B) :- 
     permutation(A, B, B). 

true. 

speranza che questo aiuti ..

Answer 4

Resta pura definendo comb/2 sulla base di same_length/2, prefix/2, foldl/4 e select/3 :

 
comb(As,Bs) :- 
    same_length(As,Full), 
    Bs = [_|_], 
    prefix(Bs,Full), 
    foldl(select,Bs,As,_). 

Ecco la query di esempio proposta dal OP:

?- comb([1,2,3],Xs). 
    Xs = [1] 
; Xs = [2] 
; Xs = [3] 
; Xs = [1,2] 
; Xs = [1,3] 
; Xs = [2,1] 
; Xs = [2,3] 
; Xs = [3,1] 
; Xs = [3,2] 
; Xs = [1,2,3] 
; Xs = [1,3,2] 
; Xs = [2,1,3] 
; Xs = [2,3,1] 
; Xs = [3,1,2] 
; Xs = [3,2,1] 
; false. 

Ok! Ma cosa succede se la lista data come primo argomento contiene duplicati?

?- comb([1,1,2],Xs). 
    Xs = [1] 
; Xs = [1]     % (redundant) 
; Xs = [2] 
; Xs = [1,1] 
; Xs = [1,2] 
; Xs = [1,1]     % (redundant) 
; Xs = [1,2]     % (redundant) 
; Xs = [2,1] 
; Xs = [2,1]     % (redundant) 
; Xs = [1,1,2] 
; Xs = [1,2,1] 
; Xs = [1,1,2]    % (redundant) 
; Xs = [1,2,1]    % (redundant) 
; Xs = [2,1,1] 
; Xs = [2,1,1]    % (redundant) 
; false. 

Non proprio! Possiamo sbarazzarci delle risposte ridondanti sopra? Sì, usa semplicemente selectd/3!

 
comb(As,Bs) :- 
    same_length(As,Full), 
    Bs = [_|_], 
    prefix(Bs,Full), 
    foldl(selectd,Bs,As,_). 

Quindi cerchiamo di eseguire nuovamente sopra di query di nuovo con la migliore attuazione delle comb/2!

?- comb([1,1,2],Xs). 
    Xs = [1] 
; Xs = [2] 
; Xs = [1,1] 
; Xs = [1,2] 
; Xs = [2,1] 
; Xs = [1,1,2] 
; Xs = [1,2,1] 
; Xs = [2,1,1] 
; false.