CODEWITHSUNDEEP
prolog
Love programming
Love programming

Reputation: 55

Reorder list in prolog

I want to rearrange a list according to the occurrence of length of sublists from small to large.For example,the expected answer is rearranged by the number of the length of sub-list,there is one length of 4,two length of 1, three length of 3 and four length of 2.

Example query and its result: 

lists_ascending([[a,b],[c],[a,b,c],[d,d,d],[d,s],[s],[d,s,s,a], [s,a],[s,t],[a,b,w]],Ls).
Ls = [[d,s,s,a],[c],[s],[a,b,c],[d,d,d],[a,b,w],[a,b],[d,s],[s,a],[s,t]]

My idea is that to calculate each length first and then do rearrangement. What I have done so far is to collect the number of sublist whose length is equal to the first sublist using the pattern [length-number].

count([],[0-0]).
count([A|B],[L-N]):-
    length(A,L),
    same_length(B,L,M),
    N is M+1.

same_length([],_,0).
same_length([A|B],L,N) :-
    (   length(A,L)->
        same_length(B,L,M),
        N=M+1
    ;   same_length(B,L,N)
    ).

The count(LIST,X) output is as followed:

21 ?- count_slot([[2],[3],[4],[2,3,4]],X).
X = [1-3].

But the expected output is [1-3,3-1], I don't know how to deal with the rest sublist(remove one by one??) and rearrange them according to the pattern [1-3,3-1].

Can somebody help? Thanks in advanced.

Upvotes: 0

Views: 404

Answers (1)

mat
mat

Reputation: 40768

You need to account for the case that there may be multiple sublists of the same length as the first sublist. Clearly, your count/2 only ever describes the case where there is at most a single one of them, because its second argument is a list of length 1.

To gather the sublists of the same length as the first sublist, consider for example:

lists_same_length_as_first([Ls|Lss], Subs) :-
    length(Ls, L),
    phrase(length_sublists(L,Lss), Subs).

length_sublists(_, []) --> [].
length_sublists(L, [Sub|Subs]) -->
    (   { length(Sub, L) } -> [Sub]
    ;   []
    ),
    length_sublists(L, Subs).

which you can also write more compactly by using include/3:

lists_same_length_as_first([Ls|Lss], Subs) :-
    length(Ls, L),
    include(length_equal(L), Lss, Subs).

length_equal(L, Ls) :- length(Ls, L).

Example query and its result:

?- lists_same_length_as_first([[2],[3],[4],[2,3,4]], Ls).
Ls = [[3], [4]].

By the way, I gave a complete solution to this problem here.

Upvotes: 1

Related Questions