hi all!

below is the description and source of a proggy that does permutation of a

dataset, i found one routine doing this in the forum here, but is so slow that

good old c had to come in to the rescue...

compare the speed of this proggy to that in the forums here and you'll be blown

away! the pb routine is so lame in comparison, well, uhm, that there is no

comparison! the one from the forum runs way slower, even on 200mhz pentium

system under nt2000.

here's the code from the

forum: http://www.powerbasic.com/support/pb...ad.php?t=22353

anyways, now that the mood is set, check out this proggy by paul and think it

over, can you write something better, faster?

the algorithm used is fairly simple. for each item i in a set of n items:

remove item i from the data set;

find all permutations of the remaining n - 1 items;

insert item i back into the set in its original position

the recursive function perm() shows this algorithm. each permutation is printed

as it is found.

the rest of the code is relatively lengthy, but merely supports the above

algorithm by providing it with appropriate data structures. two data structures

are provided:

a data set, an ordered list allowing two operations:

removing an item from a given position, and

inserting an item into a given position

a stack to hold the current permutation, which like all stacks allows two

operations:

pushing an item onto the top of the stack, and

popping an item off the top of the stack

in order to understand the algorithm used to find the permutations, it is not

necessary to delve into the details of these functions or data structures any

more than it is necessary to understand exactly how a printf() call produces

output on your screen. the main() and perm() functions describe the algorithm

completely.

functions to:

initialize and free memory used by the data set,

print out the contents of the stack, and

retrieve the number of data items from the command line

are also provided.

----------------------------------------------

usage:

pass the number of data items to the command line as the single argument. an

example session is shown below:

perm 3

permutations of 3 items:

abc

acb

bac

bca

cab

cba

6 permutations in all.

---------------------------------------------

executable size (in kb)14.256!

compiled and executed on an intel 166mhz pentium processor

with 32mb ram, running linux kernel 2.2.5-15

here you see the performance of the algorithm, where it becomes apparent

that the output (to screen etc) consumes more time than algorithm itself.

so instead of printing it, keeping it in an array eliminates the output

delays. one can then print the array with all permutations once the

program has done its job.

performance (with output):

=========================

invocation permutations (secs)

./perm 1 1 -

./perm 2 2 -

./perm 3 6 -

./perm 4 24 -

./perm 5 120 -

./perm 6 720 0.05

./perm 7 5,040 0.36

./perm 8 40,320 2.97

./perm 9 362,880 27.64

performance (no output):

=======================

invocation permutations (secs)

./perm 1 1 -

./perm 2 2 -

./perm 3 6 -

./perm 4 24 -

./perm 5 120 -

./perm 6 720 -

./perm 7 5,040 0.015

./perm 8 40,320 0.12

./perm 9 362,880 1.06

./perm 10 3,628,800 10.61

./perm 11 39,916,800 116.61

so here's the challenge:

show off pb and write it in pb/dll so it is at least as fast as the

c program, preferably even faster (if that can be done in pb)

the code should be pb only! however it would be cool to see what a

real assembler guru can do to speed it up even more once it's done...

jax

ps: i just aquired pb/dll a little while ago and am still trying to

figure it all out, however i know c since decades, so i figure it would

be easier to start with it. now i am exploring if bying pb was worth it

or not, seems to me that there are some serious speed penalties in

using pb. however, mayhaps there is a better solution ala pb style and i

am just not into it enough yet?

next post is c-source

------------------

below is the description and source of a proggy that does permutation of a

dataset, i found one routine doing this in the forum here, but is so slow that

good old c had to come in to the rescue...

compare the speed of this proggy to that in the forums here and you'll be blown

away! the pb routine is so lame in comparison, well, uhm, that there is no

comparison! the one from the forum runs way slower, even on 200mhz pentium

system under nt2000.

here's the code from the

forum: http://www.powerbasic.com/support/pb...ad.php?t=22353

anyways, now that the mood is set, check out this proggy by paul and think it

over, can you write something better, faster?

the algorithm used is fairly simple. for each item i in a set of n items:

remove item i from the data set;

find all permutations of the remaining n - 1 items;

insert item i back into the set in its original position

the recursive function perm() shows this algorithm. each permutation is printed

as it is found.

the rest of the code is relatively lengthy, but merely supports the above

algorithm by providing it with appropriate data structures. two data structures

are provided:

a data set, an ordered list allowing two operations:

removing an item from a given position, and

inserting an item into a given position

a stack to hold the current permutation, which like all stacks allows two

operations:

pushing an item onto the top of the stack, and

popping an item off the top of the stack

in order to understand the algorithm used to find the permutations, it is not

necessary to delve into the details of these functions or data structures any

more than it is necessary to understand exactly how a printf() call produces

output on your screen. the main() and perm() functions describe the algorithm

completely.

functions to:

initialize and free memory used by the data set,

print out the contents of the stack, and

retrieve the number of data items from the command line

are also provided.

----------------------------------------------

usage:

pass the number of data items to the command line as the single argument. an

example session is shown below:

perm 3

permutations of 3 items:

abc

acb

bac

bca

cab

cba

6 permutations in all.

---------------------------------------------

executable size (in kb)14.256!

compiled and executed on an intel 166mhz pentium processor

with 32mb ram, running linux kernel 2.2.5-15

here you see the performance of the algorithm, where it becomes apparent

that the output (to screen etc) consumes more time than algorithm itself.

so instead of printing it, keeping it in an array eliminates the output

delays. one can then print the array with all permutations once the

program has done its job.

performance (with output):

=========================

invocation permutations (secs)

./perm 1 1 -

./perm 2 2 -

./perm 3 6 -

./perm 4 24 -

./perm 5 120 -

./perm 6 720 0.05

./perm 7 5,040 0.36

./perm 8 40,320 2.97

./perm 9 362,880 27.64

performance (no output):

=======================

invocation permutations (secs)

./perm 1 1 -

./perm 2 2 -

./perm 3 6 -

./perm 4 24 -

./perm 5 120 -

./perm 6 720 -

./perm 7 5,040 0.015

./perm 8 40,320 0.12

./perm 9 362,880 1.06

./perm 10 3,628,800 10.61

./perm 11 39,916,800 116.61

so here's the challenge:

show off pb and write it in pb/dll so it is at least as fast as the

c program, preferably even faster (if that can be done in pb)

the code should be pb only! however it would be cool to see what a

real assembler guru can do to speed it up even more once it's done...

jax

ps: i just aquired pb/dll a little while ago and am still trying to

figure it all out, however i know c since decades, so i figure it would

be easier to start with it. now i am exploring if bying pb was worth it

or not, seems to me that there are some serious speed penalties in

using pb. however, mayhaps there is a better solution ala pb style and i

am just not into it enough yet?

next post is c-source

------------------

## Comment