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


In article <1192721177.652066.238430@v23g2000prn.googlegroups.com>, Randy Poe <poespamtrap@yahoo.com> writes: > 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.
Recursive Fortran. It also tallies the total number of permutations so that you end up with a warm fuzzy fealing that the code is correct.
program main integer total / 0 / parameter boxes = 4 call permutation ( '', boxes, total ) type *, total end
options /extend_source subroutine permutation ( lhs, boxes, total ) implicit none
character *(*) lhs integer boxes integer total
integer i
character *10 fruit(6) / 'apple', 'orange', 'pear', 'banana', 1 'gooseberry', 'lemon' / static fruit
if ( boxes .eq. 0 ) then type *, lhs total = total + 1 return end if
do i = 1, 6 call permutation ( lhs // fruit(i), boxes  1, total ) end do

