Loading ...
Sorry, an error occurred while loading the content.

Listing the n! Permutations

Expand Messages
  • Shlomi Fish
    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
      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?"
    Your message has been successfully submitted and would be delivered to recipients shortly.