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 ]
 Randy Poe Posts: 5,658 Registered: 12/6/04
Re: Algorithm for deriving permutations
Posted: Oct 18, 2007 4:43 PM

On Oct 18, 11:33 am, Water Cooler v2 <wtr_...@yahoo.com> wrote:
> On Oct 18, 4:26 pm, Randy Poe <poespam-t...@yahoo.com> wrote:
>
>
>

> > On Oct 18, 11:05 am, 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.

>
> > for fruit1=apples to lemon
> > for fruit2=apples to lemon
> > for fruit3=apples to lemon
> > for fruit4=apples to lemon
> > print: (fruit1,fruit2,fruit3,fruit4)
> > end
> > end
> > end
> > end

>
> > Easily implemented recursively and generalized to
> > an arbitrary number of boxes if you have a
> > language that supports recursion.

>
> > - Randy
>
> Thanks very much, Randy. I already had that in mind to start off with.

Well, it did seem like kind of a simple question. You
left out the non-trivial portions. Hard to tell sometimes
whether somebody is asking a homework problem or
something more difficult.

> I thought it would be too cumbersome as in the actual problem I have
> at hand, the number of "fruits" are about 255 and the number of boxes,

So the number of combinations to generate (note:
not "permutations") is 255^60, or 2.5*10^144.

> But you've reminded me that I could use recursion, so
> thanks. Instead of the 255 for loops, I could use a recursive
> function.
>
> Just a side note, is there a more efficient algorithm than the one
> above? Will the above algorithm not be too expensive for about 255
> fruits and about 60 odd boxes?

Efficient in terms of what? It doesn't seem tractable
no matter what algorithm you use if you want to
actually print 2.5*10^144 combinations, even if you
could do one iteration per femtosecond. And you'd
use an awful lot of paper, too, orders of magnitude
more than all the mass of the universe.

> That would be 255 instances of the same
> function, each with their own stack of a minimum of 60 variables, each
> doing a lot of "string concatenation", which in and of itself is very
> expensive.

Least of your problems. Finding room to print
your 2.5*10^144 lines is a bigger problem, or to
store them to file. You're going to need a bigger
disk drive, I think.

So all kidding aside, basically your problem as
stated is not possible. What are you really trying
to do?

- Randy

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