
Re: Algorithm for deriving permutations
Posted:
Oct 18, 2007 11:33 AM


On Oct 18, 4:26 pm, Randy Poe <poespamt...@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. 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, about 60. 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? 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.

