Generating ordered subsets of fixed size. Was Re: Algorithms?
in [General Programming]
|
From: Tim Rentsch on 17 Jul 2010 11:42 Frederick Williams <frederick.williams2(a)tesco.net> writes: > Someone asked for six prime numbers that satisfy an arithmetic condition > part of which is that they are in order of decreasing size. I found > that the smallest six consecutive primes satisfying the condition are > > 227, 223, 211, 199, 197, 193. > > But for all I know there might be smaller non-consecutive primes that > satisfy the condition. So I am seeking all six membered subsequences of > 227, 223, 211, ..., 3, 2 so that I may test them for the condition. > > The condition is > > Primes A, B, C, D, E, F such that > > A > B > C > D > E > F > > and > > AB > AC > AD > AE > AF > > BC > BD > BE > BF > > CD > CE > CF > > DE > DF > > and > > ABC > ABD > ABE > ABF > ACD > ACE > ACF > ADE > ADF > AEF > > BCD > BCE > BCF > BDE > BDF > BEF > > CDE > CDF > CEF > > DEF. > > (Yes, I am aware that there is a lot of redundancy there). [snip] A predicate to find sublists of a list is three lines of prolog. Here is a prolog program for the whole problem (including two unnecessary lines with 'true' clauses put in to provide some visual markers, and two redundant comparison lines): s( Solution ) :- Solution = [ _, _, _, _, _, _ ], primes_under_consideration_are( Primes ), sublist_of( Solution, Primes ), meets_criteria( Solution ). sublist_of( [], [] ). sublist_of( L, [ _ | T ] ) :- sublist_of( L, T ). sublist_of( [ H | S ], [ H | T ] ) :- sublist_of( S, T ). meets_criteria( [ A, B, C, D, E, F ] ) :- % Note that A > B, B > C, etc, guaranteed by primes ordering. % AF is A * F, BC is B * C, AF > BC, BF is B * F, CD is C * D, BF > CD, CF is C * F, DE is D * E, CF > DE, true, AEF is A * E * F, BCD is B * C * D, AEF > BCD, BEF is B * E * F, CDE is C * D * E, BEF > CDE, % redundant CEF is C * E * F, DEF is D * E * F, CEF > DEF, % redundant true. primes_under_consideration_are( P ) :- P = [ 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2 ]. Finds the minimum solution in about half a second.
From: Frederick Williams on 17 Jul 2010 14:36 Tim Rentsch wrote: > > Frederick Williams <frederick.williams2(a)tesco.net> writes: > > > Someone asked for six prime numbers that satisfy an arithmetic condition > > part of which is that they are in order of decreasing size. I found > > that the smallest six consecutive primes satisfying the condition are > > > > 227, 223, 211, 199, 197, 193. > > > > But for all I know there might be smaller non-consecutive primes that > > satisfy the condition. So I am seeking all six membered subsequences of > > 227, 223, 211, ..., 3, 2 so that I may test them for the condition. > > > > The condition is > > > > Primes A, B, C, D, E, F such that > > > > A > B > C > D > E > F > > > > and > > > > AB > AC > AD > AE > AF > > > BC > BD > BE > BF > > > CD > CE > CF > > > DE > DF > > > > and > > > > ABC > ABD > ABE > ABF > ACD > ACE > ACF > ADE > ADF > AEF > > > BCD > BCE > BCF > BDE > BDF > BEF > > > CDE > CDF > CEF > > > DEF. > > > > (Yes, I am aware that there is a lot of redundancy there). [snip] > > A predicate to find sublists of a list is three lines of prolog. > Here is a prolog program for the whole problem (including two > unnecessary lines with 'true' clauses put in to provide some > visual markers, and two redundant comparison lines): > > s( Solution ) :- > Solution = [ _, _, _, _, _, _ ], > primes_under_consideration_are( Primes ), > sublist_of( Solution, Primes ), > meets_criteria( Solution ). > > sublist_of( [], [] ). > sublist_of( L, [ _ | T ] ) :- sublist_of( L, T ). > sublist_of( [ H | S ], [ H | T ] ) :- sublist_of( S, T ). > > meets_criteria( [ A, B, C, D, E, F ] ) :- > % Note that A > B, B > C, etc, guaranteed by primes ordering. > % > AF is A * F, BC is B * C, AF > BC, > BF is B * F, CD is C * D, BF > CD, > CF is C * F, DE is D * E, CF > DE, > true, > AEF is A * E * F, BCD is B * C * D, AEF > BCD, > BEF is B * E * F, CDE is C * D * E, BEF > CDE, % redundant > CEF is C * E * F, DEF is D * E * F, CEF > DEF, % redundant > true. > > primes_under_consideration_are( P ) :- > P = [ > 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, > 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, > 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, > 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, > 2 > ]. > > Finds the minimum solution in about half a second. Thank you. I know nothing about Prolog but if I can find a free compiler (or interpreter?--I told you I know nothing about Prolog) I'll try it out. -- I can't go on, I'll go on.
From: Tim Rentsch on 17 Jul 2010 15:30 Frederick Williams <frederick.williams2(a)tesco.net> writes: > Tim Rentsch wrote: >> >> Frederick Williams <frederick.williams2(a)tesco.net> writes: >> >> > Someone asked for six prime numbers that satisfy an arithmetic condition >> > part of which is that they are in order of decreasing size. I found >> > that the smallest six consecutive primes satisfying the condition are >> > >> > 227, 223, 211, 199, 197, 193. >> > >> > But for all I know there might be smaller non-consecutive primes that >> > satisfy the condition. So I am seeking all six membered subsequences of >> > 227, 223, 211, ..., 3, 2 so that I may test them for the condition. >> > >> > The condition is >> > >> > Primes A, B, C, D, E, F such that >> > >> > A > B > C > D > E > F >> > >> > and >> > >> > AB > AC > AD > AE > AF > >> > BC > BD > BE > BF > >> > CD > CE > CF > >> > DE > DF >> > >> > and >> > >> > ABC > ABD > ABE > ABF > ACD > ACE > ACF > ADE > ADF > AEF > >> > BCD > BCE > BCF > BDE > BDF > BEF > >> > CDE > CDF > CEF > >> > DEF. >> > >> > (Yes, I am aware that there is a lot of redundancy there). [snip] >> >> A predicate to find sublists of a list is three lines of prolog. >> Here is a prolog program for the whole problem (including two >> unnecessary lines with 'true' clauses put in to provide some >> visual markers, and two redundant comparison lines): >> >> s( Solution ) :- >> Solution = [ _, _, _, _, _, _ ], >> primes_under_consideration_are( Primes ), >> sublist_of( Solution, Primes ), >> meets_criteria( Solution ). >> >> sublist_of( [], [] ). >> sublist_of( L, [ _ | T ] ) :- sublist_of( L, T ). >> sublist_of( [ H | S ], [ H | T ] ) :- sublist_of( S, T ). >> >> meets_criteria( [ A, B, C, D, E, F ] ) :- >> % Note that A > B, B > C, etc, guaranteed by primes ordering. >> % >> AF is A * F, BC is B * C, AF > BC, >> BF is B * F, CD is C * D, BF > CD, >> CF is C * F, DE is D * E, CF > DE, >> true, >> AEF is A * E * F, BCD is B * C * D, AEF > BCD, >> BEF is B * E * F, CDE is C * D * E, BEF > CDE, % redundant >> CEF is C * E * F, DEF is D * E * F, CEF > DEF, % redundant >> true. >> >> primes_under_consideration_are( P ) :- >> P = [ >> 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, >> 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, >> 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, >> 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, >> 2 >> ]. >> >> Finds the minimum solution in about half a second. > > Thank you. I know nothing about Prolog but if I can find a free > compiler (or interpreter?--I told you I know nothing about Prolog) I'll > try it out. Here's a link: http://www.swi-prolog.org/download/stable Not sure if this is the same prolog interpreter that I downloaded, but they have a full complement of platforms that they support. In the prolog I run locally, I do this: $ /usr/local/bin/pl ?- ['pt.pl']. % load file containing the program % pt.pl compiled, [etc]. true. ?- s( A ). [solutions appear as output -- use ';' to get next] The ?- are prompts for input to prolog interpreter. I hope you get to try it, prolog is cool. By the way, if you do get a prolog interpreter, try this: ?- sublist_of( L, [1,2,3,4] ). (after loading the file with 'sublist_of()' in it of course). Again use ';'s to see multiple answers. That should give you a starting sense of the power of prolog. Then, what do you suppose will happen if you try this: ?- sublist_of( L, [1,2,3,4,5] ), sublist_of( L, [2,3,5,7] ). Prolog is cool. :)
First
|
Prev
|
Pages: 1 2 3 Prev: Algorithms? Next: Generating ordered subsets of fixed size. Was Re: Algorithms? |