Subject: Listing the n! Permutations

From: Shlomi Fish <[email-masked]>
Date: Thu, 28 Feb 2002 21:43:03 +0200 (IST)

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
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        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"