Home > Archive > Prolog > April 2005 > Re: list with all the combinations of the initial list elements]
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: list with all the combinations of the initial list elements]
|
|
| bill hogan 2005-04-06, 12:44 pm |
| 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
| |
| Bart Demoen 2005-04-06, 12:44 pm |
| 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
| |
| Jan Wielemaker 2005-04-06, 12:44 pm |
| 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
| |
| student 2005-04-06, 12:44 pm |
| 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 ?
--
| |
| Bart Demoen 2005-04-06, 12:44 pm |
| 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
| |
| student 2005-04-06, 12:44 pm |
| 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.
--
| |
| Bart Demoen 2005-04-06, 12:44 pm |
| 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
| |
| Bogdan 2005-04-06, 12:44 pm |
| 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
| |
| Jan Burse 2005-04-06, 8:57 pm |
| Oops:
Change the line:
subsets(n-1,vec);
To:
subsets(n-1,vec.clone());
Otherwise it wont work.
Guess why?
Jan Burse wrote:
[color=darkred]
> 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:
>
| |
| Jan Burse 2005-04-06, 8:57 pm |
| 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.131882@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
| |
| student 2005-04-07, 4:00 am |
| Bart Demoen wrote:
> student wrote:
>
>
>
>
> Yes. Sorry, I should have said it was untested code.
>
>
>
> 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
>
Truly, a thing of beauty.
Since yesterday, I came up with something along the same lines,
crudely speaking, but whereas your program seems to be able to
handle lists of arbitrary length, mine runs out of local stack
as soon as I give it a list of length > 14 :( .
After seeing your program, I suspect the reason will turn out to
involve the difference between your elegant use of descriptors
and my heavy-handed use of bitmasks. I will take another look at
this question tomorrow, but I think it might be instructive to post my
program in its present draft form, so here it is:
next_s(Set) :-
make_zero(Set,Zero),
pnext_s(Zero,Set).
make_zero([],[]).
make_zero([_|RemSet],[0|RemZero]) :-
make_zero(RemSet,RemZero).
/*
max = next_s([a,b,c,d,e,f,g,h,i,j,k,l,m,n])
*/
pnext_s(Mask,Set) :-
apply_mask(Mask,Set,SubSet),
test_subset(SubSet),
process_subset(SubSet),
fail.
pnext_s(Mask,Set) :-
next_mask(Mask,NextMask),
pnext_s(NextMask,Set).
apply_mask([],[],[]).
apply_mask([0|RemBits],[_|RemSet],SubSet
) :-
apply_mask(RemBits,RemSet,SubSet).
apply_mask([1|RemBits],[A|RemSet],[A|Rem
SubSet]) :-
apply_mask(RemBits,RemSet,RemSubSet).
next_mask([0|Bits],[1|Bits]).
next_mask([1|Bits],[0|OtherBits]) :-
carry1(Bits,OtherBits).
carry1([0],[1]).
carry1([0|[B|Bits]],[1|[B|Bits]]).
carry1([1|[B|Bits]],[0|RemBits]) :-
carry1([B|Bits],RemBits).
test_subset(X) :-
write('>>>testing subset: '),write(X),nl.
process_subset(X) :-
write('processing subset:'),write(X),nl.
?- next_s([a,b,c]).[color=darkred]
processing subset:[][color=darkred]
processing subset:[a][color=darkred]
processing subset:[b][color=darkred]
processing subset:[a, b][color=darkred]
processing subset:[c][color=darkred]
processing subset:[a, c][color=darkred]
processing subset:[b, c][color=darkred]
processing subset:[a, b, c]
No
?-
---
billh
| |
| student 2005-04-07, 4:00 am |
| Bogdan wrote:
> student <nospam@a.b.c.dINVALID> wrote in message news:<D5l4e.13347$m31.131882@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
Sorry, I can't help you with C programming,
but be sure to look at Bart's last reply to me further along in this thread
<1112771647.3423@seven.kulnet.kuleuven.ac.be> !
Bill
| |
| Bart Demoen 2005-04-07, 4:00 am |
| student wrote:
>
> Since yesterday, I came up with something along the same lines,
> crudely speaking, but whereas your program seems to be able to
> handle lists of arbitrary length, mine runs out of local stack
> as soon as I give it a list of length > 14 :( .
....
> apply_mask([],[],[]).
> apply_mask([0|RemBits],[_|RemSet],SubSet
) :-
> apply_mask(RemBits,RemSet,SubSet).
> apply_mask([1|RemBits],[A|RemSet],[A|Rem
SubSet]) :-
> apply_mask(RemBits,RemSet,RemSubSet).
>
> next_mask([0|Bits],[1|Bits]).
> next_mask([1|Bits],[0|OtherBits]) :-
> carry1(Bits,OtherBits).
>
> carry1([0],[1]).
> carry1([0|[B|Bits]],[1|[B|Bits]]).
> carry1([1|[B|Bits]],[0|RemBits]) :-
> carry1([B|Bits],RemBits).
These three preds leave behind useless choicepoints: most Prolog
systems do indexing on the principal functor only, so if the input
argument unifies with [0], indexing does not detect that it does
not unify with [0,B|Bits] and not with [1,B,Bits] [ouch, I only just
escaped an incorrect not ... neither construct :-)]
I assume that's the reason for the out of ls.
Cheers
Bart Demoen
| |
| student 2005-04-09, 8:57 am |
| Bart Demoen wrote:
> student wrote:
>
>
> ...
>
>
>
> These three preds leave behind useless choicepoints: most Prolog
> systems do indexing on the principal functor only, so if the input
> argument unifies with [0], indexing does not detect that it does
> not unify with [0,B|Bits] and not with [1,B,Bits] [ouch, I only just
> escaped an incorrect not ... neither construct :-)]
>
> I assume that's the reason for the out of ls.
>
I tested three variations on apply_mask/3, next_mask/2, and
carry1/2, using three versions of Prolog: Yap, XSB, and
SWI-Prolog. Taking apply_mask/3 as representative, the three
variations are as follows:
%--------------------------------------------
form1([],[],[]).
form1([0|RemBits],[X|RemSet],SubSet) :-
form1(RemBits,RemSet,SubSet).
form1([1|RemBits],[X|RemSet],[X|RemSubSe
t]) :-
form1(RemBits,RemSet,RemSubSet).
%--------------------------------------------
form2([],[],[]).
form2([C|Cs],[X|Xs],Subset) :-
(C == 0 ->
Subset = RemSubset
;
Subset = [X|RemSubset]
),
form2(Cs,Xs,RemSubset).
%--------------------------------------------
form3([],[],[]).
form3([C|Cs],[X|Xs],Subset) :-
( C == 0, Subset = RemSubset ;
C == 1, Subset = [X|RemSubset] ),
form3(Cs,Xs,RemSubset).
/*
NOTE! use of '==' (as opposed to using '=')
makes these alternatives mutually exclusive!
*/
%---------------------------------------------
(similarly with the other two predicates).
I also found it instructive to compare the corresponding
interpetations placed on these three forms by LPTP:
?- def(succeeds form1(?m,?l1,?l2)).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
?m = [] & ?l1 = [] & ?l2 = [] \/
(ex [remBits,x,remSet]: ?m = [0|?remBits] & ?l1 = [?x|?remSet] &
succeeds form1(?remBits,?remSet,?l2)) \/
(ex [remBits,x,remSet,remSubSet]: ?m = [1|?remBits] & ?l1 =
[?x|?remSet] &
?l2 = [?x|?remSubSet] & succeeds
form1(?remBits,?remSet,?remSubSet))
Yes
?- def(succeeds form2(?m,?l1,?l2)).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
?m = [] & ?l1 = [] & ?l2 = [] \/
(ex [c,cs,x,xs,remSubset]: ?m = [?c|?cs] & ?l1 = [?x|?xs] &
(succeeds ?c == 0 & ?l2 = ?remSubset \/
fails ?c == 0 & ?l2 = [?x|?remSubset]) &
succeeds form2(?cs,?xs,?remSubset))
Yes
?- def(succeeds form3(?m,?l1,?l2)).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
?m = [] & ?l1 = [] & ?l2 = [] \/
(ex [c,cs,x,xs,remSubset]: ?m = [?c|?cs] & ?l1 = [?x|?xs] &
(succeeds ?c == 0 & ?l2 = ?remSubset \/
succeeds ?c == 1 & ?l2 = [?x|?remSubset]) &
succeeds form3(?cs,?xs,?remSubset))
because this pinpoints so nicely the difference between form2 and
form3.
Neither XSB nor Yap had any difficulty handling the largest
input lists that I tested (20 elements) using any combination of
these three forms, but SWI-Prolog (which is what I had been
using when I posted my previous question) seemed to have a
definite preference for the if-then-else form (i.e., it rather
quickly ran out of local stack otherwise).
After reflecting on the difference between
( C = 0, ... ; C = 1, ... )
and
( C == 0, ... ; C == 1, ... )
in Prolog, and recalling the fact that ISO Prolog does not
support type definitions or sorted predicate declarations, I
come to the concluson that, other things being equal in orders
of magnitude, either form1 or form3 are preferable to form2 because
whereas form1 and form3 can succeed only if the input mask
consists exclusively of 0s and 1s, the same cannot be said
about form2.
--
BillH
%--------------------------------------------
next_s(Set) :-
make_zero(Set,Zero),
pnext_s(Zero,Set).
%--------------------------------------------
make_zero([],[]).
make_zero([_|RemSet],[0|RemZero]) :-
make_zero(RemSet,RemZero).
%--------------------------------------------
pnext_s(Mask,Set) :-
apply_mask(Mask,Set,SubSet),
test_subset(SubSet),
write('good subset:'),write(SubSet),nl,
fail.
pnext_s(Mask,Set) :-
next_mask(Mask,NextMask),
pnext_s(NextMask,Set).
%--------------------------------------------
apply_mask([],[],[]).
apply_mask([0|RemBits],[_|RemSet],SubSet
) :-
apply_mask(RemBits,RemSet,SubSet).
apply_mask([1|RemBits],[A|RemSet],[A|Rem
SubSet]) :-
apply_mask(RemBits,RemSet,RemSubSet).
%--------------------------------------------
next_mask([0|Bits],[1|Bits]).
next_mask([1|Bits],[0|OtherBits]) :-
carry1(Bits,OtherBits).
%--------------------------------------------
carry1([0|OldBits],[1|OldBits]).
carry1([1|OldBits],[0|RemBits]) :-
carry1(OldBits,RemBits).
%--------------------------------------------
/*
test_subset(Set) :-
length(Set,N),
N < 3.
*/
test_subset(_).
%--------------------------------------------
====
1:28,31c
apply_mask([0|RemBits],[_|RemSet],SubSet
) :-
apply_mask(RemBits,RemSet,SubSet).
apply_mask([1|RemBits],[A|RemSet],[A|Rem
SubSet]) :-
apply_mask(RemBits,RemSet,RemSubSet).
2:28,34c
apply_mask([C|Cs],[X|Xs],Subset) :-
(C == 1 ->
Subset = [X|RemSubset]
;
Subset = RemSubset
),
apply_mask(Cs,Xs,RemSubset).
3:28,31c
apply_mask([C|Cs],[X|Xs],Subset) :-
( C == 1, Subset = [X|RemSubset] ;
C == 0, Subset = RemSubset),
apply_mask(Cs,Xs,RemSubset).
====
1:35,37c
next_mask([0|Bits],[1|Bits]).
next_mask([1|Bits],[0|OtherBits]) :-
carry1(Bits,OtherBits).
2:38,44c
next_mask([B|Bits],NewMask) :-
(B == 0 ->
NewMask = [1|Bits]
;
NewMask = [0|OtherBits],
carry1(Bits,OtherBits)
).
3:35,37c
next_mask([B|Bits],NewMask) :-
( B == 0, NewMask = [1|Bits] ;
B == 1, NewMask = [0|OtherBits], carry1(Bits,OtherBits) ).
====
1:41,43c
carry1([0|OldBits],[1|OldBits]).
carry1([1|OldBits],[0|RemBits]) :-
carry1(OldBits,RemBits).
2:48,54c
carry1([B|OldBits],NewBits) :-
( B == 0 ->
NewBits = [1|OldBits]
;
NewBits = [0|RemBits],
carry1(OldBits,RemBits)
).
3:41,43c
carry1([B|OldBits],NewBits) :-
( B == 0, NewBits = [1|OldBits] ;
B == 1, NewBits = [0|RemBits], carry1(OldBits,RemBits) ).
[end]
| |
| student 2005-04-09, 8:57 am |
| >
> Neither XSB nor Yap had any difficulty handling the largest
> input lists that I tested (20 elements) using any combination of
> these three forms, but SWI-Prolog (which is what I had been
> using when I posted my previous question) seemed to have a
> definite preference for the if-then-else form (i.e., it rather
> quickly ran out of local stack otherwise).
>
Correction: Both XSB and Yap terminate correctly when n=18
but XSB takes approx. an order of magnitude more time than Yap.
| |
| Bart Demoen 2005-04-10, 8:58 pm |
| student wrote:
[color=darkred]
Your next_mask is already infinitely better than my next_descr, but
before I delve more deeply into this, can I ask you this:
The first fact for carry1/2 seems subsumed by the second fact - why not
replace both by the one fact
carry1([0|R],[1|R]).
?
With that change, the clauses for next_mask and carry1 look very alike.
Why not the following def for next_mask/2:
next_mask([0|Bits],[1|Bits]).
next_mask([1|Bits],[0|OtherBits]) :-
next_mask(Bits,OtherBits).
Cheers
Bart Demoen
|
|
|
|
|