Finding all sublists of a list

[harry270768]

Hi , i am a newbie to prolog so can you guys help me in writing a program
which returns all the sublist of a list

Example :

allsubsets([1,2,3],X)?

X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Thanx in advance !!!!!

[Dave]

Hi!

It sounds very much like a homework assignment to me.

First thing you should do, is to write a simple subset/2
predicate, which is capable of returning each subset of
a list, one by one. For that, you should find a simple, but
logical way of expressing what a subset is, preferably using
some sort of recursion.
The way I was thinking is that the only subset of an empty
list, is the empty list. However if you have a list with at least
one element, there are two possibilities. Either the first element
is in the subset, or it is not.
So what I mean is that to find all subsets of a list, you need to
cut down the first element, find all subsets of the remaining
list, than for each subset found, you may or may not add the
original first element.

To collect all subsets into a list, you can use the built-in
findall/3 meta-predicate, where findall(X, pred(X), L), will
collect all Xs which satisfy the pred(X) statement, and collect
those Xs into the list L.

I hope that would be enough to write your solution.

Dave

Post by harry270768
Hi , i am a newbie to prolog so can you guys help me in writing a program
which returns all the sublist of a list
allsubsets([1,2,3],X)?
X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Thanx in advance !!!!!

[Christopher Browne]

Post by harry270768
Hi , i am a newbie to prolog so can you guys help me in writing a program
which returns all the sublist of a list
allsubsets([1,2,3],X)?
X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Could you tell us who your professor is, so we can submit the answers
directly to ensure proper academic credit? After all, you wouldn't
want to accidentally commit an academic offense that would get you
expelled, would you?

[flapper]

Post by harry270768
Hi , i am a newbie to prolog so can you guys help me in writing a program
which returns all the sublist of a list
allsubsets([1,2,3],X)?
X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Thanx in advance !!!!!

I believe that secret of Prolog programming is the ability to derive
the solution to a problem from first pribciples -- which in the case of
the problem you have been given is quite subtle.

The first time I tried to solve this problem in Prolog, the only way
I could see to generate all the possible sublists of a given list would
be to generate all the possible bitmasks of the same length as the given
list and then use these bitmasks to "mask out" the elements of the
corresonding sublist.

For example, if the given list was

[q,w,e,r,t,y]

amd the "bitmask" was

[1,0,1,1,0,1]

the corresponding sublist would be

[q,e,r,y]

/*
It is easy to describe the set of all possible bitmasks of a given length:
*/
is_bit(0).
is_bit(1).

bitmask(0,[]).
bitmask(N,[Bit|Mask]) :-
N > 0,
is_bit(Bit),
N1 is N - 1,
bitmask(N1,Mask).
/*
And, given a list L and a bitmask M of the same length as L, it is easy
to see how the bitmask can be used to select the members of L that
belong to the sublist that corresponds to M.
*/
mask([],[],[]).
mask([1|Bits],[X|L],[X|SL]) :-
mask(Bits,L,SL).
mask([0|Bits],[_|L],SL) :-
mask(Bits,L,SL).
/*
So, combining these two tools, I arrived at what at that time
(<***@sonic.net>) I thought was "the cleanest way" to
generate sublists:
*/
gen_sublist(L,SL) :-
length(L,N),
bitmask(N,M),
mask(M,L,SL).
/*
However, what did not occur to me to do at the time was to take i/o
modes into account. If I had, I might have noticed that even though I
was thinking i.t.o. (i,i,o) when I wrote the above clauses for 'mask/3',
it also works in mode (o,i,o).

Try it, and see what happens. ;)

*/

--
sequitur AT sonic DOT net

[billh]

Post by harry270768
Hi , i am a newbie to prolog so can you guys help me in writing a program
which returns all the sublist of a list
allsubsets([1,2,3],X)?
X = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Thanx in advance !!!!!

I believe the secret of successful Prolog programming is the ability
to derive the solution to a problem from first principles -- which in
the case of the problem you have been given is IMHO quite subtle.

The first time I tried to solve this problem in Prolog, the only way
I could see to generate all the possible sublists of a given list would
be to generate all the possible bit masks of the same length as the
given list and then use these bit masks to "mask out" the elements of
the corresponding sublist.

For example, if the given list was

[q,w,e,r,t,y]

and the "bit mask" was

[1,0,1,1,0,1]

the corresponding sublist would be

[q,e,r,y]

/*
It is easy to describe the set of all possible bitmasks of a given length:
*/
is_bit(0).
is_bit(1).

bitmask(0,[]).
bitmask(N,[Bit|Mask]) :-
N > 0,
is_bit(Bit),
N1 is N - 1,
bitmask(N1,Mask).
/*
And, given a list L and a bitmask M of the same length as L, it is
easy enough to see how the bitmask M can be used to select the members
of L that belong to the sublist SL that corresponds to M:
*/
mask([],[],[]).
mask([1|Bits],[X|L],[X|SL]) :-
mask(Bits,L,SL).
mask([0|Bits],[_|L],SL) :-
mask(Bits,L,SL).
/*
So, combining these two tools, I arrived at what at the time
(<***@sonic.net>) I thought was "the cleanest way" to
generate sublists:
*/
gen_sublist(L,SL) :-
length(L,N),
bitmask(N,M),
mask(M,L,SL).

/*
No doubt the reason this approach appealed to me was because that is
how I would have handled this problem during my days as a data analyst
and Fortran programmer. IOW, instead of trying to derive a fresh
understanding of the given problem on the basis of first principles, I
simply described how I was used to handling this particular problem in
Fortran.

As a result, it never even occurred to me to take into account the
fact that Prolog predicates written with one combination of given and
unknown arguments -- that is, i/o modes -- in mind sometimes also work
with other combinations of givens and unknowns. If it had, I might have
noticed that even though I was thinking i.t.o. (i,i,o) when I wrote the
above definition of 'mask/3', it also works in mode (o,i,o).

Try it and see what happens.

*/

p.s. See also:

<***@pacbell.net>

<3cdfe4d1$0$237$***@news.dial.pipex.com>

http://groups.google.com/advanced_group_search

--
sequitur AT sonic DOT net