Permutations 
Author Message
 Permutations

Can someone help me?
I am trying to write a program for an exact permutation test of the
hypothesis that the rates of a certain
event is the same in different groups. Assuming the rate follows a
Poisson distribution and conditioning on the total number of incidences
in the sample, this test simplifies to a binomial distribution when
comparing two groups, and to a multinomial distribution when we have
more than two groups. To do an exact multinomial test I have to find all
possible ways that N incidences can be allocated to M different groups.
I have written the following program for this:

    {del} R{<-}MNP A;B;C;D;I;J;S;#io;E;F;K
[1]   #io{<-}0
[2]   (A C){<-}A





[8]   I{<-}(A+1){basevalue}{reverse}C{take}A
[9]   S{<-}1+(A+1){basevalue}C{take}A
[10]  B{<-}C{rho}A+1
[11]  R{<-}(0,C){rho}0
[12]  :repeat
[13]     J{<-}20000{min}S-I
[14]     D{<-}I+{iota}J
[15]     F{<-}+{slashbar}E{<-}B{represent}D
[16]     :if 1{epsilon}K{<-}F=A & R{<-}R,[0] {transpose}K/E &:end
[17]  :until S=I{<-}I+J
    {del}

This is a slow and stupid program. It is stupid because it generates a
lot of unnecessary
values that are not used for anything, and it can only handle small
samples.
Can someone show me a faster and smarter program?

Valter Sundh
Department of Community Medicin
G?teborg University
Sweden



Sat, 26 Oct 2002 03:00:00 GMT  
 Permutations
Valter Sundh asked (below) about explicitly generating all
decompositions of N into M buckets.  Here are two simple equivalent
functions written at migration level 0 of dyalog apl.  They are both
recursive;  mnp is a conventional function with header and body,  while
mnpdf is a "dynamic function" of the kind developed and described by
John Scholes of Dyadic Systems.

I have not commented internally;  they work by building from the trivial
solution for one bucket or bin,  and the nearly equally trivial one for
two.
For example,  mnp 3 2 is
0 3
1 2
2 1
3 0
So mnp 3 3 is 0,mnp 3 2 together with
1,mnp 2 2 and 2,mnp 1 2 and 3,mnp 0 2.
The result is matrified at each recursion level before passing up.
They seem much faster than MNP for reasonable (?) arguments,  but Dr
Sundh does not suggest the sizes he needs to consider.  They do get slow
quite soon with increasing A and/or C,  and another non-recursive
approach would be preferable at some stage depending on taste, machine
resources etc.

     {del} r{<-}mnp ac;a;c;l;#IO
[1]    #IO{<-}0
[2]    a c{<-}ac
[3]    :If c{match}1 & r{<-}(({rho},a),1){rho}a :EndIf
[4]    :If c{match}2 & r{<-}l,mnp({reverse}l{<-}{iota}a+1)1 :EndIf
[5]    :If c>2 & r{<-}{first}{commabar}/l,{each}mnp{each}{split}{+
   +}({reverse}l{<-}{iota}a+1),[0.5]c-1 :EndIf     {del}

     {del}mnpdf{<-}{leftbrace}a c{<-}{omega}
[1]        #IO{<-}0
[2]        c{match}1:(({rho},a),1){rho}a
[3]        c{match}2:l,{del}({reverse}l{<-}{iota}a+1)1
[4]        c>2:{first}{commabar}/l,{each}{del}{each}{split}{+
   +}({reverse}l{<-}{iota}a+1),[0.5]c-1
[5]    {rightbrace}
     {del}

I hope these transliterated forms are readable.

Mike Day
10  5  00

Quote:

>Can someone help me?

I am trying to write a program for an exact permutation test of the
hypothesis that the rates of a certain
event is the same in different groups. Assuming the rate follows a
Poisson distribution and conditioning on the total number of incidences
in the sample, this test simplifies to a binomial distribution when
comparing two groups, and to a multinomial distribution when we have
more than two groups. To do an exact multinomial test I have to find all
possible ways that N incidences can be allocated to M different groups.
I have written the following program for this:

    {del} R{<-}MNP A;B;C;D;I;J;S;#io;E;F;K
[1]   #io{<-}0
[2]   (A C){<-}A





[8]   I{<-}(A+1){basevalue}{reverse}C{take}A
[9]   S{<-}1+(A+1){basevalue}C{take}A
[10]  B{<-}C{rho}A+1
[11]  R{<-}(0,C){rho}0
[12]  :repeat
[13]     J{<-}20000{min}S-I
[14]     D{<-}I+{iota}J
[15]     F{<-}+{slashbar}E{<-}B{represent}D
[16]     :if 1{epsilon}K{<-}F=A & R{<-}R,[0] {transpose}K/E &:end
[17]  :until S=I{<-}I+J
    {del}

This is a slow and stupid program. It is stupid because it generates a
lot of unnecessary
values that are not used for anything, and it can only handle small
samples.
Can someone show me a faster and smarter program?

Valter Sundh
Department of Community Medicin
G?teborg University
Sweden



Sun, 27 Oct 2002 03:00:00 GMT  
 Permutations

Mike Day skrev:

Quote:
> Valter Sundh asked (below) about explicitly generating all
> decompositions of N into M buckets.  Here are two simple equivalent
> functions written at migration level 0 of dyalog apl.  They are both
> recursive;  mnp is a conventional function with header and body,  while
> mnpdf is a "dynamic function" of the kind developed and described by
> John Scholes of Dyadic Systems.

Thank you Mike for a quick answer, and for a solution much better than my
own.
I use APL+Win so I had to change two things in mnp to make it work:
put a diamond before :Endif, and
change {split} on line 5 to {enclose}[1].

I have compared your mnp function with my MNP,
and mnp is much faster for all sample sizes I have tried, and will make
the test I have in mind possible to use for larger data.
Some examples:
For 30 incidences and 3 classes mnp is 5 times faster than MNP,
for 30 4 it is 8 times faster and for 40 4 it is 13 times faster.
mnp executed 50 4 in about 1 second, but MNP required more than a minute.
So I have replaced my old MNP with Mike Days code, and the following
is an example of how I use it:

The data is the number of dementia cases in a group of persons
followed from the age of 70 to 85, and we want to test if the value at 70 of

a certain predictor variable is significantly associated with the risk of
becoming
demented. This predictor have three levels that we assume have an ordered
effect
on the risk.
The number of incidences in the three groups are 34 21 11, and the total
time at risk
in the groups are 22451 9695 3622 (the time scale is months, but that is
irrelevant
to this analysis).

To test this I executed
    RATE_EXACT  (34 21 11)  (22451 9695 3622)

The result looked like this:

Risk per 100 person years:     *****It really should be months*******
   0.0       62.8
   1.0       27.1
   2.0       10.1
One-tailed Significance for trend=  0.02291
Two-tailed Significance for trend=  0.03498

Here is the program code:

    {del} A RATE_EXACT
X;B;C;D;E;F;G;H;I;J;K;FACTOR;INC;TIME;UF;TT;OBS;EXP;MP

[2]   :if 2={rho}{rho}X


[5]   :else
[6]     (B TT){<-}X
[7]   :end

[9]   :if 0=#nc'A'
[10]    A{<-}{iota}{rho}B
[11]  :end
[12]  D{<-}TT{divide}+/TT
[13]  OBS{<-}+/B{times}A
[14]  EXP{<-}(+/B){times}+/D{times}A
[15]  H{<-}MNP K,{rho}B
[16]  MP{<-}H MultiNomDist D
[17]  H{<-}H+.{times}A
[18]  :if OBS<EXP
[19]    I{<-}H{<=}OBS & E{<-}+/I/MP
[20]    I{<-}H{>=}EXP+(EXP-OBS) & F{<-}+/I/MP
[21]  :else
[22]    I{<-}H{>=}OBS & E{<-}+/I/MP
[23]    I{<-}H{<=}EXP-(OBS-EXP) & F{<-}+/I/MP
[24]  :end
[25]  'Risk per 100 person years:'
[26]  'F6.1,X3,F8.1'#fmt A,[#io+0.1] 100{times}TT{divide}+/TT
[27]  'One-tailed Significance for trend= ',5{format}E
[28]  'Two-tailed Significance for trend= ',5{format}1{min}F+E
    {del}

    {del} R{<-}X MultiNomDist P;A;B;C;D;E;F;#io
[1]   #IO{<-}1
[2]   :if 2={rho}{rho}X
[3]     R{<-}(1{take}{rho}X){rho}9.9
[4]     :for E :in {iota}{rho}R
[5]        R[E]{<-}X[E;] MultiNomDist P
[6]     :end
[7]   :else
[8]     :if 80>A{<-}+/X
[9]       R{<-}(!A){times}{times}/(P*X){divide}!X
[10]    :else
[11]
R{<-}*(+/{ln}{iota}A)+E{<-}+/(X{times}{ln}P)-+/{each}{ln}{each}{iota}{each}X

[12]    :end
[13]  :end
    {del}

     {del} r{<-}MNP ac;a;c;l;#IO



[4]   #IO{<-}0
[5]   (a c){<-}ac
[6]   :If c{match}1 & r{<-}(({rho},a),1){rho}a & :EndIf
[7]   :If c{match}2 & r{<-}l,MNP({reverse}l{<-}{iota}a+1)1 & :EndIf
[8]   :If c>2 &
r{<-}{first}{commabar}/l,{each}MNP{each}{enclose}[1]({reverse}l{<-}{iota}a+1),[0.5]c-1
& :EndIf
    {del}



Sun, 27 Oct 2002 03:00:00 GMT  
 Permutations
Valter's problem can be stated as follows:

   If you have A marbles and C cups, enumerate all the ways you can
   distribute the marbles in the cups.  For example, 3 in the first
   cup, 1 in the second, and none in the third (3 1 0); or none in
   the first cup, 2 in the second, and 2 in the third (0 2 2); etc.

Here are two functions that solve this problem.  They basically use the
same straightforward recursive algorithm as Mike Day's programs, but
they shortcut the two-cup case and don't use nested arrays or each.  (I
vastly prefer the way the recursive statement looks when it's imbedded
in a loop; it's a simple, direct statement of how the induction works,
unshackled by eaches and splits and mixes.)  They also run somewhat
faster.

The first version uses APL+ control structures:

     {del}Z{<-}A MNP2 C;I;V




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      Z{<-}(0,C){rho}0

[14]         Z{<-}Z{commabar}I,(A-I)MNP2 C-1


[17]      :Endfor
[18]  :Endselect
     {del}

The second is in vanilla APL:

     {del} Z{<-}A MNP3 C;I

[2]    {->}(C>2 1)/L2 L1

[4]    {->}0

[6]    {->}0
[7]   L2:Z{<-}(0,C){rho}0
[8]    I{<-}0
[9]   L3:Z{<-}Z{commabar}I,(A-I)MNP3 C-1
[10]   {->}(A{>=}I{<-}I+1)/L3
     {del}

They both assume the index origin is 1.  You'll need to localize and set
it if you're in the habit of fiddling with #IO.

                                                Jim



Tue, 29 Oct 2002 03:00:00 GMT  
 Permutations

Jim Weigang skrev:

Quote:
> Valter's problem can be stated as follows:

>    If you have A marbles and C cups, enumerate all the ways you can
>    distribute the marbles in the cups.  For example, 3 in the first
>    cup, 1 in the second, and none in the third (3 1 0); or none in
>    the first cup, 2 in the second, and 2 in the third (0 2 2); etc.

Thank you Jim for your solution.
I have compared Mike Days and Jim Weigangs functions
for some realistic (for the data I work with) arguments  using APL+Win 3.5:
mnp is Mike's function, MNP2 is Jim's function using control structures and
MNP3 is Jim's function in plain APL. Performance is cpu time measured by
quad-MF at it's default setting and presented relative to mnp.

    marbles    cups     mnp       MNP2      MNP3
      30         3     100.0      50.7      61.0
      30         4     100.0      64.6      77.4
      30         5     100.0      72.6      87.1
      40         3     100.0      57.5      70.8
      40         4     100.0      84.9      96.6
      40         5     100.0      86.2     102.8
      60         3     100.0      78.3      87.4
      80         3     100.0      93.9     102.2
     100         3     100.0     107.3     118.5
     100         4     100.0     139.5     144.9
     125         4     100.0     144.9     149.2
     150         3     100.0     155.2     162.5
             150                       4            ws full              could do
it         ws full
             180                       4                                    could
do it
             200                       4                                       ws
full

So mnp is slower for small arguments but faster for large, but  MNP2 is more
space efficient.

A way to increase the size of the arguments that may be handled is to allocate
space for the result variable in advance, but to do that you have to be able to
calculate the number of lines in the result from the argument, and I don't know
how to do that. It might be to be possible to find a formula for this in a
statistics
book. Does anyone know anything about this?

The following is Mike Days original function:

   {del} r{<-}mnp ac;a;c;l;#IO
[1]    #IO{<-}0
[2]    a c{<-}ac
[3]    :If c{match}1 & r{<-}(({rho},a),1){rho}a :EndIf
[4]    :If c{match}2 & r{<-}l,mnp({reverse}l{<-}{iota}a+1)1 :EndIf
[5]    :If c>2 & r{<-}{first}{commabar}/l,{each}mnp{each}{split}{+
   +}({reverse}l{<-}{iota}a+1),[0.5]c-1 :EndIf     {del}

I had to make two changes to make it work in APL+Win
    - Insert diamond in front of :Endif
    - change {split} on line 5 to  {enclose}[1]

    {del} r{<-}mnp ac;a;c;l;#IO
[1]   #IO{<-}0
[2]   (a c){<-}ac
[3]   :If c{match}1 & r{<-}(({rho},a),1){rho}a & :EndIf
[4]   :If c{match}2 & r{<-}l,mnp({reverse}l{<-}{iota}a+1)1 & :EndIf
[5]   :If c>2 &
r{<-}{first}{commabar}/l,{each}mnp{each}{enclose}[1]({reverse}l{<-}{iota}a+1),[0.5]c-1
& :EndIf
    {del}

Here are Jim Weigangs functions:

  {del}Z{<-}A MNP2 C;I;V




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      Z{<-}(0,C){rho}0

[14]         Z{<-}Z{commabar}I,(A-I)MNP2 C-1


[17]      :Endfor
[18]  :Endselect
     {del}

     {del} Z{<-}A MNP3 C;I

[2]    {->}(C>2 1)/L2 L1

[4]    {->}0

[6]    {->}0
[7]   L2:Z{<-}(0,C){rho}0
[8]    I{<-}0
[9]   L3:Z{<-}Z{commabar}I,(A-I)MNP3 C-1
[10]   {->}(A{>=}I{<-}I+1)/L3
     {del}

Valter.



Wed, 30 Oct 2002 03:00:00 GMT  
 Permutations

Quote:

> calculate the number of lines in the result from the argument, and I don't know
> how to do that. It might be to be possible to find a formula for this in a
> statistics
> book. Does anyone know anything about this?

The Stirling number of the second kind S sub n super (m) is the number of ways
of partitioning a set of n elements into m non empty subsets.  Therefore the
number of ways of partitioning a set of n elements into m possibly empty
subsets is S sub n+m super (m).  Various formulas for computing ths Stirling
numbers as well as an outline of their mathematical properties can be found in
Abramowitz and Stegun p 824 ff.


Wed, 30 Oct 2002 03:00:00 GMT  
 Permutations
I tried the reference below, but couldn't understand it. On page 835 there is a table

of Stirling numbers of the second kind. The result of MNP for argument 10 3 is a
matrix of 66 rows, but according to the table S sub 13 super(3) is 28501, and the
closed form formula 24.1.4 gives the same result. Furthermore, I couldn't find the
value
66 anywhere in the table (on the chance that I had confused the arguments).
But then luckily  Mike Day sent me a function that was a solution to the problem:

His solution was:

#io <- 1
a <- a+1
r <- (a,w) rho 1
j <- 1 drop iota a
:for i :in j
  r[j;] <- +\ r[j;]


Which I simplified to

    {del} r{<-}a mnpnos w;i
[1]   r{<-}w{rho}1
[2]   :for i :in {iota}a
[3]     r{<-}+\r
[4]   :endfor
[5]   r{<-}r[w-#io=0]
    {del}

Some examples:

    10 mnpnos 3
66

    50 mnpnos 4
23426

    40 mnpnos 4
12341

    100 mnpnos 5
4598126

Quote:

> > calculate the number of lines in the result from the argument, and I don't know
> > how to do that. It might be to be possible to find a formula for this in a
> > statistics
> > book. Does anyone know anything about this?

> The Stirling number of the second kind S sub n super (m) is the number of ways
> of partitioning a set of n elements into m non empty subsets.  Therefore the
> number of ways of partitioning a set of n elements into m possibly empty
> subsets is S sub n+m super (m).  Various formulas for computing ths Stirling
> numbers as well as an outline of their mathematical properties can be found in
> Abramowitz and Stegun p 824 ff.



Fri, 01 Nov 2002 03:00:00 GMT  
 Permutations
Valter timed the programs Mike Day and I submitted, and by pushing
the marble count a good deal higher than I had tried found that my
looping algorithms (MNP2 & 3) became much slower than Mike's nested
solution:

Quote:
>     marbles    cups     mnp       MNP2      MNP3
...
>       80         3     100.0      93.9     102.2
>      100         3     100.0     107.3     118.5
>      100         4     100.0     139.5     144.9
>      125         4     100.0     144.9     149.2
>      150         3     100.0     155.2     162.5

The problem is the repeated catenation that's used to build the result
in my loops.  With each interation, the entire result so far is copied
to a larger container along with the portion generated by the current
iteration.  This is the classic catenate-in-a-loop problem, which in the
worst case results in execution time proportional to the size of the
final result squared.

Mike's nested version, in contrast, uses catenate-reduction to join the
subresults.  In APL+, catenate-reduction is apparently smart enough to
figure out the size of the final result, allocate an array of the
appropriate size, and copy the subresults to it.  This entails much less
data movement than making repeated, progressively larger copies.

The iterative program can easily be modified to avoid slow catenation:
simply assemble the subresults as a nested array and use catenate-
reduction after the loop.

   Z{<-}{iota}0

      Z{<-}Z,{enclose}I,(A-I)MNP C-1
   :Endfor

Having spoiled the purity of the flat solution with a nested array, I
toyed with the nested-each version of this loop:

   Z{<-}{disclose}{commabar}/V,{each}(({enclose}A)-{each}V)MNP{each}C-1

But I'm still disappointed by the degree to which the repetition
constructs infest the recursive statement.  Then I remembered Dyalog
APL's dynamic functions and realized they could be used to combine the
clarity of the iterative version with the terseness of the nested-each
version:

   Z{<-}{disclose}{commabar}/{ {omega},(A-{omega})MNP C-1 }{each}V

I like this version a lot--readable, clear, and elegant.  But I can't
execute it on APL+.  (Hint, hint, APL2000!)

   (And, oi, oi, oi, those transliterated braces!  They look terrible
   in their default representation of {leftbrace}/{rightbrace}.  I've
   represented them above as {<space> and <space>}.)

With the use of catenate-reduction, the iterative version is once again
faster than the nested version:

      marbles    cups     mnp       MNP4

        80         3      100        88
       100         3      100        89
       100         4      100        92
       125         4      100        96
       150         3      100        96

     {del}Z{<-}A MNP4 C;I;V




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      Z{<-}{iota}0

[14]         Z{<-}Z,{enclose}I,(A-I)MNP4 C-1


[17]      :Endfor

[19]  :Endselect
     {del}

If anyone can come up with a practical non-recursive version of this
function, I'd be interested in seeing it.  I suspect that knowing the
size of the final result is only a small part of the solution.

                                                Jim



Fri, 01 Nov 2002 03:00:00 GMT  
 Permutations
In answer to Jim Weigang:
Knowing  the size of the problem does make a big difference on performance.
I changed MNP2 to do pre-allocation of the result variable and called this
function MNP5.  Here is the result of that:

     30 40  50 80 100 120 150 TESTMNP 4 4 4 4 4 3 3
  Marbles Cups    MNP2      MNP4      MNP5
      30    4     100.0     135.0      36.8
      40    4     100.0     112.7      30.1
      50    4     100.0     104.8      27.9
      80    4     100.0      83.4      22.6
     100    4     100.0      76.8      18.4
     120    3     100.0      71.6      25.5
     150    3     100.0      57.5      15.5

This is the program to compare performance:
    {del} M TESTMNP C;E;D;I;F;A;G
[1]   '  Marbles Cups    MNP2      MNP4      MNP5'
[2]   :for I :in {iota}{rho}C
[3]     E{<-}1 #mf 'MNP2' & E{<-}1 #mf 'MNP4' & E{<-}1 #mf 'MNP5'
[4]     D{<-}M[I] MNP2 C[I] & F{<-}M[I] MNP4 C[I] & G{<-}M[I] MNP5 C[I]
[5]     :if ~D{match}F & 'ERROR IN RESULT'  & {->} & :end
[6]     :if ~D{match}G & 'ERROR IN RESULT'  & {->} & :end
[7]     A{<-}({first}#mf'MNP2'),({first}#mf'MNP4'),({first}#mf'MNP5')
[8]     8 0 5 0 10 1 10 1 10 1 {format}M[I],C[I],100{times}A{divide}A[#io]
[9]   :end
    {del}

    {del} Z{<-}A MNP2 C;I;V




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      Z{<-}(0,C){rho}0

[14]         Z{<-}Z{commabar}I,(A-I)MNP2 C-1


[17]      :Endfor
[18]  :Endselect
    {del}

    {del} Z{<-}A MNP5 C;I;V;N;E;J




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      N{<-}A mnpnos C
[13]      Z{<-}(N,C){rho}{neg}1
[14]      J{<-}0

[16]         E{<-}I,(A-I)MNP4 C-1
[17]         Z[J+{iota}1{take}{rho}E;]{<-}E
[18]         J{<-}J+{zilde}{rho}{rho}E


[21]      :Endfor
[22]  :Endselect
    {del}

    {del} r{<-}a mnpnos w;i

[2]   r{<-}w{rho}1
[3]   :for i :in {iota}a
[4]     r{<-}+\r
[5]   :endfor
[6]   r{<-}r[w-#io=0]
    {del}

The advantage of pre-allocation is three-fold:
1. It runs faster
2. It is possible to avoid ws full error by testing if there
is sufficient free space available before running the function.
3. When ws full error occurs MNP2 reaches this only
after working for a long time, but MNP4 crashes immediately.

Valter.

Quote:

> Valter timed the programs Mike Day and I submitted, and by pushing
> the marble count a good deal higher than I had tried found that my
> looping algorithms (MNP2 & 3) became much slower than Mike's nested
> solution:

> >     marbles    cups     mnp       MNP2      MNP3
> ...
> >       80         3     100.0      93.9     102.2
> >      100         3     100.0     107.3     118.5
> >      100         4     100.0     139.5     144.9
> >      125         4     100.0     144.9     149.2
> >      150         3     100.0     155.2     162.5

> The problem is the repeated catenation that's used to build the result
> in my loops.  With each interation, the entire result so far is copied
> to a larger container along with the portion generated by the current
> iteration.  This is the classic catenate-in-a-loop problem, which in the
> worst case results in execution time proportional to the size of the
> final result squared.

> Mike's nested version, in contrast, uses catenate-reduction to join the
> subresults.  In APL+, catenate-reduction is apparently smart enough to
> figure out the size of the final result, allocate an array of the
> appropriate size, and copy the subresults to it.  This entails much less
> data movement than making repeated, progressively larger copies.

> The iterative program can easily be modified to avoid slow catenation:
> simply assemble the subresults as a nested array and use catenate-
> reduction after the loop.

>    Z{<-}{iota}0

>       Z{<-}Z,{enclose}I,(A-I)MNP C-1
>    :Endfor

> Having spoiled the purity of the flat solution with a nested array, I
> toyed with the nested-each version of this loop:

>    Z{<-}{disclose}{commabar}/V,{each}(({enclose}A)-{each}V)MNP{each}C-1

> But I'm still disappointed by the degree to which the repetition
> constructs infest the recursive statement.  Then I remembered Dyalog
> APL's dynamic functions and realized they could be used to combine the
> clarity of the iterative version with the terseness of the nested-each
> version:

>    Z{<-}{disclose}{commabar}/{ {omega},(A-{omega})MNP C-1 }{each}V

> I like this version a lot--readable, clear, and elegant.  But I can't
> execute it on APL+.  (Hint, hint, APL2000!)

>    (And, oi, oi, oi, those transliterated braces!  They look terrible
>    in their default representation of {leftbrace}/{rightbrace}.  I've
>    represented them above as {<space> and <space>}.)

> With the use of catenate-reduction, the iterative version is once again
> faster than the nested version:

>       marbles    cups     mnp       MNP4

>         80         3      100        88
>        100         3      100        89
>        100         4      100        92
>        125         4      100        96
>        150         3      100        96

>      {del}Z{<-}A MNP4 C;I;V




> [5]   V{<-}0,{iota}A
> [6]   :Select C
> [7]   :Case 1

> [9]   :Case 2

> [11]  :Else
> [12]      Z{<-}{iota}0

> [14]         Z{<-}Z,{enclose}I,(A-I)MNP4 C-1


> [17]      :Endfor

> [19]  :Endselect
>      {del}

> If anyone can come up with a practical non-recursive version of this
> function, I'd be interested in seeing it.  I suspect that knowing the
> size of the final result is only a small part of the solution.

>                                                 Jim



Sat, 02 Nov 2002 03:00:00 GMT  
 Permutations
I made a misstake in the previous posting Permutations- comparison-2

The function MNP5 called MNP4 inside the loop instead of itself as
was intended. I have corrected this error in MNP5, but as the
accidental function was so fast I renamed it to MNP54 (because
it is a hybrid of MNP4 and MNP5).
I also substituted the function mnpnos for the formula provided
by Eugene McDonnell.

Performance:

  Marbles Cups    MNP2      MNP4      MNP54     MNP5
      30    4     100.0     139.5      37.9     109.0
      60    4     100.0      92.7      24.0      56.8
     120    3     100.0      73.9      25.7      36.4
     120    4     100.0      73.9      18.5      28.1
     150    3     100.0      55.7      15.2     103.1
     150    4     100.0      73.3      16.0      19.6

So MNP5 is faster than MNP4 for most arguments, but not
for all. But MNP54 consistently out perform all alternatives.

    {del} Z{<-}A MNP54 C;I;V;N;E;J




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      N{<-}A!A+C-1
[13]      Z{<-}(N,C){rho}{neg}1
[14]      J{<-}0

[16]         E{<-}I,(A-I)MNP4 C-1
[17]         Z[J+{iota}1{take}{rho}E;]{<-}E
[18]         J{<-}J+{zilde}{rho}{rho}E


[21]      :Endfor
[22]  :Endselect
    {del}

    {del} Z{<-}A MNP4 C;I;V




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else
[12]      Z{<-}{iota}0

[14]         Z{<-}Z,{enclose}I,(A-I)MNP4 C-1


[17]      :Endfor

[19]  :Endselect
    {del}

    {del} Z{<-}A MNP5 C;I;V;N;E;J




[5]   V{<-}0,{iota}A
[6]   :Select C
[7]   :Case 1

[9]   :Case 2

[11]  :Else

[13]      Z{<-}(N,C){rho}{neg}1
[14]      J{<-}0

[16]         E{<-}I,(A-I)MNP5 C-1
[17]         Z[J+{iota}1{take}{rho}E;]{<-}E
[18]         J{<-}J+{zilde}{rho}{rho}E


[21]      :Endfor
[22]  :Endselect
    {del}

Valter.



Sat, 02 Nov 2002 03:00:00 GMT  
 
 [ 16 post ]  Go to page: [1] [2]

 Relevant Pages 

1. all-permutations is faster than permutation

2. A permutation on permutations

3. Generating permutations

4. Finding permutations

5. All Permutations

6. All permutations

7. Permutation

8. Linked list to Permutation vector

9. Permutations

10. Puzzler: function of permutation vector

11. Fwd: re: Puzzler: Permutations and Anagrams

12. Puzzler: Permutations and Anagrams

 

 
Powered by phpBB® Forum Software