Generating ordered subsets of fixed size. Was Re: Algorithms?
in [General Programming]
|
From: Daniel Pitts on 15 Jul 2010 14:44 On 7/15/2010 8:41 AM, Frederick Williams wrote: > osmium wrote: >> >> Frederick Williams wrote: >> >>> Is there a comp dot something that deals with algorithms? And if not, >>> would it be appropriate to ask about them here? >> >> This is a good place to ask about algorithms. > > Ooh good! Then I shall: > > I have an array of 48 (ish) positive integers arranged in order of > increasing magnitude without repetitions. I wish to create all > 6-element sub-arrays maintaining the order. I think there are about 12 > million of them. My plan is to create all 5-element sub-arrays and > interpolate all single elements that don't disturb the order. And to do > that by creating all 4-element ..., etc. So, a recursive solution. My > question: is that the best way? Best probably means fastest. > > Should it be necessary to say so: no, this isn't homework. > Not sure if this will help lead to a solution, but your asking basically for "all 48bit numbers which have exactly 6 bits on" Sounds kind of like a combinatorial problem to me. Find all permutations of 6 1's and 42 0's. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Ben Bacarisse on 15 Jul 2010 17:23 Frederick Williams <frederick.williams2(a)tesco.net> writes: > Ben Bacarisse wrote: <snip> >> Do you need them all in storage? Can you use some indirect >> representation (for example a 64-bit word with 6 bits set)? In short, >> what are generating them for? > > 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. Hmm... Something is wrong here. Your example (227, 223, 211, 199, 197, 193) does not meet this condition unless I've misunderstood or miscalculated something. The "smallest" solution (with non-consecutive primes) that I can find is 109, 89, 79, 73, 71, 67. > (Yes, I am aware that there is a lot of redundancy there). The post > where the question is raised is at > news:3bfb7912-1818-4d86-a45d-661fefc9e226(a)s9g2000yqd.googlegroups.com. -- Ben.
From: Frederick Williams on 15 Jul 2010 17:40 Ben Bacarisse wrote: > > Frederick Williams <frederick.williams2(a)tesco.net> writes: > > > Ben Bacarisse wrote: > <snip> > >> Do you need them all in storage? Can you use some indirect > >> representation (for example a 64-bit word with 6 bits set)? In short, > >> what are generating them for? > > > > 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. > > Hmm... Something is wrong here. Your example (227, 223, 211, 199, 197, > 193) does not meet this condition unless I've misunderstood or > miscalculated something. Don't worry, it's probably I who haven't translated the above into C correctly. > The "smallest" solution (with non-consecutive primes) that I can find is > 109, 89, 79, 73, 71, 67. I get (using James Dow Allen's code) 31, 29, 11, 5, 3, 2; so it's probably I who's made the mistake. I haven't checked 227, 223, 211, 199, 197, 193 or 31, 29, 11, 5, 3, 2 "by hand". Your 109, 89, 79, 73, 71, 67 is in my list of (supposedly) all candidates up to 227. -- I can't go on, I'll go on.
From: Ben Bacarisse on 15 Jul 2010 18:01 Frederick Williams <frederick.williams2(a)tesco.net> writes: > Ben Bacarisse wrote: >> >> Frederick Williams <frederick.williams2(a)tesco.net> writes: >> >> > Ben Bacarisse wrote: >> <snip> >> >> Do you need them all in storage? Can you use some indirect >> >> representation (for example a 64-bit word with 6 bits set)? In short, >> >> what are generating them for? >> > >> > 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. >> >> Hmm... Something is wrong here. Your example (227, 223, 211, 199, 197, >> 193) does not meet this condition unless I've misunderstood or >> miscalculated something. > > Don't worry, it's probably I who haven't translated the above into C > correctly. > >> The "smallest" solution (with non-consecutive primes) that I can find is >> 109, 89, 79, 73, 71, 67. > > I get (using James Dow Allen's code) 31, 29, 11, 5, 3, 2; so it's > probably I who's made the mistake. It looks like some part of your code is wrong because that does not match the condition either. > I haven't checked 227, 223, 211, > 199, 197, 193 or 31, 29, 11, 5, 3, 2 "by hand". Presumably you have some code to check the condition! The list of pairwise > Your 109, 89, 79, 73, > 71, 67 is in my list of (supposedly) all candidates up to 227. Ah. That made me check. I was not printing the smallest. The smallest I find is: 89, 41, 29, 23, 19, 17. -- Ben.
From: Frederick Williams on 15 Jul 2010 18:47 Ben Bacarisse wrote: > > [...] The smallest > I find is: 89, 41, 29, 23, 19, 17. My code was wrong, I now get 89, 41, 29, 23, 19, 17 too. Phew. -- I can't go on, I'll go on.
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 Prev: Algorithms? Next: Generating ordered subsets of fixed size. Was Re: Algorithms? |