permuting a string (was Re: Speed)

Geoff Canyon gcanyon at gmail.com
Sat Aug 30 09:01:16 EDT 2014


Gah -- now I'm not convinced that my way will work at all. I'll test and
reply later.


On Sat, Aug 30, 2014 at 8:19 AM, Geoff Canyon <gcanyon at gmail.com> wrote:

>
> On Sat, Aug 30, 2014 at 7:24 AM, Beat Cornaz <B.Cornaz at gmx.net> wrote:
>
>>  Sat, 30 Aug 2014  Geoff wrote :
>>
>> > Used Alex's code to generate a list of the permutations of all the
>> characters that were duplicates.
>> > Substituted in unique characters for each instance of the duplicates.
>> > Ran my permutation code on the rest of the characters, with the
>> addition of the duplicates-permutation-strings as the base case.
>>
>> I was working on the same line, but from the other end. I start with the
>> characters that are not duplicate and use your very fast code to get all
>> the permutations.
>> The I slot in, one for one, all the duplicate elements on all possible
>> positions. After slotting in each duplicate element, I delete duplicate
>> lines, so in the next run of inserting the next duplicate element, I will
>> have to do less, as the duplicate lines have been deleted. I am not
>> completely finished with the script & testing. I will post it as soon as
>> possible.
>>
>
> This was my initial thought as well, but I didn't like having to work
> line-by-line on (potentially) large sets of lines from the initial
> not-duplicate set of permutations. Doing the dupes first is weirder
> conceptually, but it means that the line-by-line work is done on a much
> smaller data set. For example, permuting "aaaabbbbcdef" would only require
> line-by-line on 8!/(4!*4!) = 70 lines. It will be interesting comparing the
> two solutions.
>
> btw, there is no need to unroll the recursive nature of my initial routine
> unless it bugs you. It only calls itself as many times as there are
> characters, so there is virtually 0 overhead involved in the function calls.
>
> gc
>



More information about the use-livecode mailing list