Re: list with all the combinations of the initial list elements]

Bogdan wrote:
>
> So I will to explain you what I want to do with the findall result.
>
> I have a list Initial_List = [a,b,c,d] for example
> With your predicate I can find a combination between the list
> elements. But I want a final list will all the possible combinations .
>
>  Combin_List=[[a],[b],[c],[d],[a,b],[a,c]
,[a,d],[a,b,c],[a,b,d],….[a,b,c,d]]
>
> After that, I will check if every sublist of Combin_List verifies 2
> conditions and all the sublist which verify these conditions I will
> put them in a new list, Wanted_List.
> I thought it will be something like that:
>
> verify(Initial_List,Wanted_List):- findall(Z,subset(Initial_List,Z),Combin_

List),
>      verify(Combin_List,Wanted_List).
>
> verify(_,[ ],_).
>
>  verify([Head|Combin_List],[Head|Wanted_L
ist]):-
> condition1(Head),condition2(Head), verify(Combin_List,Wanted_List).
>
> The list Wanted_List will be for example:
>
> Wanted_List = [[b],[b,c],[c,d],[a,b,d],[a,b,c,d]].
>
> The problem is, I must to be sure I check all the possible
> combinations between the Initial_List elements. So I use findall.
>
> But in this situation, if I have Initial_List with 21 elements, the
> SWI Prolog's global steak limit memory is not enough.
>
> I hope you can give me some advices. I am a Phd. student and here in
> my laboratory there isn't someone who works with Prolog. And you know,
> when you start is difficult.
>

It occurs to me that one way this might be done would be by
using two computers (or two processes), one that produces the
subsets and one that consumes them. I don't know exactly how
this sort of thing is done in Prolog, but I envision something
along the following lines:

on producer side,

:- dynamic pipe/1.

open_pipe :-
retractall(pipe(_)).

produce_subsets :-
write('sending subsets...'),nl,
produce_subset(Next),
send_subset(Next),
fail.
produce_subsets :-
write('no more subsets to send.'),nl.

produce_subset(Next) :-
subset([1,2,3],Next),
write('produced '),write(Next),nl.

send_subset(Next) :-
assert(pipe(Next)),
write('sent     '),write(Next),nl.

and, on the consumer side,

consume_subsets :-
write('receiving subsets...'),nl,
receive_subset(Next),
consume_subset(Next),
fail.
consume_subsets :-
write('no more subsets to consume.'),nl.

receive_subset(Next) :-
retract(pipe(Next)),
write('received '),write(Next),nl.

consume_subset(Next) :-
write('consumed '),write(Next),nl.

where, of course, 'assert(pipe(Next))' and 'retract(pipe(Next))'
would be replaced by calls to appropriate Prolog I/O predicates.

The sequence of events on the producer side would then look like

?- open_pipe,produce_subsets.
sending subsets...
produced []
sent     []
produced [3]
sent     [3]
produced [2]
sent     [2]
produced [2, 3]
sent     [2, 3]
produced [1]
sent     [1]
produced [1, 3]
sent     [1, 3]
produced [1, 2]
sent     [1, 2]
produced [1, 2, 3]
sent     [1, 2, 3]
no more subsets to send.

and the corresponding sequence of events on the consumer side
would look like

?- consume_subsets.
receiving subsets...
received []
consumed []
received [3]
consumed [3]
received [2]
consumed [2]
received [2, 3]
consumed [2, 3]
received [1]
consumed [1]
received [1, 3]
consumed [1, 3]
received [1, 2]
consumed [1, 2]
received [1, 2, 3]
consumed [1, 2, 3]
no more subsets to consume.

--
BillH

bill hogan wrote:

> It occurs to me that one way this might be done would be by
> using two computers (or two processes), one that produces the
> subsets and one that consumes them.

BinProlog has the concept of engines; they allow you to do what
you describe.

Cheers

Bart Demoen

On 2005-04-04, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> bill hogan wrote:
> 
>
> BinProlog has the concept of engines; they allow you to do what
> you describe.

So true.  For this particular case (and many others) however,
producing the subsets on backtracking and testing them appears is a
perfect Prolog-natural way to organise a generate-and-test program
(or have I missed something in this discussion?)

Cheers --- Jan

Jan Wielemaker wrote:
> On 2005-04-04, Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> 
>
>
> So true.  For this particular case (and many others) however,
> producing the subsets on backtracking and testing them appears is a
> perfect Prolog-natural way to organise a generate-and-test program
> (or have I missed something in this discussion?)
>

I thought the general problem was that

findall(Subset, (next_subset(Set,Subset), passes_test(Subset)), Keepers )

caused (ram and disk-virtual) memory overflow.

If you have in mind something like

loop(Set) :-
next_subset(Set,Subset),
passes_test(Subset),
fail.
loop(_).

what do you propose to do with all the subsets that pass the test?

If there are so many such subsets that you have to process them
one-by-one, wouldn't you need a second process and some way
connect the two, like

producer --> subset --> test --> pipe --> subset --> consumer ?

--

student wrote:

> I thought the general problem was that
>
> findall(Subset, (next_subset(Set,Subset), passes_test(Subset)), Keepers )
>
> caused (ram and disk-virtual) memory overflow.


Did the OP say this ? I can't remember; he seemed just reluctant to try
the above suggestion by Jan. But it might be true anyway ...


> If there are so many such subsets that you have to process them
> one-by-one, wouldn't you need a second process and some way
> connect the two, like
>
> producer --> subset --> test --> pipe --> subset --> consumer ?

This can be done in one process as well - generate the next subset
from the current one at the moment you need it; something like

?- process_subsets(Set,[]).

process_subsets(Set,CurrentSubSet) :-
(test(CurrentSubSet) ->
do_something(CurrentSubSet)
;
true
),
 nextsubset(CurrentSubSet,SubSet,NextSubS
et),
process_subsets(Set,NextSubSet).

Cheers

Bart Demoen

Bart Demoen wrote:
> student wrote:
> 
> 
>
>
> This can be done in one process as well -

 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!
> *generate the next subset from the current one at the moment you need
it;
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!

> something like
>
>     ?- process_subsets(Set,[]).
>
>     process_subsets(Set,CurrentSubSet) :-
>         (test(CurrentSubSet) ->
>             do_something(CurrentSubSet)
>         ;
>             true
>         ),
>         nextsubset(CurrentSubSet, SubSet, NextSubSet),  <--- ?
>         process_subsets(Set,NextSubSet).
>

Do you mean

process_subsets(Set, CurrentSubSet) :-
(test(CurrentSubSet) ->
do_something(CurrentSubSet)
;
true
),
nextsubset(CurrentSubSet, Set, NextSubSet),
process_subsets(Set, NextSubSet).

?

Hmm.

For any given Set and current subset CurrSubset

nextsubset(CurrSubSet,Set,NextSubSet) if and only if NextSubset is ... ?

What?

What could "the next subset after the current subset" mean?

Look at an example.

?- nextsubset([1,2,4], [1,2,3,4,5], X ).

X = ... what?

What would come next "after" [1,2,4] and why?

Look at "bitmask" for [1,2,4].

(1,1,0,1,0) = 50

Is this a clue?

51 = (1,1,0,1,1) = [1,2,4,5] ?

Thank you.

--

student wrote:
 
>
>   Do you mean
>
>      process_subsets(Set, CurrentSubSet) :-
>          (test(CurrentSubSet) ->
>              do_something(CurrentSubSet)
>          ;
>              true
>          ),
>          nextsubset(CurrentSubSet, Set, NextSubSet),
>          process_subsets(Set, NextSubSet).
>
> ?


Yes. Sorry, I should have said it was untested code.

>  Look at an example.
>
>   ?- nextsubset([1,2,4], [1,2,3,4,5], X ).
>
>    X = ... what?
>
>  What would come next "after" [1,2,4] and why?
>
>  Look at "bitmask" for [1,2,4].
>
>  (1,1,0,1,0) = 50
>
>  Is this a clue?
>
>  51 = (1,1,0,1,1) = [1,2,4,5] ?
>
>  Thank you.
>
> --

That's a good way to do it. Here is code that uses essentially
the same idea, but passes along only the description of the current
subset.

process_subsets(Set,Filter) :-
initial_descr(Set,Empty),
process_subsets(Set,Empty,Filter).

process_subsets(Set,Descr,Filter) :-
(subset(Set,Descr,Subset), call(Filter,Subset) ->
write(goodsubset:Subset), nl
;
true
),
next_descr(Descr,1,NextDescr),
process_subsets(Set,NextDescr,Filter).

subset([],_,[]).
subset([X|Xs],[C|Cs],Subset) :-
(C == 1 ->
Subset = [X|Restsubset]
;
Subset = Restsubset
),
subset(Xs,Cs,Restsubset).

next_descr([],Carry,[]) :-
(Carry == 1 ->
write(done), nl,
fail
;
true
).
next_descr([C|Cs],Carry,[NC|NCs]) :-
Z is C + Carry,
NC is Z /\ 1,
Newcarry is Z >> 1,
next_descr(Cs,Newcarry,NCs).

initial_descr([],[]).
initial_descr([_|R],[0|S]) :- initial_descr(R,S).


test_filter(Set) :-
length(Set,N),
N < 3.

To be called as:

?- process_subsets([a,b,c],test_filter).

produces:

goodsubset : []
goodsubset : [a]
goodsubset : [b]
goodsubset : [a,b]
goodsubset : [c]
goodsubset : [a,c]
goodsubset : [b,c]
done



Cheers

Bart Demoen

student <nospam@a.b.c.dINVALID> wrote in message news:<D5l4e.13347$m31.131882@typhoon.sonic
.net>...
> Jan Wielemaker wrote: 
>
> I thought the general problem was that
>
> findall(Subset, (next_subset(Set,Subset), passes_test(Subset)), Keepers )
>
> caused (ram and disk-virtual) memory overflow.
>
> If you have in mind something like
>
>        loop(Set) :-
>           next_subset(Set,Subset),
>           passes_test(Subset),
>           fail.
>       loop(_).
>
> what do you propose to do with all the subsets that pass the test?
>
> If there are so many such subsets that you have to process them
> one-by-one, wouldn't you need a second process and some way
> connect the two, like
>
> producer --> subset --> test --> pipe --> subset --> consumer ?
>
> --
Hi,
Now, I can do it, I mean generate Subset, test it and put it in a new
List.
I have not the problem with virtual memory, but the time computation
is too long.
after that, I will analyse all the subset with a C ++ code and I will
chosse the best solution  (which give a better objectiv fonction ,for
exemple).

In this moment I don't know I must to use directly in a C code a
Prolog predicate which generate a wanted file with all subsets.

Thanks you,
Best regards

Oops:

Change the line:

subsets(n-1,vec);

To:

subsets(n-1,vec.clone());

Otherwise it wont work.
Guess why?

Jan Burse wrote:

> You can easily generate all the subsets in
> a procedural language, for example Java:
>
>   public class Subsets {
>
>      private static void subsets(int n, Vector vec) {
>         if (n==0) {
>           System.out.println(vec);
>         } else if (n>0) {
>           subsets(n-1,vec);
>           vec.addElement(new Integer(n));
>           subsets(n-1,vec);
>         }
>       }
>
>       public static void main(String[] args) {
>          subsets(5,new Vector());
>       }
>
>   }
>
> Hope this helps!
>
> Bogdan wrote:
> 

You can easily generate all the subsets in
a procedural language, for example Java:

public class Subsets {

private static void subsets(int n, Vector vec) {
if (n==0) {
System.out.println(vec);
} else if (n>0) {
subsets(n-1,vec);
vec.addElement(new Integer(n));
subsets(n-1,vec);
}
}

public static void main(String[] args) {
subsets(5,new Vector());
}

}

Hope this helps!

Bogdan wrote:

> student <nospam@a.b.c.dINVALID> wrote in message news:<D5l4e.13347$m31.131
882@typhoon.sonic.net>...
> 
>
> Hi,
> Now, I can do it, I mean generate Subset, test it and put it in a new
> List.
> I have not the problem with virtual memory, but the time computation
> is too long.
> after that, I will analyse all the subset with a C ++ code and I will
> chosse the best solution  (which give a better objectiv fonction ,for
> exemple).
>
> In this moment I don't know I must to use directly in a C code a
> Prolog predicate which generate a wanted file with all subsets.
>
> Thanks you,
> Best regards