permuting a string (was Re: Speed)

[Geoff Canyon]

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