Re: Problem: code, algorithm, or both?


"pineapple" <pineapple.link@xxxxxxxxx> wrote in message
news:6c3585e1-9152-44d2-9cda-913ac20992d1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I have needed a permutation algorithm. I found a simple one online
that seems to fit my needs, and tried to code it up. Hasn't worked
right yet, but due to my limited APL skill, I don't know if the
problem is the algorithm, my code, or both.

This is the algorithm I found online (I inserted line numbers). You
give it a number (k), and a vector (s), and it will return a
permutation computed using that number:

[0] function permutation(k, s) {
[1] for j= 2 to length(s) {
[2] k:= k/ (j-1); // integer division cuts off the
remainder
[3] swap s[(k mod j)+ 1] with s[j]; //note that our array is
indexed starting at 1
[4] }
[5] return s;
[6] }

This is one of my many attempts to APL-ify the above. I tried to
"unravel" the loop at first, then later tried an almost direct looping
translation. This is an "unraveled loop" version (line numbers
correspond):

[0] s ? k perm s ; j
[1] j ? 1 ? ? ? s
[2] k ? ? k ÷ j - 1
[3] s[1 + j | k] ? s[j]

For those who have problems with the unicode:

[0] s gets k perm s ; j
[1] j gets 1 drop iota rho s
[2] k gets floor k dividedby j - 1
[3] s[1 + j | k] gets s[j]

I also tried:

[3] s ? s[1+j | k] ([3] s gets s[1+j | k])

and a few other things that made intuitive sense on the surface.
Since swapping is occurring, I also tried the classic swap that one
would do in a "standard" language, i.e. "temp gets x, x gets y, y gets
temp" and numerous other things. Finally I tried a standard old for
loop.

Thanks.

Try this it is not the most efficient I guess but it appears to work and
does its swapping by successively applying the rotate function.

r{<-}n Perm v;p;m;i

m{<-}{rho}v & p{<-}{times}\{iota}m

v{<-}(p[{rho}p],m){rho}v & r{<-}(p[{rho}p],0){rho}0

:for i :in {iota}m-1

r{<-}r,(p[{rho}p],1){take}v{<-}(p[{rho}p]{rho}p[m-i]/0,{iota}m-i){rotate}v

v{<-}0 1{drop}v

:endfor

r{<-}(p[{rho}p],n){take}r,v

r{<-}({or}{slashbar}<\r^.={transpose}r){slashbar}r

Graham.


.

Relevant Pages

  • Problem: code, algorithm, or both?
    ... I have needed a permutation algorithm. ... This is the algorithm I found online. ... This is an "unraveled loop" version (line numbers ...
    (comp.lang.apl)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... and Richard made it clear that he understands the order ... >> of evaluation of a for loop. ... > using strlen but using an Oalgorithm when there is a trivial O ... >> In most other languages the terminating ...
    (comp.programming)
  • Re: Efficiency questions: combined ifs and looping 4 times
    ... Choice of algorithm always has a far bigger impact in performance than ... Use sizeof before the loop, store the result in a var and use ... speaks well of PHP. ... your order of complexity analysis is off. ...
    (comp.lang.php)
  • Re: count of each word occurred
    ... > take each word in order and compare it with the rest of the list ... Another version of this algorithm takes advantage of the fact that it does ... loop over all words in the list ... a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Excel Sort() Algorithm
    ... keys by appending the original order as the lowest order element. ... 'infinite' loop. ... That's what the 1-loop algorithm I used provides and what the 3-loop ... Dim kv As Variant, pv As Variant, t As Variant ...
    (microsoft.public.excel.worksheet.functions)