CODEWITHSUNDEEP
prologcombinations
Heves
Heves

Reputation: 5

How to generate all permutations from positional value-lists in Prolog?

I have a list of lists and I'd like to generate the possible permutations, the first element coming from the first sub-list, the second from the second sub-list and so on.

?- A = [[1], [a, b], [2]], magic_function(A, Ans).
   Ans = [1, a, 2]
;  Ans = [1, b, 2]
;  false.

?- B = [[1], [a, b], [4, 5]], magic_function(B, Ans).
   Ans = [1, a, 4]
;  Ans = [1, a, 5]
;  Ans = [1, b, 4]
;  Ans = [1, b, 5]
;  false

I suppose it's a pretty standard idea, but for some reason I just can't seem to come up with anything useful.

Upvotes: 0

Views: 60

Answers (2)

TessellatingHeckler
TessellatingHeckler

Reputation: 29033

I've been trying to do this without using built-in functions

Do it without maplist:

perms([], []).
perms([List|Ls], [Item|T]) :-
    member(Item, List),
    perms(Ls, T).

And without member/2 by writing a custom version:

member_list(X, [X|_]).
member_list(X, [_|T]) :-
    member_list(X, T).

perms([], []).
perms([List|Ls], [Item|T]) :-
    member_list(Item, List),
    perms(Ls, T).

e.g.

?- A = [[1], [a, b], [2]], perms(A, Ans).
  Ans = [1, a, 2]
; Ans = [1, b, 2]

?- B = [[1], [a, b], [4, 5]], perms(B, Ans).
  Ans = [1, a, 4]
; Ans = [1, a, 5]
; Ans = [1, b, 4]
; Ans = [1, b, 5]

Upvotes: 0

notoria
notoria

Reputation: 3059

It can be done using maplist/3 and member/2:

?- maplist(member, Es, [[1],[a,b],[2]]).
   Es = [1,a,2]
;  Es = [1,b,2].

Upvotes: 3

Related Questions