Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Algorithm for deriving permutations
Replies: 26   Last Post: Oct 21, 2007 2:16 PM

 Messages: [ Previous | Next ]
 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 4-digit base 6 numbers.
>
> base10: 1000 base6: 4344
> But...
> base6: 4344 is the 785th 4-digit base 6 number
> The 1000th 4-digit base 6 number...
> ...is 5343.
>
> base10: 1100 base6: 5032
> But...
> base6: 5032 is the 885th 4-digit base 6 number
> The 1100th 4-digit 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 4-digit 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 (polyforms-subscr...@egroups.com)- Hide quoted text -

>
> > - Show quoted text -

Date Subject Author
10/18/07 Water Cooler v2
10/18/07 Randy Poe
10/18/07 Water Cooler v2
10/18/07 hardwidg
10/18/07 Richard Heathfield
10/18/07 Proginoskes
10/18/07 Robert Israel
10/18/07 Proginoskes
10/19/07 David Bernier
10/19/07 Richard Heathfield
10/18/07 Randy Poe
10/19/07 David Breton
10/19/07 Proginoskes
10/19/07 Richard Harter
10/19/07 Marshall
10/19/07 Patricia Shanahan
10/18/07 briggs@encompasserve.org
10/18/07 Patrick Hamlyn
10/19/07 mensanator
10/19/07 hagman
10/19/07 Patrick Hamlyn
10/19/07 Richard Heathfield
10/19/07 mensanator
10/19/07 rossum
10/20/07 Grouchy