## Listing the n! Permutations

Expand Messages
• I m sorry to introduce yet another case study, but in this case it is more a comparison of algorithms than that of implementations in varaious languages. I m
Message 1 of 1 , Feb 28, 2002
• 0 Attachment
I'm sorry to introduce yet another case study, but in this case it is more
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
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

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

--
-- 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).

-- (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) |
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@...