looping through possible combinations of McNuggets packs of 6, 9 and 20

Mel mwilson at the-wire.com
Mon Aug 16 21:52:41 CEST 2010


Baba wrote:
[ ... ]
> Now, i believe that the number of consecutive passes required to make
> this work is equal to the smallest number of pack sizes. So if we have
> packs of (9,12,21) the number of passes needed would be 9 and the
> theorem would read
> 
> "If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to
> buy any number of nuggets >= 9 given that they come in packs of
> 9,12,21"

That's the proper statement.
> 
> However i turn in circles because i don't seem to get any results for
> some random pack combinations like (9,12,21) or (10,20,30).

That "if it is possible" is the big if.  If every package you can buy has a 
multiple of 3, then every possible purchase will be a multiple of 3.  
Nothing that leaves a remainder of 1 or 2 will ever show up.
> 
> The must always be a solution i'm thinking, be it the smallest pack -
> 1

The set (9/3, 12/3, 21/3) settles down pretty quickly:

>>> s = nuggets.buyable_set ((3, 4, 7))
>>> nuggets.print_from (s, xrange(20))
0	set([])
3	set([0])
4	set([0])
6	set([3])
7	set([0, 3, 4])
8	set([4])
9	set([6])
10	set([3, 6, 7])
11	set([8, 4, 7])
12	set([8, 9])
13	set([9, 10, 6])
14	set([10, 11, 7])
15	set([8, 11, 12])
16	set([9, 12, 13])
17	set([10, 13, 14])
18	set([11, 14, 15])
19	set([16, 12, 15])
>>> 

The printout here is the 'genaeology' of each purchase -- the set of smaller 
purchases from which you can reach each one.  After ...,6,7,8,... every 
larger number can be reached.

	Mel.




More information about the Python-list mailing list