Re: Sorting a list of lists in the order of ascending length

On 24 Sep 2013, at 18:39 , Norbert E. Fuchs <[email protected]> wrote:

> I need all subsets of a list in the order of ascending length of the subsets. 
> 
> Thus I wrote a predicate 
> 
>  generate_subset(+List, -SubList) that generates a SubList of List 
> 
> and that is also used for other purposes, and a variant of insertion sort
> 
>  sort_list_of_lists_in_ascending_length(+ListOfLists, -SortedListOfList) that sorts ListOfLists into SortedListOfList 
> 
> and then called 
> 
>  findall(SubList, generate_subset(List, SubList), SubLists), sort_list_of_lists_in_ascending_length(SubLists, SortedSubLists)
> 
> This works quite nicely and efficiently, but nevertheless I wonder whether there isn't a simpler way to perform this operation. 

I would like to thank Paulo, Richard, Jürgen and Markus for their suggestions below.

Best.

   --- nef


On 24 Sep 2013, at 19:50 , Paulo Moura <[email protected]> wrote:

> An alternative would be to modify an implementation of a power set predicate to return each subset in the form Length-Subset and then to use keysort/2.

Right, but I as I wrote I need generate_subset/2 also for other purposes.


On 25 Sep 2013, at 2:18 , Richard A. O'Keefe <[email protected]> wrote:

> Since 26 July 2007,
> 
> %   Enumerate subsets such that if A subset-of B subset-of S
> %   then    subset_biggest_first(S, B) will be reported
> %   before  subset_biggest_first(S, A).
> 
> subset_biggest_first([], []).
> subset_biggest_first([X|Xs], S) :-
>    subset_biggest_first(Xs, T),
>    ( S = [X|T] ; S = T ).
> 
> %   Enumerate subsets such that if A subset-of B subset-of S
> %   then    subset_smallest_first(S, A) will be reported
> %   before  subset_smallest_first(S, B).
> 
> subset_smallest_first([], []).
> subset_smallest_first([X|Xs], S) :-
>    subset_smallest_first(Xs, T),
>    ( S = T ; S = [X|T] ).
> 
> However, subset_smallest_first/2 satisfies a weaker property:
>  - if S1 is a proper subset of S2, S1 will be generated before S2.
> 
> ?- subset_smallest_first([a,b,c], S).
> S = [] ;
> S = [a] ;
> S = [b] ;
> S = [a, b] ;
> S = [c] ;
> S = [a, c] ;
> S = [b, c] ;
> S = [a, b, c]
> 
> I wonder if this property is strong enough for your needs?

No, since I need the subsets strictly in ascending order of length. (I am working on a theorem prover and I want to find the minimal sets of axioms needed to prove a theorem.)

> Otherwise, something like
> 
> subsets_in_size_order(Set, Sub) :-
>    length(Set, N),
>    between(0, N, L),
>    length(Sub, L),
>    generate_subset(Sub, Set).
> 
> generate_subset([], _).
> generate_subset([X|Xs], Set) :-
>    generate_subset_aux(Set, X, Set1),
>    generate_subset(Xs, Set1).
> 
> generate_subset_aux([X|Set1], X, Set1).
> generate_subset_aux([_|Set],  X, Set1) :-
>    generate_subset_aux(Set,  X, Set1).
> 
> ?- subsets_in_size_order([a,b,c], S).  
> 
> S = [] ;
> S = [a] ;
> S = [b] ;
> S = [c] ;
> S = [a, b] ;
> S = [a, c] ;
> S = [b, c] ;
> S = [a, b, c] 

This will do. I like the elegant subsets_in_size_order/2 while Richard's generate_subset/2 seems to be more complicated than my generate_subset/2 which is

generate_subset([], []).

generate_subset([X|Xs], [X|Ys]):-
  generate_subset(Xs, Ys).
  
generate_subset([_X|Xs], Ys):-
  generate_subset(Xs, Ys).


On 25 Sep 2013, at 8:35 , J. Cleve <[email protected]> wrote:

> Here is a solution, which only needs findall and length.
> Please do NOT discuss the complexity ... ;-)
> 
> 
> numbr(Max,Max,Max) :- !.
> numbr(Min,_Max,Min).
> numbr(Min, Max, N) :- Min1 is Min+1, numbr(Min1,Max,N).
> 
> subset([],_,N) :- N=0,!.
> subset([H|T],[H|L],N) :- N1 is N-1, subset(T,L,N1).
> subset(L2,[_|L],N) :- subset(L2,L,N).
> 
> ?- List=[1,2,3,4,5], length(List,LL), findall(X,
> (numbr(0,LL,N),subset(X,List,N)),L),write(L),nl.

As I wrote, I need subset/2 by itself, and your subset/3 seems to loop if not constrained by numbr/3.


On 25 Sep 2013, at 14:40 , Markus Triska <[email protected]> wrote:

> What about:
> 
>   set_ascending_length_subset(Set, Sub) :-
>           length(Set, N),
>           between(0, N, L),
>           length(Sub, L),
>           phrase(subset(Set), Sub).
> 
>   subset([])     --> [].
>   subset([L|Ls]) --> ( [L] ; []), subset(Ls).
> 
> Example:
> 
>   ?- findall(Sub, set_ascending_length_subset([a,b,c], Sub), Subs).
>   %@ Subs = [[], [a], [b], [c], [a, b], [a, c], [b, c], [a|...]].

This is a very compact an elegant solution.

set_ascending_length_subset/2 is basically the same as Richard's subsets_in_size_order/2, while the DCG for subset/1 when expanded is basically my code for generate_subset/2.


Now instead of my clumsy sort_list_of_lists_in_ascending_length/2 (based on insertion_sort)

sort_list_of_lists_in_ascending_length([], []).

sort_list_of_lists_in_ascending_length([List|Lists], Sorted) :-
  sort_list_of_lists_in_ascending_length(Lists, IntermediateSorted),
  insert(List, IntermediateSorted, Sorted).

insert(X, [], [X]).
insert(X, [Y|Ys], [Y|Zs]) :-
  length(X, LX),
  length(Y, LY),
  LX > LY,
  insert(X, Ys, Zs).
  
insert(X, [Y|Ys], [X,Y|Ys]) :-
  length(X, LX),
  length(Y, LY),
  LX =< LY.

I will used Richard's subsets_in_size_order/2, respectively Markus' set_ascending_length_subset/2, and continue to use my generate_subset/2. Thus instead of the two-step approach

  findall(findall(SubList, generate_subset(List, SubList), SubLists), sort_list_of_lists_in_ascending_length(SubLists, SortedSubLists)

I will simply have 

  findall(SubList, subsets_in_size_order(List, SubList), SortedSubLists)

Thanks again to all of you. Sorry for the long message.