Finding permutations 
Author Message
 Finding permutations

Recently in this newsgroup an example has been given for finding all of the
permutations of a set of integers. What follows are illustrations of
solutions in Dyalog APL, the first being a dynamic function and the second a
traditional function. The algorithms for each of the solutions are
essentially identical, employing recursive logic. The APL symbols are
represented here by hopefully obvious textual descriptors. Note that for a
dynamic function the symbol "omega" represents the right argument and the
symbol "self" the identity of the containing function. Some timing tests
suggest that the dynamic function solution takes about two-thirds the time as
does the traditional function solution.

permutations assign {
0 = shape omega:mix ravel split omega
mix catenatefirst reduction omega catenate compose self each omega compose    
    without each omega

Quote:
}

r assign permutations x
:If 0 equals shape x
     r assign mix ravel split x
:Else
     r assign mix catenatefirst reduction x catenate compose permutations    
          each x compose without each x
:EndIf

--
James L. Ryan
TaliesinSoft



Sun, 12 Jun 2005 00:48:45 GMT  
 Finding permutations
The use of catenatefirst reduction in the following
makes me curious.  Can you please tell me the time for
the following reduction in Dyalog APL?

   x {is} 1e6 2 3 {rho} 'a'
   {catenatefirst} {reduction} x

Quote:
----- Original Message -----


Sent: Tuesday, December 24, 2002 09:00 AM
Subject: Finding permutations


> Recently in this newsgroup an example has been given for finding all of
the
> permutations of a set of integers. What follows are illustrations of
> solutions in Dyalog APL, the first being a dynamic function and the second
a
> traditional function. The algorithms for each of the solutions are
> essentially identical, employing recursive logic. The APL symbols are
> represented here by hopefully obvious textual descriptors. Note that for a
> dynamic function the symbol "omega" represents the right argument and the
> symbol "self" the identity of the containing function. Some timing tests
> suggest that the dynamic function solution takes about two-thirds the time
as
> does the traditional function solution.

> permutations assign {
> 0 = shape omega:mix ravel split omega
> mix catenatefirst reduction omega catenate compose self each omega compose
>     without each omega
> }

> r assign permutations x
> :If 0 equals shape x
>      r assign mix ravel split x
> :Else
>      r assign mix catenatefirst reduction x catenate compose permutations
>           each x compose without each x
> :EndIf

> --
> James L. Ryan
> TaliesinSoft



Sun, 12 Jun 2005 02:37:10 GMT  
 Finding permutations


Quote:
> The use of catenatefirst reduction in the following
> makes me curious.  Can you please tell me the time for
> the following reduction in Dyalog APL?

>    x {is} 1e6 2 3 {rho} 'a'
>    {catenatefirst} {reduction} x

15 sec on a 1GHz PC

         x {<-} 1e6 2 3 {rho} 'a'
       #ts  &    a{<-} {commabar}/x   &   #ts
2002 12 25 1 47 15 0
2002 12 25 1 47 30 0

Ray



Sun, 12 Jun 2005 09:50:31 GMT  
 Finding permutations
On Tue, 24 Dec 2002 20:50:31 -0500, Ray Cannon wrote

Quote:


>> The use of catenatefirst reduction in the following
>> makes me curious.  Can you please tell me the time for
>> the following reduction in Dyalog APL?

>> x {is} 1e6 2 3 {rho} 'a'
>> {catenatefirst} {reduction} x

> 15 sec on a 1GHz PC

>          x {<-} 1e6 2 3 {rho} 'a'
>        #ts  &    a{<-} {commabar}/x   &   #ts
> 2002 12 25 1 47 15 0
> 2002 12 25 1 47 30 0

I run Dyalog APL under Windows 2000 which in turn is running under Virtual PC
on a Macintosh. Virtual PC emulates a Pentium processor on a Power PC
processor. Although this privides me with a totally satisfactory development
environment, the performance is quite a bit slower than it would be if I were
running natively on a real PC. My Macintosh has a processor speed of 500 MHZ,
and the benchmarks I have performed suggest that all-in-all through Virtual
PC I am getting the equivilent of something between a 150 to 200 MHZ PC.

The above expression took 72 seconds, a time which is reasonably consistent
with that which Ray reported.

--
James L. Ryan
TaliesinSoft



Sun, 12 Jun 2005 12:26:23 GMT  
 Finding permutations

For comparison:

APLX on a PowerBook G4 (500MHz) running MacOSX yields 23 seconds.
APLX on a PowerMac G4 (1.25GHz) running MacOSX is 8 seconds - that's on
busy system with a lot of apps running that I didn't want to terminate
for the quick test.

regards

roland


Quote:

> On Tue, 24 Dec 2002 20:50:31 -0500, Ray Cannon wrote



> >> The use of catenatefirst reduction in the following
> >> makes me curious.  Can you please tell me the time for
> >> the following reduction in Dyalog APL?

> >> x {is} 1e6 2 3 {rho} 'a'
> >> {catenatefirst} {reduction} x

> > 15 sec on a 1GHz PC

> >          x {<-} 1e6 2 3 {rho} 'a'
> >        #ts  &    a{<-} {commabar}/x   &   #ts
> > 2002 12 25 1 47 15 0
> > 2002 12 25 1 47 30 0

> I run Dyalog APL under Windows 2000 which in turn is running under Virtual PC
> on a Macintosh. Virtual PC emulates a Pentium processor on a Power PC
> processor. Although this privides me with a totally satisfactory development
> environment, the performance is quite a bit slower than it would be if I were
> running natively on a real PC. My Macintosh has a processor speed of 500 MHZ,
> and the benchmarks I have performed suggest that all-in-all through Virtual
> PC I am getting the equivilent of something between a 150 to 200 MHZ PC.

> The above expression took 72 seconds, a time which is reasonably consistent
> with that which Ray reported.



Mon, 13 Jun 2005 05:05:43 GMT  
 Finding permutations
Two things can be done to put the "15 seconds on
a 1 GHz PC" benchmark in perspective.  The first
is to compare it to some standard benchmark,
say the time it takes to do +/ on a million-
element floating point vector; the second is to do
,/ on (n,2 3){rho}'a' for n=2e5 4e5 6e5 8e5 1e6.
In J (on a 500 Mhz PC):

   timer=: 6!:2
   timer '+/x' [ x=: 0.01 * ?1e6$100
0.0182708

   tcr=: 3 : 'timer '',/x'' [ x=. (y.,2 3)$''a'''
   tcr"0 ] 2e5 * 1 2 3 4 5
0.00979398 0.0192589 0.0351765 0.0453169 0.0629398

   0.0629398 % 0.0182708
3.44483

i.e. in J the time for ,/x is linear in the leading
dimension of x, and the time for ,/(1e6 2 3)$'a'
is roughly 3.5 times the time for +/1e6$1.01.

Can you please do the additional benchmarks in
Dyalog APL?

Quote:
----- Original Message -----


Sent: Tuesday, December 24, 2002 20:33 PM
Subject: Re: Finding permutations


> On Tue, 24 Dec 2002 20:50:31 -0500, Ray Cannon wrote



> >> The use of catenatefirst reduction in the following
> >> makes me curious.  Can you please tell me the time for
> >> the following reduction in Dyalog APL?

> >> x {is} 1e6 2 3 {rho} 'a'
> >> {catenatefirst} {reduction} x

> > 15 sec on a 1GHz PC

> >          x {<-} 1e6 2 3 {rho} 'a'
> >        #ts  &    a{<-} {commabar}/x   &   #ts
> > 2002 12 25 1 47 15 0
> > 2002 12 25 1 47 30 0

> I run Dyalog APL under Windows 2000 which in turn is running under Virtual
PC
> on a Macintosh. Virtual PC emulates a Pentium processor on a Power PC
> processor. Although this privides me with a totally satisfactory
development
> environment, the performance is quite a bit slower than it would be if I
were
> running natively on a real PC. My Macintosh has a processor speed of 500
MHZ,
> and the benchmarks I have performed suggest that all-in-all through
Virtual
> PC I am getting the equivilent of something between a 150 to 200 MHZ PC.

> The above expression took 72 seconds, a time which is reasonably
consistent
> with that which Ray reported.

> --
> James L. Ryan
> TaliesinSoft



Mon, 13 Jun 2005 06:16:37 GMT  
 Finding permutations

Quote:
> The use of catenatefirst reduction in the following
> makes me curious.  Can you please tell me the time for
> the following reduction in Dyalog APL?

>    x {is} 1e6 2 3 {rho} 'a'
>    {catenatefirst} {reduction} x

I would expect the performance to be tragic (which is indeed what others
before me already have confirmed). Since the technique to make the proposed
reduction linear in space and time is well-known (and implemented already in
J and K) I expect that it will soon be implemented in Dyalog APL as well
(rumours...).
--
    WildHeart'2k2 (at Home)


Mon, 13 Jun 2005 18:17:05 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. all-permutations is faster than permutation

2. A permutation on permutations

3. Generating permutations

4. All Permutations

5. All permutations

6. Permutation

7. Permutations

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