
Re: Algorithm for deriving permutations
Posted:
Oct 19, 2007 12:27 AM


>On 18 Oct 2007, wtr_clr@yahoo.com wrote: > >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.
One way to handle a variable number of for loops is to use an array. Something like this:
int n_boxes = 60; int n_fruits = 255; int[] counter = int[n_boxes]
for (int i=0; i<n_boxes; i++) counter[i] = 1
do for (int i=0; i<n_boxes; i++) print name_of(counter[i]); while (next(counter))
boolean next(counter) int i; for (i=0; i<n_boxes; i++) if (counter[i] < n_fruits) counter[i]++; break;
if (i == n_boxes) return false
for (int j=i1; j>=0; j) if (counter[j] == n_fruits) counter[j] = 1 else break;
return true;
I'm not sure if the above next function does what you need (fixing it is left as an exercise blah, blah, blah) but basically think of 'counter' as a number in base n_fruits. Initialize 'counter' to 1 and increment it by one until you reach n_fruits^n_boxes. Since this is an iterative method, it is somewhat more scalable than a recursive solution. Also you don't have to convert numbers back and forth between different basis, which can become an expensive calculation. As others have noted, for some values of n_boxes and n_fruits the loop may take a while to execute.
David  Send complain to /dev/null

