|
Hi
I would like to work out that combination of a set of specified items whose total weight will be closest to 16.50 kg. (from the example data set, syntax below, weight is in kg). Any number of combinations can be used. I think the hard part is working out all possible combinations, and collating them into a data set; once that bit is done it is easy to clean out duplicates, and figure out the total weight for each combination, and then get the closest ones. Clearly this is a combinatorial problem and I have looked at Raynald Levesqueâs macro * !combine* from Aug 30, 2001 - http://pages.infinit.net/rlevesqu/Syntax/Combinations/FindAllCombinationsOf NitemsOutOfMitems.txt - that macro is I think mainly designed to work our combinations of strings. I can see how in principle it might be adapted, but I wondered if anyone can think of a better solution? Thanks Clive. * syntax to create sample data. * ----------------------------. DATA LIST FREE/ item(A15) weight. BEGIN DATA shoes 3.00 watch 0.25 book 1.00 fridge 15.00 toaster 4.50 END DATA. DATASET NAME picklist. ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Hi
Thanks to the Lister who pointed out (off-list)that the problem outlined is similar to the well-known 'knapsack' scenario in combinatorial optimisation (and for which there are solutions available in Python). I did email a reply directly to you, but it seems your in-box is full! Clive. ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
In reply to this post by Clive Downs
Clive Downs wrote:
> I would like to work out that combination of a set of specified items > whose total weight will be closest to 16.50 kg. (from the example data > set, syntax below, weight is in kg). > > Any number of combinations can be used. I think the hard part is working > out all possible combinations, and collating them into a data set; once > that bit is done it is easy to clean out duplicates, and figure out the > total weight for each combination, and then get the closest ones. > > Clearly this is a combinatorial problem and I have looked at Raynald > Levesque’s macro * !combine* from Aug 30, 2001 - > > http://pages.infinit.net/rlevesqu/Syntax/Combinations/FindAllCombinationsOf > NitemsOutOfMitems.txt > > - that macro is I think mainly designed to work our combinations of > strings. I can see how in principle it might be adapted, but I wondered if > anyone can think of a better solution? > > Although You have already been given an offline solution, I couldn't resist trying mine. Perhaps I have over simplified the problem, since I am not really sure whether a certain item can appear more than one time or not. HTH, Marta GG DATA LIST FREE/ item(A15) weight. BEGIN DATA shoes 3.00 watch 0.25 book 1.00 fridge 15.00 toaster 4.50 END DATA. DATASET NAME picklist. MATRIX. GET PickName /VAR=item. GET PickWght /VAR=weight. COMPUTE nx=NROW(PickWght ). COMPUTE subset={0;1}. COMPUTE nsub=NROW(subset). LOOP i=2 TO nx. /* Expanding array to nx variables by recursive duplication *. . COMPUTE subset={MAKE(nsub,1,0),subset;MAKE(nsub,1,1),subset}. . COMPUTE nsub=NROW(subset). END LOOP. COMPUTE Weights=ABS(subset*PickWght-16.5). PRINT {subset,Weights} /FORMAT='F8.1' /CNAMES=PickName /TITLE='Items included (0=No; 1=Yes) and ABS(diff) from 16.5 Kg'. COMPUTE Sweights=Weights. COMPUTE Sweights(GRADE(Weights))=Weights. COMPUTE SubSort=Subset. COMPUTE Subsort(GRADE(Weights),:)=subset. PRINT {Subsort,Sweights} /FORMAT='F8.1' /CNAMES=PickName /TITLE='Items included (0=No; 1=Yes) and ABS(diff) from 16.5 Kg - sorted'. END MATRIX. -- For miscellaneous SPSS related statistical stuff, visit: http://gjyp.nl/marta/ ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
In reply to this post by Clive Downs
Hi Marta,
Thank you - I'm glad you were tempted! I've tried your solution and it works fine. Great! I don't think you oversimplified the problem. I'll have to try to learn a bit more about SPSS matrix language. No, I didn't envisage that an item could appear more than once - because the scenario I had in mind was one where you have to decide what items to 'pack' in your 'car'. I'm not sure if you will be able to resist trying a SPSS/matrix (non- python) solution to the 'knapsack' problem itself? I guess it would entail more dimensions of matrices? Regards, Clive ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Clive Downs wrote:
> Thank you - I'm glad you were tempted! > > I've tried your solution and it works fine. Great! > > I don't think you oversimplified the problem. I'll have to try to learn a > bit more about SPSS matrix language. > Just in case, I'd like to mention that if you plan to expand the problem to more than 40 items, the syntax will need modification (SET MXLOOPS=nnn, where nnn is, at least, equal to the number of items to be combined). > No, I didn't envisage that an item could appear more than once - because > the scenario I had in mind was one where you have to decide what items > to 'pack' in your 'car'. > > I'm not sure if you will be able to resist trying a SPSS/matrix (non- > python) solution to the 'knapsack' problem itself? I guess it would entail > more dimensions of matrices? > I must confess my ignorance on the topic... and the word itself ("knapsack"), because English is not my native tongue (I'll go to the Free Dictionary later to learn about it). If you provide some good documentation/examples, I might be tempted indeed. Best regards, Marta -- For miscellaneous SPSS related statistical stuff, visit: http://gjyp.nl/marta/ ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
In reply to this post by Clive Downs
Hi,
Knapsack (or 'back pack') basically means a bag that you can wear (eg on your back) and you use to carry things you need(eg food, drinks, maps, notebook) perhaps if you were on a walking holiday. As I understand the problem, (possibly simplifying it) there is an additional element, as each item has a value; further, you have two objectives, (1) total weight must be below a specified limit (2) the total value is as great as possible. Apparently the problem is similar to situations in cryptography, and combinatorics. Looking at it naively, would you just work out all the weight combinations, and then calculate the total value for each - or is that too simple? I suppose an example dataset (with arbitrary values) would be: DATA LIST FREE/ item(A15) weight value. BEGIN DATA shoes 3.00 10.0 watch 0.25 25.0 book 1.00 0.5 satnav 3.00 30.0 toaster 4.50 2.5 pen 0.75 15.0 phone 0.75 15.5 penknife 1.25 6.5 END DATA. DATASET NAME picklist. where you have to keep the weight below 5.5 kg. Regards, Clive. ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Hi Clive:
Does it look close to the goal? (weight<5.5 Kg and maximum value): DATA LIST FREE/ item(A15) weight value. BEGIN DATA shoes 3.00 10.0 watch 0.25 25.0 book 1.00 0.5 satnav 3.00 30.0 toaster 4.50 2.5 pen 0.75 15.0 phone 0.75 15.5 penknife 1.25 6.5 END DATA. DATASET NAME picklist. * Create all combinations with MATRIX *. DATASET DECLARE Knapsacks. MATRIX. GET PickName /VAR=item. GET Pick /VAR=Weight Value /NAMES=VNames. * Generating all combinations *. COMPUTE nx=NROW(Pick). COMPUTE subset={0;1}. COMPUTE nsub=NROW(subset). LOOP i=2 TO nx. /* Expanding array to nx variables by recursive duplication *. . COMPUTE subset={MAKE(nsub,1,0),subset;MAKE(nsub,1,1),subset}. . COMPUTE nsub=NROW(subset). END LOOP. COMPUTE Results=subset*Pick. * Export results to SPSS dataset *. COMPUTE AllData={subset,Results}. COMPUTE VarNames={T(PickName),VNames}. SAVE AllData /OUTFILE='Knapsacks' /NAMES=VarNames. END MATRIX. * Process all combinations to eliminate those with weight GE 5.5 *. DATASET ACTIVATE Knapsacks. FORMAT ALL (F8) weight (F8.2) value (F8.1). VALUE LABEL ALL 0' ' 1'X'/weight value 0'' 1''. SELECT IF (weight LT 5.5) AND (weight NE 0). * Sort by value *. SORT CASES BY value (D) weight (D) . SUMMARIZE /TABLES=all /FORMAT=LIST NOCASENUM TOTAL /TITLE='Knapsacks with weight<5.5 kg & sorted by value' /MISSING=VARIABLE /CELLS=NONE. Best regards, Marta GG Clive Downs escribió: > Hi, > > Knapsack (or 'back pack') basically means a bag that you can wear (eg on > your back) and you use to carry things you need(eg food, drinks, maps, > notebook) perhaps if you were on a walking holiday. > > As I understand the problem, (possibly simplifying it) there is an > additional element, as each item has a value; further, you have two > objectives, (1) total weight must be below a specified limit (2) the total > value is as great as possible. > > Apparently the problem is similar to situations in cryptography, and > combinatorics. Looking at it naively, would you just work out all the > weight combinations, and then calculate the total value for each - or is > that too simple? > > I suppose an example dataset (with arbitrary values) would be: > > > DATA LIST FREE/ item(A15) weight value. > BEGIN DATA > > shoes 3.00 10.0 > watch 0.25 25.0 > book 1.00 0.5 > satnav 3.00 30.0 > toaster 4.50 2.5 > pen 0.75 15.0 > phone 0.75 15.5 > penknife 1.25 6.5 > END DATA. > DATASET NAME picklist. > > > where you have to keep the weight below 5.5 kg. > For miscellaneous SPSS related statistical stuff, visit: http://gjyp.nl/marta/ ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Marta,
I've kind of been waiting for you to post a solution since I figured the problem was particularly well suited to using the matrix command subset and you are skilled with that command set. But I have a question that stumped me when I tried to concoct a solution using loop. Unless I miss understand the problem, you need to consider Sum((N factorial)/(m(i) factorial)*((N-m(i)) factorial)) where i=1 to N, arrangements of objects. Those arrangements need to be enumerated so that the total weight (for a suitcase or backpack) or total cost, which is what Clive was considering, I think, can be computed. My question is how did you do build that enumerated list in your code. Gene Maguin -----Original Message----- From: SPSSX(r) Discussion [mailto:[hidden email]] On Behalf Of Marta García-Granero Sent: Friday, September 18, 2009 10:57 AM To: [hidden email] Subject: Knapsacks (was Re: Combinations) Hi Clive: Does it look close to the goal? (weight<5.5 Kg and maximum value): DATA LIST FREE/ item(A15) weight value. BEGIN DATA shoes 3.00 10.0 watch 0.25 25.0 book 1.00 0.5 satnav 3.00 30.0 toaster 4.50 2.5 pen 0.75 15.0 phone 0.75 15.5 penknife 1.25 6.5 END DATA. DATASET NAME picklist. * Create all combinations with MATRIX *. DATASET DECLARE Knapsacks. MATRIX. GET PickName /VAR=item. GET Pick /VAR=Weight Value /NAMES=VNames. * Generating all combinations *. COMPUTE nx=NROW(Pick). COMPUTE subset={0;1}. COMPUTE nsub=NROW(subset). LOOP i=2 TO nx. /* Expanding array to nx variables by recursive duplication *. . COMPUTE subset={MAKE(nsub,1,0),subset;MAKE(nsub,1,1),subset}. . COMPUTE nsub=NROW(subset). END LOOP. COMPUTE Results=subset*Pick. * Export results to SPSS dataset *. COMPUTE AllData={subset,Results}. COMPUTE VarNames={T(PickName),VNames}. SAVE AllData /OUTFILE='Knapsacks' /NAMES=VarNames. END MATRIX. * Process all combinations to eliminate those with weight GE 5.5 *. DATASET ACTIVATE Knapsacks. FORMAT ALL (F8) weight (F8.2) value (F8.1). VALUE LABEL ALL 0' ' 1'X'/weight value 0'' 1''. SELECT IF (weight LT 5.5) AND (weight NE 0). * Sort by value *. SORT CASES BY value (D) weight (D) . SUMMARIZE /TABLES=all /FORMAT=LIST NOCASENUM TOTAL /TITLE='Knapsacks with weight<5.5 kg & sorted by value' /MISSING=VARIABLE /CELLS=NONE. Best regards, Marta GG Clive Downs escribió: > Hi, > > Knapsack (or 'back pack') basically means a bag that you can wear (eg on > your back) and you use to carry things you need(eg food, drinks, maps, > notebook) perhaps if you were on a walking holiday. > > As I understand the problem, (possibly simplifying it) there is an > additional element, as each item has a value; further, you have two > objectives, (1) total weight must be below a specified limit (2) the total > value is as great as possible. > > Apparently the problem is similar to situations in cryptography, and > combinatorics. Looking at it naively, would you just work out all the > weight combinations, and then calculate the total value for each - or is > that too simple? > > I suppose an example dataset (with arbitrary values) would be: > > > DATA LIST FREE/ item(A15) weight value. > BEGIN DATA > > shoes 3.00 10.0 > watch 0.25 25.0 > book 1.00 0.5 > satnav 3.00 30.0 > toaster 4.50 2.5 > pen 0.75 15.0 > phone 0.75 15.5 > penknife 1.25 6.5 > END DATA. > DATASET NAME picklist. > > > where you have to keep the weight below 5.5 kg. > For miscellaneous SPSS related statistical stuff, visit: http://gjyp.nl/marta/ ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Gene Maguin wrote:
> > I've kind of been waiting for you to post a solution since I figured the > problem was particularly well suited to using the matrix command > subset and > you are skilled with that command set. But I have a question that > stumped me > when I tried to concoct a solution using loop. Unless I miss > understand the > problem, you need to consider Sum((N factorial)/(m(i) factorial)*((N-m(i)) > factorial)) where i=1 to N, arrangements of objects. Those > arrangements need > to be enumerated so that the total weight (for a suitcase or backpack) or > total cost, which is what Clive was considering, I think, can be computed. > My question is how did you do build that enumerated list in your code. Hi Gene: This little piece of code does the trick: COMPUTE nx=NROW(Pick). COMPUTE subset={0;1}. COMPUTE nsub=NROW(subset). LOOP i=2 TO nx. . COMPUTE subset={MAKE(nsub,1,0),subset;MAKE(nsub,1,1),subset}. . COMPUTE nsub=NROW(subset). END LOOP. Explanation: A) First step (for the first item), just before the loop. "COMPUTE subset={0;1}." creates a small vector with these two values: 0 1 B) Now the loop begins, and cycles from the second to the last item: B1) Result after the first cycle (i=2): This step: "COMPUTE subset={MAKE(nsub,1,0),subset;MAKE(nsub,1,1),subset}." creates the following matrix: 0 0 0 1 1 0 1 1 As you can see, the small (0,1) vector is stacked twice, and a column is added at the left with the values (0,0,1,1). The number of 0s or 1s is fixed by the value stored in the previous "COMPUTE nsub=NROW(subset). " B2) Result after the i=3: 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Again, the result after the previous loop is stacked twice, and a pattern of 0 and 1 is created at the first column, with the number of 0s and 1s fixed by the new value stored in "nsub" (see the second "COMPUTE nsub=NROW(subset)." right before the end loop). . . . C) After the last loop, we have as many columns as items, and as many rows as every possible combinations of 0s and 1s. I hope the explanation is clear (I'm not really sure myself...). Best regards, Marta -- For miscellaneous SPSS related statistical stuff, visit: http://gjyp.nl/marta/ ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Thanks, Marta.
While I have to look over your explanation and code, the example also revealed to me how simple the problem actually was. Knowing that Sum((N factorial)/(m(i) factorial)*((N-m(i) factoral), i=1,m equals ((2**N)-1) Makes every thing fall out very simply. Always good to learn something. Gene ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
In reply to this post by Clive Downs
Hi All,
I have a script file that includes some macros to start up when SPSS is open (version 12). Could anyone please tell me a script (*.sbs) that can help create a file from a variable. The equipvalent SPS syntax is: "write outfile 'c:\new-file.txt' / candidate_name." I know I can add something like{strCmd = strCmd & "-----syntax----" & vbCrLf} to get the sps file to run as a script but I wish to have a REAL script that can do the job. Thank you so much! Robert ===================== To manage your subscription to SPSSX-L, send a message to [hidden email] (not to SPSSX-L), with no body text except the command. To leave the list, send the command SIGNOFF SPSSX-L For a list of commands to manage subscriptions, send the command INFO REFCARD |
|
Hi there!
I don't understand your problem mate. Please explain your problem a little bit more in detail. All the best Wilhelm Landerholm Queue/STATB BOX 92 162 12 Vallingby Sweden +46-735-460000 http://www.qsweden.com http://www.statb.com QUEUE - your partner in data analysis, data modeling and data mining. STATB - your Research agency. 2009/9/23 Thien Hop <[hidden email]> Hi All, |
|
Sorry for not making it clear enough!
I want to have a script (*.sbs) that can save a
variable [candidate_name] into a
file (new-file.txt). ie.
Sub
Main
xxx xxx
xxx
End Sub
Hope this clarifies. Thanks
a lot,
Robert
|
|
Something like this:
Option Explicit Dim DataDoc As ISpssDataDoc Dim objSPSSInfo As ISpssInfo,ValueLabels() Dim ss, dd, uu As String Dim NumVars, i As Long Sub Main Set objSPSSInfo = objSpssApp.SpssInfo Set DataDoc = objSpssApp.Documents.GetDataDoc(0) NumVars=objSPSSInfo.NumVariables-1 dd = InputBox("Name") If Len(dd) = 0 Then Exit Sub ss = "" For i=0 To NumVars If InStr(LCase(objSPSSInfo.VariableAt(i)),LCase(dd)) > 0 Then ss = ss & objSPSSInfo.VariableAt(i) & " " End If Next i If Len(ss) > 0 Then uu = "Write OUTFILE='C:\Users\Landerholm\Documents\" & dd & ".dat' TABLE /" & ss & "." & vbCrLf & "Execute." objSpssApp.ExecuteCommands(uu,True ) Else MsgBox "Can not find varible(s) including " & dd End If End Sub All the best Wilhelm Landerholm Queue/STATB BOX 92 162 12 Vallingby Sweden +46-735-460000 http://www.qsweden.com http://www.statb.com QUEUE - your partner in data analysis, data modeling and data mining. STATB - your Research agency. 2009/9/24 Thien Hop <[hidden email]>
|
| Free forum by Nabble | Edit this page |
