a comparison of algorithms than that of implementations in varaious

languages.

I'm talking about having a finite set of distinct numbers and displaying

all of their n! permutations:

I.e:

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

Assuming the set is {1,2,3}. Now, I had to write a Perl codelet that will

generate them as part of a script I wrote to check something in my "Game

Theory" homework. The code worked beautifully. Then I checked the Standard

C++ library and the Internet for ready-made algorithms and discovered the

following page:

http://www.cut-the-knot.com/do_you_know/AllPerm.html

It describes two algorithms to do so: an iterative one and a recursive

one. The Standard C++ algorithm header seems to use a variation of the

iterative one. In any case, both use assignment and can only be

implemented in a FP language using pseudo-recursion. The algorithm I came

up with however, seemed to be very adaptable for FP. Here is its

implementation in Haskell:

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

-- (gradual_transfer set empty_set)

--

-- Gradually pops elements out of set and [1..5] pushes them into

-- empty_set,

-- and makes a list of both stacks in their intermediate phases.

--

-- E.g:

-- gradual_transfer [1 .. 5] [] =

-- [([1,2,3,4,5],[]),([2,3,4,5],[1]),([3,4,5],[2,1]),

-- ([4,5],[3,2,1]),([5],[4,3,2,1])]

gradual_transfer :: [a] -> [a] -> [([a],[a])]

-- I stop when the list contains a single element, not when it contains

-- no elements at all. The reason for this is that gen_perms like it

-- better

-- this way, as it has no use of a zero element (a:as).

gradual_transfer (a:[]) ps = [((a:[]),ps)]

gradual_transfer (a:as) ps = ((a:as),ps):(gradual_transfer as (a:ps))

-- (dump ps as) is equivalent to (reverse ps) ++ as, only it should

-- be much faster.

dump :: [a] -> [a] -> [a]

dump [] as = as

dump (p:ps) as = dump ps (p:as)

gen_perms :: [a] -> [[a]]

gen_perms [] = [[]]

gen_perms set = [ (a:rest) |

(a:as,ps) <- (gradual_transfer set []),

rest <- gen_perms(dump ps as)

]

print_perms [] = return ()

print_perms (a:as) = do print a

print_perms as

main = print_perms (gen_perms [1 .. 8])

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

For all ye Haskell illiterate, here is the more-or-less original Perl

code, that generates a very long array containing the permutations:

##############################3

sub gen_perms

{

my @set = @_;

if (! scalar(@set))

{

return ([]);

}

my $elem;

my @prev_elems;

my @perms;

while ($elem = shift(@set))

{

push @perms, (map { [$elem,@{$_}] } gen_perms(@prev_elems,@set));

push @prev_elems, $elem;

}

return @perms;

}

#################################

I'm not sure but I think it's a distinct algorithm than the recursive one

that is proposed in the site. Am I wrong?

It's a nice thing that one can come up with several ways of doing the same

thing. I remember that in the second time I tried to master Haskell, I

came across three algorithms for generating the list of primes. My SICP

lecturer said there was a way to reduce two functional algorithms to see

if they are the same, does anybody know what is the applicability here?

I'd like to know if I found a distinct algorithm, so if this is the case,

I'll post it to the site's forum for discussion.

Regards,

Shlomi Fish

There is no IGLU Cabal! Its members spent a better time of their lives

writing an RDBM server in a purely functional programming language. After

having to deal with desigining many FP-friendly algorithms, and dealing

with ugly code that was made uglier due to FP, they found the task

of maintaining the IGLU site too mundande and unchallenging.

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

Shlomi Fish shlomif@...

Home Page: http://t2.technion.ac.il/~shlomif/

Home E-mail: shlomif@...

"Let's suppose you have a table with 2^n cups..."

"Wait a second - is n a natural number?"