From: Terry Reedy
Subject: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <53rmh2$n84@news.udel.edu>
Constrained Combinations in Lisp and Python (Oct 13, 1996)

In "Algorithm Alley" (Dr. Dobb's Journal, Nov 1996), John Swartz
presents a simple LISP program for generating all unique
combinations from a list (multiset) with duplicate members.
His straightforward solution is to generate all combinations
and then filter out the duplicates.  For selection of 9 elements
from 12 consisting of 3 copies of 4 different items, 220 candidates
reduce to 20 different combinations.  His program:

(defun makeset (lat)
  (cond ((null lat) ())
        ((member (car lat)(cdr lat) :test ` equal)
                    (makeset (cdr lat)))
        ( t         (cons (car lat)(makeset (cdr lat))))
))
(defun combinations (size set)
  (cond ((zerop size) '(()))
        ((null set)    ())
    (t (append (distrib (car set) (combinations (1- size) (cdr set)))
               (combinations size (cdr set))))
))
(defun (distrib (a sett)
  (cond ((null sett) ())
        (t (cons (cons a (car sett)) (distrib a (cdr sett))))
))
(mapcar print (makeset (combinations 9 '(a a a b b b c c c d d d))))

On an unspecified PC, XLISP 1.6 (by David Betz) took 3 minutes.

As an experiment and learning exercise, I translated this into Python.
Python (www.python.org, comp.lang.python) has the list facilities of
LISP (and other stuff) with a syntax more like C, Pascal, etc.

# The 4 substitutions below (in '#' comments) are explained later
from time import clock
t0=clock()

def makeset(lat):
  if lat == []:           return []
  elif lat[0] in lat[1:]: return makeset(lat[1:])
  else:                   return [lat[0]] + makeset(lat[1:])

def combinations(size, set):
  if size == 0:   return [[]]  # [[]] to ['']
  elif set == []: return []    #  []  to  ''
  else:           return distrib(set[0],combinations(size-1,set[1:]))\
  +                      combinations(size,set[1:])

def distrib(a, sett):
  if sett == []: return []     # [a] to a (line below)
  else:          return [[a]+sett[0]] + distrib(a,sett[1:])

for l in makeset(combinations(9,
  ['a','a','a','b','b','b','c','c','c','d','d','d'])):
    print l  # [...] to 'aaabbbcccddd' (line above)

print clock()-t0
# if "def prt(l): print l" then "map(prt,makeset(...))" parallels lisp

With Python 1.3 interpreter pyth_dos.exe in a DOS window under W95 on a 
120 MH Pentium PC, this takes 1.3 seconds (1.1 for combinatins()).

I conclude:
1. At least some LISP code translates 'word-for-word' into Python.
This suggests that tested and published LISP algorithms could be
good source material for Python programmers.
2. Unless Swartz ran XLISP on an old 8088 PC, at least some of the
137-fold difference in speed (181/1.32) is due to the Python
interpreter running this algorithm faster than the XLISP interpreter.
3. Programmers who like the lisp coding style but not the syntax
might consider Python as an alternative.

"Improvements" in the Python version:
1. Representing combinations as strings rather than lists of characters 
requires only 4 minor syntax changes. Speedup: 10%.
2. Straitforwardly converting single recursion to iteration gives the 
following (speedup: 10% each):

def distrib(a, sett):
  ret = []
  for l in sett:
    ret.append(a+l)
  return ret

def makeset(lat): # this empties original set; could write otherwise
  ret = []
  while lat:
    l = lat[0]
    del lat[0]
    if l not in lat: ret.append(l)
  return ret

3. In either Lisp or Python, one can reduce intermediate space usage
by bringing the call to makeset() inside of combinations(), applying
it to the list about to be returned.  In Python, the speedup from 
handling shorter lists is balanced by the slowdown from making more
function calls.

4. The string output is given below.  As indicated, this constrained
combinations problem is equivalent to that of partitioning 9 into
the sum of 4 counts in the range [0,3] (where order matters).
Rather than trying to remove either or both of the recursive calls
in combinations(), I would look into partitioning algorithms for
further speedup.

aaabbbccc # 3+3+3+0
aaabbbccd # 3+3+2+1
aaabbbcdd # 3+3+1+2
aaabbbddd # 3+3+0+3
aaabbcccd # 3+2+3+1
aaabbccdd # 3+2+2+2
aaabbcddd # 3+2+1+2
aaabcccdd # 3+1+3+2
aaabccddd # 3+1+2+3
aaacccddd # 3+0+3+3
aabbbcccd # 2+3+3+1
aabbbccdd # 2+3+2+2
aabbbcddd # 2+3+1+3
aabbcccdd # 2+2+3+2
aabbccddd # 2+2+2+3
aabcccddd # 2+1+3+3
abbbcccdd # 1+3+3+2
abbbccddd # 1+3+2+3
abbcccddd # 1+2+3+3
bbbcccddd # 0+3+3+3

Terry J. Reedy, ·······@udel.edu

From: Seth Tisue
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <53seb5$tiq@Godzilla.cs.nwu.edu>
In article <··········@news.udel.edu>, Terry Reedy <·······@udel.edu> wrote:
>[code deleted]
>On an unspecified PC, XLISP 1.6 (by David Betz) took 3 minutes.
>With Python 1.3 interpreter pyth_dos.exe in a DOS window under W95 on a 
>120 MH Pentium PC, this takes 1.3 seconds (1.1 for combinatins()).

The Lisp version runs in 2.5 seconds using GCL 2.2 under Linux on my
relatively underpowered 486/66 PC.  That's running interpreted, not
compiled.  Under CLISP in the same environment, it runs in 1.5
seconds.

I'm afraid your benchmark doesn't prove anything except that XLISP is
an incredibly slow Lisp implementation.

>"Improvements" in the Python version:
>1. Representing combinations as strings rather than lists of characters 
>requires only 4 minor syntax changes. Speedup: 10%.

This is not an improvement -- you're restricting the program to
operate only on characters.  The LISP version works on any type of
object.  Is this possible in Python?  (Honest question, not sarcastic)
-- 
== Seth Tisue <·······@nwu.edu>         http://www.cs.nwu.edu/~tisue/
From: Rainer Joswig
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <joswig-ya023180001410960821200001@news.lavielle.com>
In article <··········@Godzilla.cs.nwu.edu>, ·····@cs.nwu.edu (Seth Tisue)
wrote:

> In article <··········@news.udel.edu>, Terry Reedy <·······@udel.edu> wrote:
> >[code deleted]
> >On an unspecified PC, XLISP 1.6 (by David Betz) took 3 minutes.
> >With Python 1.3 interpreter pyth_dos.exe in a DOS window under W95 on a 
> >120 MH Pentium PC, this takes 1.3 seconds (1.1 for combinatins()).
> 
> The Lisp version runs in 2.5 seconds using GCL 2.2 under Linux on my
> relatively underpowered 486/66 PC.  That's running interpreted, not
> compiled.  Under CLISP in the same environment, it runs in 1.5
> seconds.

Who needs an interpreter?


This is in Macintosh Common Lisp 4 on a 100 Mhz PowerPC 603e
PowerBook. Without changing the source, optimizations are off,
EGC is on, tons of programs in the background, PPP currently
running.

With printing (which takes most of time, because it goes
directly into an editor):

(MAPCAR #'PRINT (MAKESET (COMBINATIONS 9 '(A A A B B B C C C D D D))))
took 2,247 milliseconds (2.247 seconds) to run.
Of that, 402 milliseconds (0.402 seconds) were spent in The Cooperative
Multitasking Experience.
39 milliseconds (0.039 seconds) was spent in GC.
 47,840 bytes of memory allocated.

Without printing (the result is being printed anyway by the listener):

(MAKESET (COMBINATIONS 9 '(A A A B B B C C C D D D))) took 40
milliseconds (0.040 seconds) to run.
 47,680 bytes of memory allocated.
From: Peter Norvig
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <NORVIG.96Oct15100908@meteor.harlequin.com>
In Harlequin's LispWorks on a Sun 2, it takes 0.03 seconds compiled.

Note that the APPEND in COMBINATIONS could better be an NCONC, and that
MAKESET could be replaced by the built-in DELETE-DUPLICATES with :TEST #'EQUAL.

In article <··········@Godzilla.cs.nwu.edu> ·····@cs.nwu.edu (Seth Tisue) writes:

> From: ·····@cs.nwu.edu (Seth Tisue)
> Newsgroups: comp.lang.python,comp.lang.lisp
> Date: 13 Oct 1996 23:08:05 -0500
> Organization: Northwestern University Computer Science Department
> 
> In article <··········@news.udel.edu>, Terry Reedy <·······@udel.edu> wrote:
> >[code deleted]
> >On an unspecified PC, XLISP 1.6 (by David Betz) took 3 minutes.
> >With Python 1.3 interpreter pyth_dos.exe in a DOS window under W95 on a 
> >120 MH Pentium PC, this takes 1.3 seconds (1.1 for combinatins()).
> 
> The Lisp version runs in 2.5 seconds using GCL 2.2 under Linux on my
> relatively underpowered 486/66 PC.  That's running interpreted, not
> compiled.  Under CLISP in the same environment, it runs in 1.5
> seconds.
> 
> I'm afraid your benchmark doesn't prove anything except that XLISP is
> an incredibly slow Lisp implementation.
> 
-- 
Peter Norvig               | Phone: 415-833-4022           
Harlequin Inc.             | FAX:   415-833-4111
1010 El Camino Real, #310  | Email: ······@harlequin.com
Menlo Park CA 94025        | http://www.harlequin.com/books/norvig/norvig.html
From: Rainer Joswig
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <joswig-ya023180001510961406290001@news.lavielle.com>
In article <··········@news.udel.edu>, ·······@udel.edu (Terry Reedy) wrote:

> * For production code, native-language compiled Lisp is faster than the 
> non-existent Python equivalent.  But for development work and one-time 
> usage, being able to cut from an editor window and paste into an interpreter 
> window is a dream come true. 

Hmm, in Lisp systems I have used (LispWorks, ACL, Genera, MacScheme,
CMUCL, MCL, Emacs, ...) I never had to do cut and paste. Just
pressing "Enter" in MCL and the current expression at the
cursor of the editor gets compiled, runs and results are
printed in the next listener. Who needs an interpreter?
Actually we have this some 15 years.


> * I did a string version of the Python code to see how much faster it ran.  
> My 'justification' is that practical problems will almost certainly select 
> from a (multi)set with fewer than 256 (unique) members. With a Python 
> dictionary, it is trivial to map characters back to the original objects and 
> hence answer strings to answer lists.  In this sense, a string 
> representation of the input and output lists is a convenience 'canonical' 
> representation.

Ummpf.

> * Although translating Lisp into Python (or writing Lisp-like recursive code 
> directly) does not give optimized Python code (ie, with recursion converted 
> to iteration),

With todays Lisp compilers you don't need to convert recursion
to iteration. Recursion can be as fast as iteration. 

Why would anyone convert Lisp code to Python? I mean this not
negatively. Is Python superior to Lisp? In what cases?
I'm curious.


Rainer Joswig

(are people still using "APPEND"?)
From: Tom Culliton
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <540785$6j4@clarknet.clark.net>
In article <·································@news.lavielle.com>,
Rainer Joswig <······@lavielle.com> wrote:
>Why would anyone convert Lisp code to Python? I mean this not
>negatively. Is Python superior to Lisp? In what cases?
>I'm curious.

Is Python superior to Lisp?  Yes, at least for people who are used to
algorithmic (Fortran/Algol family) languages rather than functional
(lisp family) languages.  (Anyone who wants to nit pick about what
functional and algorithmic are can go straight to /dev/null.)  Python
is simply the most readable langauge I've ever come across.

Can it do anything that Lisp can't do at least as efficiently,
elegantly, and easily?  No, but my experience with various flavors of
Lisp is that looking at code again after even a few weeks is at least
as hard as writing it in the first place.

It's mainly just a matter of taste and what you're used to.
From: Rainer Joswig
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <joswig-ya023180001510962015190001@news.lavielle.com>
In article <··········@clarknet.clark.net>, ········@clark.net (Tom
Culliton) wrote:

> In article <·································@news.lavielle.com>,
> Rainer Joswig <······@lavielle.com> wrote:
> >Why would anyone convert Lisp code to Python? I mean this not
> >negatively. Is Python superior to Lisp? In what cases?
> >I'm curious.
> 
> Is Python superior to Lisp?  Yes, at least for people who are used to
> algorithmic (Fortran/Algol family) languages rather than functional
> (lisp family) languages.

Must be a matter of syntax? Most Lisp dialects include a full share
of procedural constructs (Common Lisp has stuff like tagbody, go,
progn, dolist, do, loop, ...). So it is possible to write
imperative code in Lisp as well (Common Lisp is a multi-paradigm 
language - it supports out of the box imperative, functional and
object-oriented programming - it also can be easily extended
to add rule-based, logic, constraint-based, ... programming).

I still don't get it, what makes Python different. 

> Can it do anything that Lisp can't do at least as efficiently,
> elegantly, and easily?  No, but my experience with various flavors of
> Lisp is that looking at code again after even a few weeks is at least
> as hard as writing it in the first place.

Hmm, that's completely different to my experience. I can look
at self written code after a year and still do understand
what it does. Btw., a coworker of mine is Pascal, C and C++ programmer.
He thinks (atleast what I gave him to read) Common Lisp code is
readable. But he has the problem of understanding his own
Pascal source.

> It's mainly just a matter of taste and what you're used to.

Yes, this is a very important factor.

Rainer Joswig
From: Glenn Ammons
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <AMMONS.96Oct16132802@salsa.cs.wisc.edu>
Thanks Terry for bringing DrDobb's article up in this group.  I
personally think a more interesting question than "Is Python better
than Lisp for this problem?" is "Why would a magazine like DrDobb's
publish such a misleading article on Lisp?"  The article reinforced
many common misconceptions about Lisp:

  1) Lisp is very slow.  The last sentence of the article read
  
    "As you can see, the execution time was three minutes."

  This for listing the choices of 9 items from a bag with 3 items in
  each of 4 colors.  How many readers new to Lisp ran in fear when
  they saw that?

  2) Lisp isn't standardized.  The article should have used Common
  Lisp instead of an archaic version of Xlisp.

  3) Lisp is tailored for list processing.

  4) Lisp wastes memory.  Quoting the article, "John McCarthy would
  probably not have been able to run this example using the hardware
  on which he developed LISP." (because of memory constraints) Maybe
  John McCarthy couldn't have run _that_ program, but I'm sure he
  could have solved the problem.

  5) Lisp is only good for toy problems.  The article appeared in
  Algorithm Alley, a regular column.  Past Algorithm Alley's have
  discussed an efficient algorithm for constructing suffix trees, a
  data structure to speed up resizing variable-sized arrays, and an
  algorithm to find minimal perfect hashes.  Usually an implementation
  is given in C or C++.  So what do we get when DrDobb's decides to
  run an article supposedly demonstrating the kinds of problems for
  which Lisp is "the right tool"?  An inefficient (as others have
  pointed out here) algorithm for listing combinations!


--glenn
From: Rainer Joswig
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <joswig-ya023180001710960425520001@news.lavielle.com>
In article <····················@salsa.cs.wisc.edu>,
······@salsa.cs.wisc.edu (Glenn Ammons) wrote:

> Thanks Terry for bringing DrDobb's article up in this group.  I
> personally think a more interesting question than "Is Python better
> than Lisp for this problem?

In the Lisp "world" there are a lot of tools for implementing
abstractions (and also abstractions which do not impose unnecessary
efficiency penalties) for these kind of problems (see the treatment by
Abelson&Sussman of streams in SICP, see the Series package
available for Common Lisp, see the various works on
Functional Programming, etc., see PAIP by Peter Norvig, ...).
This is ordinary Computer Science stuff. See also the various
Computer Algebra systems, for example Macsyma or Axiom,
which provide good support for these kind of problems.

Some Python examples posted here showed much more insight
than the original article. The algorithms were already bad,
but their Lisp implementation was even worse. The real
problem is that on some Lisp systems even such a bad
implementation has reasonable performance when used
in isolation with small to medium sized datasets. 
And some people don't have an idea what
"complexity of algorithms" is.
Unfortunately most development environments won't
give you any feedback that you may have made bad decisions,
when your software shows unnecessary speed and space
problems. Atleast you should use a profiler (which
is standard on Symbolics Genera and some other Lisp systems).

Building larger systems out of this kind of software will
eventually fail. Reimplementation with better
combinations of data structures and
algorithms will have better performance characteristics.
But then it might already be to late that you still will be allowed
to use Lisp or languages like Python. Yeah, use C. Its
so much faster.
From: Glenn Ammons
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <AMMONS.96Oct17221008@salsa.cs.wisc.edu>
In article <·································@news.lavielle.com> ······@lavielle.com (Rainer Joswig) writes:

> In article <····················@salsa.cs.wisc.edu>,
> ······@salsa.cs.wisc.edu (Glenn Ammons) wrote:
> 
> > Thanks Terry for bringing DrDobb's article up in this group.  I
> > personally think a more interesting question than "Is Python better
> > than Lisp for this problem?
> 
> In the Lisp "world" there are a lot of tools for implementing
> abstractions (and also abstractions which do not impose unnecessary
> efficiency penalties) for these kind of problems...

Plus a couple of paragraphs about the importance of choosing good
algorithms, using profilers, etc.

I just want to make clear that I agree with you.  The real tragedy is
that the DrDobb's article, which was supposed to showcase Lisp in an
area in which it's strong, chose a bad algorithm and a bad
implementation.  This leaves the casual reader who doesn't program in
Lisp with the impression that Lisp is impossibly impractical.

--glenn
From: ········@wat.hookup.net
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <548d7m$nvn@nic.wat.hookup.net>
In <····················@salsa.cs.wisc.edu>, ······@salsa.cs.wisc.edu (Glenn Ammons) writes:
> ...
>I just want to make clear that I agree with you.  The real tragedy is
>that the DrDobb's article, which was supposed to showcase Lisp in an
>area in which it's strong, chose a bad algorithm and a bad
>implementation.  This leaves the casual reader who doesn't program in
>Lisp with the impression that Lisp is impossibly impractical.
>
>--glenn

When was this article published? The machine they were running it on might
very well have been an XT with DOS 3.0. For quite a while xlisp was pretty
much the only Lisp implementation available on PCs (at least I didn't know of
any other).

Hartmann Schaffer
From: Cyber Surfer
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <845709444snz@wildcard.demon.co.uk>
In article <··········@nic.wat.hookup.net> ········@wat.hookup.net  writes:

> When was this article published? The machine they were running it on might
> very well have been an XT with DOS 3.0. For quite a while xlisp was pretty
> much the only Lisp implementation available on PCs (at least I didn't know of
> any other).

Yes, I remember a time when XLISP appeared to be the only
freely available Lisp for DOS (and many other OSs/machines).
While I'm typing this, I'm downloading the latest CLISP for
DOS - just by coincidence - as its about time I updated my copy.

I'm currently writing an indexing util in CL, and ACL Lite
runs out of memory when I run it on a big document (like CLtL2!).
So, I'll use CLISP for the stress testing. I doubt that XLISP
could begin to cope.

Actually, I'm writing the indexing util in C++ _and_ Lisp, as
an experiment. So far, the C++ version runs 4X faster, but
that would be coz it examines each file character by character,
and I'm unable to put that (very small) part of the program
into a DLL and call it from ACL. This is because I'm using ACL
Lite - the full version would not only allow me to use the FFI,
but also deliver a stand alone binary.

It's not so much the performance differences that interest me,
as the ease and speed of development. The amount of pleasure
I get from using Lisp instead of C++ is also significant!

The bottom line is this: when you're counting beans, it helps
if you count the _right_ beans, i.e. the ones that matter.
Computers make it easy for us to measure things, but we can
measure things that have no significance to anyone except for
a few sad people obsessed with meaningless details. The fact
that we can save a few beans (e.g. milliseconds of runtime)
here and there in our code only helps us if we can something
better for the machine to do during those beans, and all too
often we don't even notice them. We can count them, but so what?

It sounds a lot like the author of the article being discussed
here forgot what the beans represented, or simply chose the
_wrong_ beans to count.
-- 
<URL:http://www.enrapture.com/cybes/> You can never browse enough
Future generations are relying on us
It's a world we've made - Incubus
We're living on a knife edge, looking for the ground -- Hawkwind
From: Olivier Lefevre
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <3268662C.4A1B@ny.ubs.com>
Terry Reedy wrote:
> 
> Constrained Combinations in Lisp and Python (Oct 13, 1996)
> 
> In "Algorithm Alley" (Dr. Dobb's Journal, Nov 1996), John Swartz
> presents a simple LISP program for generating all unique
> combinations from a list (multiset) with duplicate members.

A thread on just this topic unfolded about a year ago in comp.lang.apl
and the proposed solutions were *much* more compact than anything seen
here. Unfortunately I can't really comment any further than that because 
I am unfamiliar with both Lisp and python.

Olivier Lefevre
From: Steve Apter
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <54lm46$a28@ns2.ny.ubs.com>
Those of you who track comp.lang.apl will know something about J and K, since
practitioners of those languages regularly post there.  As my colleague Olivier
pointed out, a thread devoted to similar problems ran in that forum last year.
The J folks have a nice suite of combinatorial primitives for handling this
sort of thing.

Roger?

·······@udel.edu (Terry Reedy) wrote:
>In article <··········@news.udel.edu>, I discussed a LISP program, and its 
>Python translation, for generating all unique combinations from a list 
>(multiset) with duplicate members.  The algorithm given was to generate all 
>combinations, without regard to duplication, and then filter out the 
>duplicates.

In K:

         ······@&:'+q[;&9=+/q:4_vs!_4^4]
("bbbcccddd"
 "abbcccddd"
 "abbbccddd"
 "abbbcccdd"
 "aabcccddd"
 "aabbccddd"
 "aabbcccdd"
 "aabbbcddd"
 "aabbbccdd"
 "aabbbcccd"
 "aaacccddd"
 "aaabccddd"
 "aaabcccdd"
 "aaabbcddd"
 "aaabbccdd"
 "aaabbcccd"
 "aaabbbddd"
 "aaabbbcdd"
 "aaabbbccd"
 "aaabbbccc")

On my Sparc2, this runs too quickly to register a timing in milliseconds.  But as
several posters have said, this is a terrible algorithm.

>
>* I conjectured near the end that generation of constrained combinations of 
>k items could be done directly (without generating duplicates), and more 
>quickly, by solving the isomorphic problem of generating sums.
>IE. suppose multiset of n items has j unique items and mj of each.
>Then: subset of k items <==> j integers kj in range [0,mj] with sum k.
>Example: aaabbcccd <==> 3,2,3,1.  

x is the vector of ranges, y is the target sum, z is the result list.  g calls h,
h calls i, and i calls g.

	g:{:[(()~x)&y>0;();y=0;,z,&#x;h[1_ x;y;(!*x;z)]]}
	h:{i[x;y;(z[0]@&~y<*z;z 1)]}
	i:{,/(y-*z)g[x]'z[1],/:*z}

The original problem:

	g[4 4 4 4;9;()]
(0 3 3 3
 1 2 3 3
 1 3 2 3
 1 3 3 2
 2 1 3 3
 2 2 2 3
 2 2 3 2
 2 3 1 3
 2 3 2 2
 2 3 3 1
 3 0 3 3
 3 1 2 3
 3 1 3 2
 3 2 1 3
 3 2 2 2
 3 2 3 1
 3 3 0 3
 3 3 1 2
 3 3 2 1
 3 3 3 0)

Once again, this is too fast to raise a millisecond blip on my Sparc.  So let's
run it on a much larger problem.  Find sequences in 5 6 7 4 8 4 8 which sum to
34:

	\t r:g[5 6 7 4 8 4 8;34;()]
11830
	r
(3 5 6 3 7 3 7
 4 4 6 3 7 3 7
 4 5 5 3 7 3 7
 4 5 6 2 7 3 7
 4 5 6 3 6 3 7
 4 5 6 3 7 2 7
 4 5 6 3 7 3 6)

12 seconds to find the seven sequences in 5 6 7 4 8 4 8 which sum to 34.

	\t s:g[5 6 7 4 8 4 8;22;()]
10930
	#s			/ number of sequences
11726
	&/22=+/'s		/ verify results sum to 22
1
  
A bit less to find those sequences which sum to 22.

	\t t:g[5 6 7 4 8 4 8;12;()]
2075
	#t			/ number of sequences
9496
	&/12=+/'t		/ verify results sum to 12
1
  
Only two seconds to find those which sum to 12 - 9496 of those.

> 		The recursion is as follows:
>
>def partitions(k, set):
>  if set == [] and k == 0:   return [[]]
>  if set == [] or set[0] <0: return [] #
>  s0 = set[0]
>  if s0 > k: s0 = k # or: return partitions(k, [k]+set[1:])
>  return distrib(s0, partitions(k-s0,set[1:]))\
>  +                  partitions(k, [s0-1]+set[1:])
>
>def distrib(a, sett):
>  if sett == []: return []     # [a] to a (line below)
>  else:          return [[a]+sett[0]] + distrib(a,sett[1:])
>
>for l in partitions(9, [3,3,3,3]): print l
>
>Generating 20 items directly instead of filtering 220 to 20 is, not too 
>surprisingly, about 10x as fast.  Getting the better algorithm saves more 
>than optimizing the poorer one.  Still, I could not resist a semi-iterative 
>version of this, which cuts the time in half again to .05 seconds
>
>def partitions(target, cnts):
>  if type(target) != type(0): raise TypeError, "Non-int target %s" % target
>  if type(cnts)  != type([]): raise TypeError, "Non-list arg %s" % cnts
>  if cnts == []: raise ValueError, "Empty list of counts"
>  sum = 0
>  for i in cnts:
>    if type(i) != type(0): raise TypeError, "Non-int %s in list" % i
>    if i < 0: raise ValueError, "Negative count %d" % i
>    sum = sum + i
>  if target < 0 or target > sum: return [] # or raise ValueError
>  return _partit2(sum, target, cnts)
>
>def _partit2(sum, target, cnts): # sum >= target, cnts != []
>  imax = cnts[0]
>  imin = target + imax - sum
>  if imax > target: imax = target
>  if imin < 0:      imin = 0
>  ret = []
>  for i in range(imax, imin-1, -1):
>    if len(cnts) == 1: ret.append([i])
>    else:
>      for p in _partit2(sum-cnts[0], target-i, cnts[1:]):
>        ret.append([i]+p)
>  return ret
>
From: Steve Apter
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <54lnnf$a28@ns2.ny.ubs.com>
In my post, I said

> On my Sparc2 ...

But that's not right.  It's a Sparc20.
				    ^
sa
From: Randy MacDonald
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <32726614.1EF7@godin.on.ca>
My concern with all this K is that the language definition
is not available to us, and I'm reminded of Joe McCarthy
talking about a list of known communists that he never shows us.
We can only take your word that it does what it says.

Steve Apter wrote:
>duplicates.
> 
> In K:
> 
>          ······@&:'+q[;&9=+/q:4_vs!_4^4]

> On my Sparc2, this runs too quickly to register a timing in
> milliseconds.  But as several posters have said, this is a 
> terrible algorithm.

on a Von Neumann machine it would be.. If it does what it says
it should be obvious to a K reader.

> x is the vector of ranges, y is the target sum, z is the result list.
> g calls h,
> h calls i, and i calls g.
> 
>         g:{:[(()~x)&y>0;();y=0;,z,&#x;h[1_ x;y;(!*x;z)]]}
>         h:{i[x;y;(z[0]@&~y<*z;z 1)]}
>         i:{,/(y-*z)g[x]'z[1],/:*z}

--
|\/| Randy A MacDonald       |"We ARE the weirdos, mister!"
|\\| ·····@godin.on.ca       |        Fairuza Balk "The Craft"
     BSc(Math) UNBF '83      | APL: If you can say it, it's done.
     Natural Born APL'er     | *** GLi Info: ····@godin.on.ca ***
     I use Real J            | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-
From: Michael Rosenberg
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <552fqj$53s@panix2.panix.com>
In article <·············@godin.on.ca>,
Randy MacDonald  <·····@godin.on.ca> wrote:
>My concern with all this K is that the language definition
>is not available to us, and I'm reminded of Joe McCarthy
>talking about a list of known communists that he never shows us.
>We can only take your word that it does what it says.
>

it's a massive hoax. steve is making this stuff up as he
goes along. i work in the office next door to him. we use
apl2 on ibm mainframes. i must say i'm impressed with the
consistency of the so-called "code" he has posted here.

mike
From: Michael Rosenberg
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <552g77$5mo@panix2.panix.com>
the mailer cut off the crucial last line in my posting:

p.s.  i manage the k group at ubs   ;-)


In article <··········@panix2.panix.com>,
Michael Rosenberg <···@panix.com> wrote:
>In article <·············@godin.on.ca>,
>Randy MacDonald  <·····@godin.on.ca> wrote:
>>My concern with all this K is that the language definition
>>is not available to us, and I'm reminded of Joe McCarthy
>>talking about a list of known communists that he never shows us.
>>We can only take your word that it does what it says.
>>
>
>it's a massive hoax. steve is making this stuff up as he
>goes along. i work in the office next door to him. we use
>apl2 on ibm mainframes. i must say i'm impressed with the
>consistency of the so-called "code" he has posted here.
>
>mike
>
From: Randy MacDonald
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <327591C2.5E7@godin.on.ca>
Michael Rosenberg wrote:
> 
> the mailer cut off the crucial last line in my posting:
> 
> p.s.  i manage the k group at ubs   ;-)

Minister of Propaganda, should we be impressed?  If it's
proprietary, perhaps it should be private. 


--
|\/| Randy A MacDonald       |"We ARE the weirdos, mister!"
|\\| ·····@godin.on.ca       |        Fairuza Balk "The Craft"
     BSc(Math) UNBF '83      | APL: If you can say it, it's done.
     Natural Born APL'er     | *** GLi Info: ····@godin.on.ca ***
     I use Real J            | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-
From: Steve Apter
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <552odr$57j@ns2.ny.ubs.com>
···@panix.com (Michael Rosenberg) wrote:
>In article <·············@godin.on.ca>,
>Randy MacDonald  <·····@godin.on.ca> wrote:
>>My concern with all this K is that the language definition
>>is not available to us, and I'm reminded of Joe McCarthy
>>talking about a list of known communists that he never shows us.
>>We can only take your word that it does what it says.

You mean there weren't any communists in the State Department?

>>
>
>it's a massive hoax. steve is making this stuff up as he
>goes along. i work in the office next door to him. we use
>apl2 on ibm mainframes. i must say i'm impressed with the
>consistency of the so-called "code" he has posted here.

That's the easy part.  You try delivering applications written
in a non-existent language.

>
>mike
>

Once again, for a description of K, see:

      _Vector_, vol 10, number 1, July 1993, pp.71-80.

sa
From: Randy MacDonald
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <32782D8B.52BD@godin.on.ca>
Steve Apter wrote:
> 
> ···@panix.com (Michael Rosenberg) wrote:
> >In article <·············@godin.on.ca>,
> >Randy MacDonald  <·····@godin.on.ca> wrote:
> >>My concern with all this K is that the language definition
> >>is not available to us, and I'm reminded of Joe McCarthy
> >>talking about a list of known communists that he never shows us.
> >>We can only take your word that it does what it says.

> Once again, for a description of K, see:
> 
>       _Vector_, vol 10, number 1, July 1993, pp.71-80.
> 
If it is equivalent to the version at (and please, if you tell
Bob to remove it, you won't do anyone any favours.)

  http://cosy.com/cosy/language/k.txt

then you have not answered my question.  There is not even what
one would call a reasonable cover of the language.  A "description"
is not a "definition" 

In another post, Ste

>>Please grow up. We know otherwise.  You fill apl/j bandwidth
>>with an untestable language.  Perhaps we should just target
>>it as the K(am) it is?

>First you claim that the language definition is not available.  As
>I've pointed out at least twice, this is not true.

See above.

>Then you compare me to a disgraced alcoholic senator from Wisconsin,
>and suggest that my word is unreliable.

No I'm comparing Spam to K(am)...

>And you tell Mike to grow up?

>Stop this nonsense, please.  A typical comp.lang.java thread contains
>more bytes than will flow in a year's worth of K discussion.  

Your choice of newsgroup reading is NOT my problem. In any case, the
Java specification is as OVER exposed as the K definition is under-
exposed.

>And if you're really all that concerned about wasting net resource,
>trim your sig.  Hell, it's longer than most APL functions.

But is it full of inaccessible ideas, I think not. And it is longer
than 89.3% of the functions in our primary workspace, so your
comment is correct if beside the point.

> This newsgroup is a forum for ideas in array programming.

A "forum" is not necessarily where one talks only to oneself.

> Algorithms matter. 

I totally agree.  Algorithms formulated in a proprietary, private
language are not worth much more than random characters.

> Dialect-specific details don't.

Details like: no verifiable method of checking the correctness of
statements written in the language.  I apologize if "trust me"
is not a statement I accept.

--
|\/| Randy A MacDonald       |"We ARE the weirdos, mister!"
|\\| ·····@godin.on.ca       |        Fairuza Balk "The Craft"
     BSc(Math) UNBF '83      | APL: If you can say it, it's done.
     Natural Born APL'er     | *** GLi Info: ····@godin.on.ca ***
     I use Real J            | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-
From: Randy MacDonald
Subject: Re: Constrained Combinations in Lisp and Python
Date: 
Message-ID: <32759133.2DA9@godin.on.ca>
Michael Rosenberg wrote:
> 
> In article <·············@godin.on.ca>,
> Randy MacDonald  <·····@godin.on.ca> wrote:
> >My concern with all this K is that the language definition
> >is not available to us, and I'm reminded of Joe McCarthy
> >talking about a list of known communists that he never shows us.
> >We can only take your word that it does what it says.
> >
> 
> it's a massive hoax. steve is making this stuff up as he
> goes along. i work in the office next door to him. we use
> apl2 on ibm mainframes. i must say i'm impressed with the
> consistency of the so-called "code" he has posted here.

Please grow up. We know otherwise.  You fill apl/j bandwidth
with an untestable language.  Perhaps we should just target
it as the K(am) it is?

--
|\/| Randy A MacDonald       |"We ARE the weirdos, mister!"
|\\| ·····@godin.on.ca       |        Fairuza Balk "The Craft"
     BSc(Math) UNBF '83      | APL: If you can say it, it's done.
     Natural Born APL'er     | *** GLi Info: ····@godin.on.ca ***
     I use Real J            | Also http://www.godin.com/godin/
------------------------------------------------<-NTP>----{ gnat }-