Rocky Smolin at Beach Access Software
rockysmolin at bchacc.com
Fri Mar 2 20:11:53 CST 2007
Arthur:
I don't know if this is helpful or not but might move the problem along
towards a solution. I forwarded your problem to my cousin who is a math
prof. - taught at Toronto for years, then came back to San Diego State - now
retired. This is what he wrote back.
Rocky
-----Original Message-----
From: Steve Pierce [mailto:stevepb at san.rr.com]
Sent: Friday, March 02, 2007 5:01 PM
To: Rocky Smolin at Beach Access Software
Subject: Re: [AccessD] Help discovering algorithm
----- Original Message -----
From: "Rocky Smolin at Beach Access Software" <rockysmolin at bchacc.com>
To: <stevepb at san.rr.com>
Sent: Friday, March 02, 2007 4:35 PM
Subject: FW: [AccessD] Help discovering algorithm
> Here's an interesting question. How would devise an algorithm to generate
> the permutations per Arthur's spec below?
>
> Rocky
Actually, Arthur has hit on the usual method. In fact, he has hit on two
possible methods. First of all, for strings of length n, mathematicians
usually use the numbers from 1 to n. It's just for convenience; you could
use ABCDE.... or any n distinct objects.
What Arthur has done is observe that he can write down all of the
permutations of {2,3,4,5} in lexicographic order (i.e., "alphabetical
order"). Then he takes each of these 24 permutations, puts a 1 on the left
and then "cycles" them, getting 5 different permutations for each of the 24.
This is as good as anything as far as I know. Or he can just write down the
120 permutations of {1,2,3,4,5} in lexicographic order. I suspect that the
first way is computationally faster.
Arthur also notes that any permutation of n objects can be achieved by
starting with 1,2,3,4,....,n and making a series of transpositions
(switching 2 numbers). But I don't think that this would be very useful for
writing (in some convenient way) all of the n! permutations.
Now how do I get that DOWNLOAD button off of my desktop?
Steve
>
>
>
>
>
>
>
>
> -----Original Message-----
> From: accessd-bounces at databaseadvisors.com
> [mailto:accessd-bounces at databaseadvisors.com] On Behalf Of
> artful at rogers.com
> Sent: Friday, March 02, 2007 1:40 PM
> To: AccessD at databaseadvisors. com
> Subject: [AccessD] Help discovering algorithm
>
> For some reason, I cannot deduce what I'm doing when I work out this
> algorithm. I can work it out by hand, as the following table illustrates,
> but I am having big problems generalizing what I'm doing to account for a
> string of inderminate length.
>
> Assume a string of inderminate length. I want to produce all variations of
> said string. What is so far obvious is that the number of variations is
> equal to the factorial of the string. I can generate them by hand but I
> cannot seem to be able to deduce the algorithm that I'm using. The
> following
> table uses a 5-character string and presents only the variations that
> leave
> the first character alone (for brevity). Obviously to generate the
> remaining
> solutions I just rotate the string and repeat.
>
> The first column in the table shows the string's variants. The second
> column
> does the same, but uses numbers indicating the the sequence of the
> characters with relation to the original string. Here is the table:
>
> ABCDE12345
> ABCED12354
> ABDCE12435
> ABDEC12453
> ABECD12534
> ABEDC12543
> ACBDE13245
> ACBED13254
> ACDBE13425
> ACDEB13452
> ACEBD13524
> ACEDB13542
> ADBCE14235
> ADBEC14253
> ADCBE14325
> ADCEB14352
> ADEBC14523
> ADECB14532
> AEBCD15234
> AEBDC15243
> AECBD15324
> AECDB15342
> AEDBC15423
> AEDCB15432
>
>
> Please help me realize what I'm doing here. I have a function that works
> called Transpose(s as String, i as Integer, j as Integer), which (gasp)
> will
> transpose the letters in the string that are located at positions i and j.
> What I need is the algorithm that I'm using to walk through the string and
> generate the variations.
>
> Any insights much appreciated.
>
> Arthur
> --
> AccessD mailing list
> AccessD at databaseadvisors.com
> http://databaseadvisors.com/mailman/listinfo/accessd
> Website: http://www.databaseadvisors.com
>
> --
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.5.446 / Virus Database: 268.18.5/707 - Release Date: 3/1/2007
> 2:43 PM
>
>
--
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.5.446 / Virus Database: 268.18.5/707 - Release Date: 3/1/2007
2:43 PM