BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Need help with an algorithm Goto page 1, 2  Next          BorlandTalk.com Forum Index -> comp.lang.pascal.delphi.misc View previous topic :: View next topic   Author Message F2S Newsgroups Guest Posted: Fri Feb 18, 2005 8:00 am    Post subject: Need help with an algorithm Hello group I'm very poor with numbers, so I'd appreciate some help! Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? Many thanks in advance Back to top J French Guest Posted: Fri Feb 18, 2005 8:31 am    Post subject: Re: Need help with an algorithm On Fri, 18 Feb 2005 08:00:25 -0000, "F2S Newsgroups" <na (AT) not_an_address (DOT) com> wrote: Quote: Hello group I'm very poor with numbers, so I'd appreciate some help! Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? It sounds as if you want to test the bits in a 'number' A byte looks like: [128][64][32][16][8][4][2][1] procedure TForm1.Button1Click(Sender: TObject); Var I :Integer; begin I := 21; If ( I And 4 ) = 4 Then ShowMessage( '4 is used' ); end; Back to top Nico de Jong Guest Posted: Fri Feb 18, 2005 8:45 am    Post subject: Re: Need help with an algorithm "F2S Newsgroups" <na (AT) not_an_address (DOT) com> skrev i en meddelelse news:cv478v$rro$1 (AT) news (DOT) freedom2surf.net... Quote: Hello group I'm very poor with numbers, so I'd appreciate some help! Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? The way I see it, it is an ideal job for logical operator AND and for SHL (shift left) The following code works for the range 1 - 512 Nico procedure TForm1.FormCreate(Sender: TObject); var i, number : integer; str1, str2 : string; begin number := 21; str2 := ''; i := 1; while i < 1024 do (* identical to twice the rane you need, withing the limits of an integer *) begin if (number and i) <> 0 then begin str(i,str1); str2 := str2 + str1 + ' - '; end; i := i shl 1; end; application.messagebox(pchar(str2),'Result',mb_ok); end; Back to top alanglloyd@aol.com Guest Posted: Fri Feb 18, 2005 2:17 pm    Post subject: Re: Need help with an algorithm If you are working with less than 32 bits then use a set of enumerated values. Enumerated values are constants starting at zero and defined with meaningful names as follows : TAutoPaste = (apNone, apCopyName, apSwapNames); Note the convention of type initials (ap) as prefix.These enumerated values would have values of 0, 1 & 2. Extend the list of enumerated values as necessary up to 32 values. A set of this enumerated value is declared as : TAutoPasteSet = set of TAutoPaste; This is implemented by Delphi as a value with appropriate bits set for the presence in the set of any of the values. If you have a number then one could typecast the number to the set and test for any item in it. MyNum := 5; if (apSwapNames in TAutoPasteSet(MyNum)) then etc, etc {bit 2 is set in MyNum} Note that MyNum must be an appropriate type - byte if up to 8 enumerated values and bits in the number. word if 9 - 16 enum values, integer if 17 - 32 enum values. You can use any set operator with sets - "in", "=", ">=" (contains), "<=" (is contained in), "+" (union), "-"(difference), "*" (intersection). Alan Lloyd Back to top Ed Guest Posted: Fri Feb 18, 2005 2:37 pm    Post subject: Re: Need help with an algorithm Quote: So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? Bitwise AND. Back to top Hanford Carr Guest Posted: Fri Feb 18, 2005 3:24 pm    Post subject: Re: Need help with an algorithm F2S Newsgroups wrote: Quote: Hello group I'm very poor with numbers, so I'd appreciate some help! Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? Many thanks in advance type tset = set of 0..63 var i: int64; k: integer; begin i := 21; // i is stored in binary // what powers of 2 are in this number? for k := 0 to 62 do begin if ( k in tset (i) ) then write (pwr2 (k),' is in number') //where pwr2 is a function raising 2 to the // k'th power else write (pwr2 (k), ' is not in number'); end ; end. Back to top NA Guest Posted: Fri Feb 18, 2005 6:36 pm    Post subject: Re: Need help with an algorithm Many thanks for all of the suggestions everyone, you've been a tremendous help "F2S Newsgroups" <na (AT) not_an_address (DOT) com> wrote Quote: Hello group I'm very poor with numbers, so I'd appreciate some help! Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? Many thanks in advance Back to top Jud McCranie Guest Posted: Fri Feb 18, 2005 7:05 pm    Post subject: Re: Need help with an algorithm On Fri, 18 Feb 2005 08:00:25 -0000, "F2S Newsgroups" <na (AT) not_an_address (DOT) com> wrote: Quote: So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? All you have to do i use the binary representation, and the least significant bit corresponds to 1, the next one corresponds to 2, etc. Use bitwise operations to do the inquiry. --- Replace you know what by j to email Back to top Dr John Stockton Guest Posted: Fri Feb 18, 2005 9:44 pm    Post subject: Re: Need help with an algorithm JRS: In article <cv478v$rro$1 (AT) news (DOT) freedom2surf.net>, dated Fri, 18 Feb 2005 08:00:25, seen in news:comp.lang.pascal.delphi.misc, F2S Newsgroups <na (AT) not_an_address (DOT) com> posted : Quote: Given a sequence of numbers that are powers of 2 - 1, 2, 4, 8, 16, and so on (I'll be dealing with a pretty short range), I'm aware that any specific combination of those numbers will be unique - no other combination of different numbers from the same range will match the same total. I need to determine whether, if I've got a computed total, a particular number in the sequence was included in the elements that were combined to give its value. So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Any elegant solutions? Please set your right margin to about 72 characters when posting. You ask for an elegant solution, and have been given inelegant ones. Assume for this that the number is word-sized - 16-bit. type TS = set of 0..15 ; var N : word ; { the number in question } var S : TS ; for k := 0 to 15 do begin S := TS(N) ; Exclude(S, k) ; d := N - word(S) ; if d<>0 then Writeln(d, ' present') ; end {k} ; Note that the casts generate no code; and Exclude generates little. -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Delphi 3 Turnpike 4 © <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links; <URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ; <URL:http://www.borland.com/newsgroups/guide.html> news:borland.* Guidelines Back to top Martin Harvey (Demon acco Guest Posted: Sat Feb 19, 2005 12:00 am    Post subject: Re: Need help with an algorithm On Fri, 18 Feb 2005 08:00:25 -0000, "F2S Newsgroups" <na (AT) not_an_address (DOT) com> wrote: Quote: So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' var Combined: integer; Part: integer; Idx: integer; begin Part := 1; for Idx := 1 to 31 do begin if (Part and Combined) <> 0 then ShowMessage(IntToStr(Part) + ' was used in reaching ' + InttoStr(Combined); Part := Part shl 1; end; end; MH. Back to top Jud McCranie Guest Posted: Sat Feb 19, 2005 3:24 am    Post subject: Re: Need help with an algorithm On Sat, 19 Feb 2005 00:41:58 GMT, "Martin Harvey (Demon account)" <martin (AT) nospam_pergolesi (DOT) demon.co.uk> wrote: Quote: All the engineers wrote the solution with the "and" operator on integers .... and all the mathematicians use sets! Not all. I suggested integers and bit operations, and I'm a math type and not an engineer. --- Replace you know what by j to email Back to top alanglloyd@aol.com Guest Posted: Sat Feb 19, 2005 7:43 am    Post subject: Re: Need help with an algorithm Martin Harvey wrote Quote: All the engineers wrote the solution with the "and" operator on integers .... and all the mathematicians use sets! As a mathematically based engineer, the big advantage of sets is code clarioty, No one has to say "I had to think quite hard about how this works ". Had JS made full use of sets he might have coded ... Str := ''; for i := 0 to 15 do begin if i in TS(N) then Str := Str + IntToStr(i) + ', '; if Str <> '' then SetLength(Str, Length(Str) - 2); ShowMessage('[' + Str + ']'); Of course its slower, but who cares and its obvious code. If the values in the sets had meaning and an enumerated type was used, the readability would be even more obvious because of the absence of "magic numbers". If JS (or the "engineers") had to test if a multibit set was in N then the difference would be even more apparent. Try coding a test for 3, 6, 7, 8 in the set. Using set operators that reduces to a single line of code. Alan Lloyd [email]alanglloyd (AT) aol (DOT) com[/email] Back to top Dr John Stockton Guest Posted: Sat Feb 19, 2005 8:49 pm    Post subject: Re: Need help with an algorithm JRS: In article <1108799033.150745.294130 (AT) o13g2000cwo (DOT) googlegroups.com> , dated Fri, 18 Feb 2005 23:43:53, seen in news:comp.lang.pascal.delphi. misc, [email]alanglloyd (AT) aol (DOT) com[/email] <alanglloyd (AT) aol (DOT) com> posted : Quote: Had JS made full use of sets he might have coded ... JRS, please, as should be sufficiently evident. JS is javascript. You are evidently AGL, and not a mere AL (though you may answer to Al) which might get confused with a '86 Register. Quote: Str := ''; for i := 0 to 15 do begin if i in TS(N) then Str := Str + IntToStr(i) + ', '; if Str <> '' then SetLength(Str, Length(Str) - 2); ShowMessage('[' + Str + ']'); But that does not give the right answer. It answers a different question. The OP wanted the powers of 2 contributed by the bits, not the indexes of the bits. Methods which just test the bits, whether with in or with and , give the indexes of the set bits; something essentially different is needed to get the values of the set bits directly. -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Delphi 3 Turnpike 4 © <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links; <URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ; <URL:http://www.borland.com/newsgroups/guide.html> news:borland.* Guidelines Back to top alanglloyd@aol.com Guest Posted: Sun Feb 20, 2005 8:46 am    Post subject: Re: Need help with an algorithm Dr John Stockton wrote: Quote: JRS: In article [email]1108799033.150745.294130 (AT) o13g2000cwo (DOT) googlegroups.com[/email] , dated Fri, 18 Feb 2005 23:43:53, seen in news:comp.lang.pascal.delphi. misc, [email]alanglloyd (AT) aol (DOT) com[/email] <alanglloyd (AT) aol (DOT) com> posted : snip Str := ''; for i := 0 to 15 do begin if i in TS(N) then Str := Str + IntToStr(i) + ', '; if Str <> '' then SetLength(Str, Length(Str) - 2); ShowMessage('[' + Str + ']'); But that does not give the right answer. It answers a different question. The OP wanted the powers of 2 contributed by the bits, not the indexes of the bits. Methods which just test the bits, whether with in or with and , give the indexes of the set bits; something essentially different is needed to get the values of the set bits directly. OK, how about ... function ShowMakeUp(N : word) : string; type TInt = 0..15; TIntSet = set of TInt; var I : TInt; ISet : TIntSet; begin Result := ''; for I := Low(TInt) to High(TInt) do begin ISet := [I] * TIntSet(N); // get intersection if ISet <> [] then // I is in N Result := Format('%s%d, ', [Result, Word(ISet)]); end; {for I := Low(TInt) to High(TInt} if Result <> '' then SetLength(Result, Length(Result) - 2); end; Alan Lloyd Back to top Jud McCranie Guest Posted: Sun Feb 20, 2005 4:30 pm    Post subject: Re: Need help with an algorithm On Fri, 18 Feb 2005 08:00:25 -0000, "F2S Newsgroups" <na (AT) not_an_address (DOT) com> wrote: Quote: So, for example, if I have '21', 16 + 4 + 1 will give this total - I want to be able to say 'was 4 used in reaching the value?' Here's the way I would do it. ------------- const HighestBit = 30; var i, x : integer; pow2 : array[ 0 .. HighestBit] of integer; begin pow2[ 0] := 1; for i := 1 to HighestBit do pow2[ i] := 2 * pow2[ i - 1]; // the above can be set up once and re-used { below shows all powers of 2 used. It could be modified to ask about only one value} x := 21; // or what ever your number is for i := 0 to HighestBit do if odd( x shr i) then // pow2[ i] is used --- Replace you know what by j to email Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> comp.lang.pascal.delphi.misc All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.