
Re: Algorithm for deriving permutations
Posted:
Oct 18, 2007 11:53 PM


Water Cooler v2 <wtr_clr@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.
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 (polyformssubscribe@egroups.com)

