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 ]
 David Breton Posts: 2 Registered: 8/17/06
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 <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.
>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=i-1; 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

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