[futurebasic] Re: [FB] Permutation Challenge

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : November 2000 : Group Archive : Group : All Groups

From: Jay Reeve <jktr@...>
Date: Tue, 28 Nov 00 13:46:35 -0600
>> Here is some code that is TESTED to do what you ask:
>> '====================
>> DIM 10 gString$(3628800)
>> dim gCount as long
>> end globals
>> 
>> local fn permutations(whichChar,NextStr$ as str15)
>> dim as long d
>> long if whichChar < 10
>> fn permutations(whichChar+1,NextStr$)
>> for d = whichChar + 1 to 10
>> swap NextStr$[d],NextStr$[whichChar]
>> gString$(gCount) = NextStr$
>> gCount++
>> fn permutations(whichChar+1,NextStr$)
>> next
>> end if
>> end fn
>> 
>> gString$(0) = "0123456789"
>> gCount = 1
>> fn permutations(1,gString$(0))
>> '====================
>
>Whoa !!  Very nice...  Jay, would you kindly clarify what you did here...  I
>mean, is this an example of recursive programming?  How can this routine
>call itself - twice?  I missed that chapter (smile).

Bill,

Yes, this is recursion in a major way. Notice that the FN calls itself 
not just twice, but anywhere from 2 to 10 times. It first calls itself to 
do all the permutations on the chars to the right of whichChar without 
changing that char, then it swaps whichChar with each of the chars to its 
right, and calls itself again for each one.

The key to successful recursion is the test: when whichChar = 10, the FN 
falls through and no new calls are made. To understand how it works, 
change all the 10's to 4's and change gString(0) to "1234", then step 
through it in the debugger.

HTH,
 0"0
 =J= a  y
  "