Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ucbvax!decwrl!labrea!sri-unix!quintus!ok
From: ok@quintus
Newsgroups: comp.lang.prolog
Subject: all permutations
Keywords: comparisons, costs
Message-ID: <314@quintus.UUCP>
Date: 25 Aug 88 04:43:16 GMT
Sender: news@quintus.UUCP
Reply-To: ok@quintus ()
Organization: Quintus Computer Systems, Inc.
Lines: 31


In message <615@mannix.iros1.UUCP>, Paul Tarau @ l'Universite de Montreal
presented an "all permutations" predicate, and said
>However, I think it is not as fast as it could be.  Does someone
>know about a faster and/or shorter 'all_permutations' program?

In message <1172@tuhold>, Thom Fruehwirth @ TU Vienna presented his
version, which he says is "much faster and shorter".  As for its size,
that depends on how you measure it.  Here are four measurements:
Version		    Tarau's  Fruehwirth's
# of predicates       4        4
# of clauses	      8        7
# of identifiers     73       71 (things starting with a letter)
# of characters     630      338 (when converted to the same layout style)
The principal size difference between them is that Tarau used longer
predicate and variable names.

As for speed, when one says that method A is faster than method B, one has
to be clear about which implementation one is using.  On a Sun 3/50 using
Quintus Prolog release 2.4, for example, Tarau's version is about 1.7 times
faster than Fruehwirth's (well, I tweaked it a bit).

Tarau correctly describes this operation as "very space-consuming".
Suppose that a list cell costs 8 bytes, that there is no sharing, and
that you have a virtual address space of 128 Mbytes.  How long a list
can you store all the permutations of?  The space required for all the
permutations of a list of N elements is 8.N.N!  For N=9, this comes to
about 26 Mbytes.  For N=10, this comes to about 290 Mbytes.  (I made the
mistake of trying N=9 with "limit core 8M".  Makes a great torture test
for the garbage collector.)

Time is not the only cost.