hagman
Posts:
1,923
Registered:
1/29/05


Re: Algorithm for deriving permutations
Posted:
Oct 19, 2007 3:11 AM


On 19 Okt., 07:24, "mensana...@aol.com" <mensana...@aol.com> wrote: > On Oct 18, 10:53?pm, Patrick Hamlyn <p...@multipro.N_OcomSP_AM.au> > wrote: > > > > > Water Cooler v2 <wtr_...@yahoo.com> wrote: > > > >If you have, say, 4 boxes to put the following 6 types of things in: > > > >Apples > > >Oranges > > >Pears > > >Bananas > > >Gooseberry > > >Lemon > > > >Such that you could: > > > >a) only put one piece of each of the things in one box; and > > > >b) you could put the same thing in all the boxes, i.e you could put, > > >say, an apple each in each of the boxes. In the mathematical jargon, > > >if repetition was allowed > > > >Then, I know that we could have 6*6*6*6, i.e 1296 permutations. > > > >However, I want to know the algorithm to decide what those > > >combinations are. Help appreciated. > > > I've seen a bunch of algorithms posted, whether loops or recursions, but you > > don't need any of those. > > > Simply represent each box by a digit in a number in base 6. > > > Now each combination is numbered. If you want the 1000th combination, you can > > generate it directly by converting 1000 to base 6. The nth digit gives the nth > > bin's contents. > > But that includes ALL combinations. Sounds more > like th OP wants the 1000th combination of just > the 4digit base 6 numbers. > > base10: 1000 base6: 4344 > But... > base6: 4344 is the 785th 4digit base 6 number > The 1000th 4digit base 6 number... > ...is 5343. > > base10: 1100 base6: 5032 > But... > base6: 5032 is the 885th 4digit base 6 number > The 1100th 4digit base 6 number... > ...does not exist, there are only 1080 of them. >
0 is a digit (or apples are fruit if you prefer). Thus 4344 is the 1000th 4digit base 6 number (with leading zeroes), 5032 is the 1100th and there are 1296 of them.
> > > > The same works for 1000000 types of object in 1000000 bins. The arithemetic is > > more tedious and the numbers larger, but you can still produce the Xth > > combination directly without loops. > >  > > Patrick Hamlyn posting from Perth, Western Australia > > Windsurfing capital of the Southern Hemisphere > > Moderator: polyforms group (polyformssubscr...@egroups.com) Hide quoted text  > > >  Show quoted text 

