Give as a solution every different number in a list of lists

Question

I need to do a predicate, select(ListOfLists, X) that returns as a solution every different number in a list of lists, starting with the numbers that are alone in a list, for example:

select([[1,2,3],[1,2],[4],[3]],X).

Would return:

X = 4 ; 
X = 3 ;
X = 2 ;
X = 1

Order doesn't matter as long as the numbers that are alone in the list are shown first.

To do this, first I coded 2 other predicates, which are:

%OrderedList is Lists ordered by size.  
orderListsBySize(Lists, OrderedLists).

Example: orderListsBySize([[1,2],[6],[3,4,5]], L). ->L = [[6], [1,2], [3,4,5]]

And

%ListsWithoutX is Lists without the X elements  
removeFromLists(X, Lists, ListsWithoutX).

Example: removeFromLists(1,[[1,2],[3],[4,1,5]],L). -> L = [[2],[3],[4,5]]

Both predicates work.

Then, to do the select(ListOfLists, X) predicate, I tried the following:

select([[X|[]]|_], X). select(L1,S) :-
    orderListsBySize(L1, [[X|XS]|LS]),
    length(XS, A),
    A == 0,
    select([[X|[]]|M], S),
    removeFromLists(X, [XS|LS], M).  
select([[X|_]|_], X).

But it doesn't work.
It's not a hard exercise to do in other languages, the problem is that it's still hard for me to understand how prolog works. I appreaciate any help, thanks!

Just a syntactic comment: [X|[]] is exactly the same as [X]. — lurker

user27815 user27815 · Accepted Answer · 2018-05-25T09:45:15

You could start with:

select2(ListOfLists,Element):-
    length(List,_Len),
    member(List,ListOfLists),
    member(Element,List).

Which will return all the answers, but then get stuck in a loop looking for ever bigger lists. This can be averted using the :-use_module(library(clpfd)). and defining a fd_length/2 which wont keep looking for bigger lists then exist in the list of lists.

fd_length(L, N) :-
   N #>= 0,
   fd_length(L, N, 0).

fd_length([], N, N0) :-
   N #= N0.
fd_length([_|L], N, N0) :-
   N1 is N0+1,
   N #>= N1,
   fd_length(L, N, N1).

select(ListOfLists,Element):-
    maplist(length,ListOfLists,Lengths),
    sort(Lengths,SortedLength),
    last(SortedLength,Biggest),
    Biggest #>= Len,
    fd_length(List,Len),
    member(List,ListOfLists),
    member(Element,List).

Example Query:

?-select([[1,2,3],[1,2],[4],[3]],X).
X = 4
X = 3
X = 1
X = 2
X = 1
X = 2
X = 3
false

If you want unique solutions, you could enclose in a setof/3 and then call member/2 again.

Give as a solution every different number in a list of lists

1 Answers