APL, Finding permutations

Finding permutations

Author	Message
James L. Rya #1 / 7	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

Roger Hu #2 / 7	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

Ray Canno #3 / 7	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

James L. Rya #4 / 7	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

Roland Bessere #5 / 7	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

Roger Hu #6 / 7	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

Stefano Lanzavecchi #7 / 7	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

Page 1 of 1

[ 7 post ]