Date: Oct 18, 2007 11:55 AM
Author: briggs@encompasserve.org
Subject: Re: Algorithm for deriving permutations
In article <1192721177.652066.238430@v23g2000prn.googlegroups.com>, Randy Poe <poespam-trap@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