Generating ordered subsets of fixed size. Was Re: Algorithms?
in [General Programming]
|
From: Frederick Williams on 15 Jul 2010 11:41 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. -- I can't go on, I'll go on.
From: S Perryman on 15 Jul 2010 12:03 Frederick Williams wrote: > 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. ARRAY = [ 1 2 3 ] 1. Form a directed graph D from ARRAY. 1 ---> 2 ---> 3 +-------------^ 2. Find all paths in D that are of length L. L = 2 gives [1,2] , [1,3] , [2,3] . Should be plenty of "all paths of length L" graph algorithms out there, for your desired prog lang. Regards, Steven Perryman
From: Ben Bacarisse on 15 Jul 2010 12:18 Frederick Williams <frederick.williams2(a)tesco.net> writes: > 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. That's certainly one way. The trouble with "fastest" is that it might depend on things that have nothing to do with the algorithm. For example, if you need to allocate storage for the 6-element lists, this allocation might dominate the execution time. 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? > Should it be necessary to say so: no, this isn't homework. -- Ben.
From: Frederick Williams on 15 Jul 2010 13:35 Ben Bacarisse wrote: > > Frederick Williams <frederick.williams2(a)tesco.net> writes: > > > 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. > > That's certainly one way. The trouble with "fastest" is that it might > depend on things that have nothing to do with the algorithm. For > example, if you need to allocate storage for the 6-element lists, this > allocation might dominate the execution time. > > 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. (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. -- I can't go on, I'll go on.
From: Niklas Holsti on 15 Jul 2010 14:03 Ben Bacarisse wrote: > Frederick Williams <frederick.williams2(a)tesco.net> writes: [ snip ] >> 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. [ 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? Those are good questions, and may be decisive for the choice of algorithm, especially if memory is tight. The simplest solution that comes to my mind is to first pick the first element of the sub-array by traversing the first 48 - 5 = 43 elements of the whole array, then recursively picking the remaining 5 elements from the rest of the whole array. That is, if the first element is picked from wholearray[i], the second element is picked from wholearray[i+1] .. wholearray[44], and so on. This algorithm generates the sub-arrays in ascending order and uses a trivial amount of memory (recursion six levels deep with a few integer variables per level). Here below is an Ada program that uses this algorithm. The example embedded in the program generates all 3-element sub-arrays of a 6-element array, and prints out: 12 41 66 12 41 71 12 41 92 12 41 99 12 66 71 12 66 92 12 66 99 12 71 92 12 71 99 12 92 99 41 66 71 41 66 92 41 66 99 41 71 92 41 71 99 41 92 99 66 71 92 66 71 99 66 92 99 71 92 99 Here is the code: with Ada.Text_IO; procedure SubArr is type Datum is new Integer; -- The type of data in our arrays. type Datum_Array is array (Positive range <>) of Datum; -- The arrays we are manipulating. procedure Generate_Subarrays ( Whole : in Datum_Array; Length : in Natural) -- Given a Whole array of Datum values, in ascending order -- with no duplication, this procedure generates all -- subarrays (subsets) of Length items in ascending order, -- selected from the Whole, with no duplication. is Subarray : Datum_Array (1 .. Length); -- The result. procedure Extend_Subarray ( From : in Positive; More : in Natural) -- Extends the Subarray with More new elements from -- the Whole array, starting at Whole(From). is begin if More = 0 then -- Nothing left to do. for S in Subarray'Range loop Ada.Text_IO.Put (Datum'Image (Subarray(S))); end loop; Ada.Text_IO.New_Line; else -- Pick the first new element of the subarray: for Next in From .. Whole'Last - More + 1 loop Subarray(Length - More + 1) := Whole(Next); -- Then pick the remaining elements: Extend_Subarray ( From => Next + 1, More => More - 1); end loop; end if; end Extend_Subarray; begin -- Generate_Subarrays Extend_Subarray ( From => Whole'First, More => Length); end Generate_Subarrays; begin -- SubArr Generate_Subarrays ( Whole => (12, 41, 66, 71, 92, 99), Length => 3); end SubArr; -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .
|
Next
|
Last
Pages: 1 2 3 Prev: Algorithms? Next: Generating ordered subsets of fixed size. Was Re: Algorithms? |