"Chuck Crayne" <ccrayne@[EMAIL PROTECTED]
> wrote in message
news:20080720192150.38d2fa30@[EMAIL PROTECTED]
> > How? Try to generate 1...47,52,51,50,49,48 without an array from some
> > function. Or, try to generate 1..47,52,51,50,49,48 with an input
> > array of 1...52 from some function.
>
> I'll demonstrate one possible algorithm for the three element string
> ABC, and leave the generalization as an exercise for the reader
>
> Pn Permutation
> 0 ABC
> 1 ACB
> 2 BAC
> 3 BCA
> 4 CAB
> 5 CBA
>
> Divide Pn by two, remembering both the dividend and the
> remainder. The first element in the desired permutation is obtained by
> using the dividend as an [base 0] index into the base string.
>
> Next, remove that element from the string. The second element in the
> desired permutation is obtained by using the remainder as an index
> into the remaining string.
>
> Finally, remove that element from the string. The third element in the
> desired permutation is the remaining string character.
>
> For example, consider the fourth permutation, for which Pn = 3. Three
> divided by two is one with one remaining. Thus the first element is
> ABC[1], the second element is AC[1], and the third element is A[0].
>
> The reverse function is almost as easy. Starting with BCA, B's index in
> the base string is 1, as is C's index after removing B. Thus Pn = 2*1
> +1.
>
> QED
QED for length 3! But for length 4, some of the div indexes will exceed
the
string length... (Um, maybe?...)
RP
|
