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

On 25/09/2013, at 4:39 AM, Norbert E. Fuchs wrote:

> 
> Hi
> 
> I need all subsets of a list in the order of ascending length of the subsets.

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?

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 works quite nicely and efficiently, but nevertheless I wonder whether there isn't a simpler way to perform this operation. 

See above.