int main() {
    ifstream in("input.dat");
    vector<int> L;
    int n;
    while(in >> n)
        L.push_back(n);
    ofstream out("output.dat");
    sort(L.begin(), L.end());
    do {
        for(int i = 0; i < L.size(); i++)
            out << L[i] << " ";
        out << '\n';
    } while(next_permutation(L.begin(), L.end()));
    return 0;

BTW, use less than 12 input values while testing, unless you want
"output.dat" to be 10Gb :)

Wroot

(defun permute-stream (in-stream out-stream)
  (loop
      for element = (read in-stream nil in-stream)
      while (not (eq element in-stream))
      collect element into elements
      finally (format out-stream "~{~{~A~^ ~}~%~}" (permute elements))))

(defun permute-file (in-file out-file)
  (with-open-file (in-stream in-file)
    (with-open-file (out-stream out-file :direction :output :if-exists :supersede)
      (permute-stream in-stream out-stream))))

First, this does nothing useful.  Second, all it does is wrap up a STL
function for use in batch processing.  If you had made the program a
pipe instead, I might see the point, but even then, a Lisp programmer
wouldn't have needed to wrap it up in the first place.  C++
programmers primarily use the Unix shell, so you'll need to wrap
functions up for the shell if you want to test them.  Lisp programmers
primarily use the REPL, so you can just call the function directly.

Common Lisp doesn't have a vector permutator built-in.  That said,
it's quite easy to build one.  Here's mine that I've used maybe 3 times:

  (defun map-permutations! (fn vector)
    (let ((end (1- (length vector))))
      (labels ((helper (start)
                 (if (= start end)
                     (funcall fn vector)
                     (loop for i from start to end
                           do (rotatef (aref vector start) (aref vector i))
                              (helper (1+ start))
                              (rotatef (aref vector start) (aref vector i))))))
        (helper 0)
        nil)))

  ;;; This just wraps it up in a syntax I prefer -- something you
  ;;; can't to in C++, BTW
  (defmacro do-permutations! ((var vector) &body body)
    `(map-permutations! #'(lambda (,var) ,@body) ,vector))

You can test it like this:

  * (do-permutations! (v #(1 2 3))
      (format t "~S~%" v))
  #(1 2 3)
  #(1 3 2)
  #(2 1 3)
  #(2 3 1)
  #(3 2 1)
  #(3 1 2)
  NIL

A more reasonable example, assuming you're not just trolling, would be
to construct a simple neural network (that's not build into either
language's standard library ;)

Consider all possible expressions formed by combining nine nines
using addition, subtraction, multiplication and division, and
arbitrary grouping with parentheses. Here is one possible
expression:

        ((9 + 9) - (9 * 9)) / (9 - ((9 + 9) / 9) * 9)

here is another:

        (9 + 9 - 9 * 9 * 9 / (9 + 9) + (9 * 9))

there is obviously large number of other expressions which combine 9
nines using these operators in all the possible ways. Your task is to
find the smallest positive integer which is not the value of any of
these expressions.

Let's see your C++ program which finds the result.

But then, you are using someone else's algorithms library to do it,
so maybe you don't have a fscking clue what it entails.

There is nothing you can do in C++ that you cannot do in Lisp (not LISP,
by the way). Any program which can be expressed succinctly in C++ can also
be expressed even more succinctly in Lisp, because the Lisp
program won't have to contain any stupid workarounds for limitations
in the C++ type system, syntax and other braindamage.  The reverse is
not the case; some Lisp programs can only be imitated by C++ programs
that are orders of magnitude larger, because they reimplement a good
proportion of common Lisp. Reimplement it badly, and reimplement it
in a way that is incompatible with everyone else's way of reinventing.

I suspect you will run into this when writing the code to solve the Nine
Nines problem above. My Lisp version is 47 physical lines.

Good luck.

(defun doit ()
  (with-open-file (in-stream "input.dat")
    (with-open-file (out-stream "output.dat" :direction :output)
      (let ((items (loop for item = (read in-stream nil in-stream)
                         until (eq item in-stream)
                         collect item)))
        (with-all-permutations (set (sort items #'<))
          (format out-stream "~{~A~^ ~}~%" set))))))

This makes use of the following facility for permutations on lists
(you have to include at least the macro before the doit function, if
you put everything in one file):

(defun permute (set function)
  (labels ((permute-one (tail)
             (if (null tail)
                 (funcall function set)
                 (loop for rest on tail do
                       (rotatef (first tail) (first rest))
                       (permute-one (rest tail))
                       (rotatef (first tail) (first rest))))))
    (permute-one set)))

(defmacro with-all-permutations ((var items) &body body)
  `(permute ,items #'(lambda (,var) ,@body)))

The code differs from the C++ version in the following:

a) The C++ STL comes with code for permutation building built-in.  CL
   doesn't, hence the need for the additional code.  So it is 20 LoC
   in C++ with STL against 8 + 12 LoC for CL.

b) The CL version doesn't produce superfluous whitespace at the end of
   each line, although it can trivially be changed to do that, if
   wanted, or produce more complex formats, e.g. use

          (format out-stream "~{~A ~}~%" set)

   to produce the C++ output, or use

          (format out-stream "~{~A~^, ~}~%" set)

   to produce lines like "1, 2, 3, 4", or use

          (format out-stream "~{~A~^;~}~%" set)

   to produce CSV files.

c) At least minimal error checking, for no added work.  The C++
   version silently assumes that a non-existant file means no entries,
   and hence produces an empty output file.  The Common Lisp version
   will raise an appropriate error in that case.

d) If we elide the sorting step, then the given code will work for all
   readable CL objects.  With the sorting step the code works for
   everything that is acceptable to #'<, i.e. all CL numeric types
   except for complex numbers.  Again you get useful error messages at
   runtime if you violate that condition.

e) Since we use the CL reader, comments, read-time conditionals and
   even read-time evaluation work as expected.

Of course the whole exercise is just silly, and doesn't show any of
CL's strengths, but who cares...

Regs, Pierre.

Anyways, if you mean backprop, IIRC according to one of the comp.ai FAQs,
C++ is actually the language of choice for this. I think what it said was
"it's *only* about 200 lines in C++". What I was asking in the OP was "what
are the things that Lisp is better suited for compared to C++".

12! * 12 * 2 / 1024^3 ~ 10.7 (12! lines, 12 elements per line, 2 bytes per
element, 1024^3 bytes per Gb)  Lighten up, kid.

  Have you considered downgrading your arrogance to a reasonable level?

  Here is a challenge for you.  Write a function that accepts an expression
  and a list of values for the variables and returns the lambda expression
  applied to these values.  (To reduce the complexity of the task when
  accepting an expression from the user, you may assume that a compiler is
  available in the function compile, so this is _not_ about making an
  evaluator.)  Call the function you write apply.

  For extra bonus points, write an evaluator using the apply function you
  just wrote, which evaluates all arguments of an expression before calling
  the function with the values collected from that evaluation.  Call this
  function eval.

  For even more extra bonusp points, write a function read that accepts a
  character stream and returns the next expression the user has supplied on
  that stream.  Match it with a function write that accepts an object of
  any kind and produces a character stream suitable for read and humans.

  If you have time, write a simple loop which calls read to obtain an
  expression from the user, then calls eval to obtain the result of
  evaluating it, and finally calls write to show the user this result.

  If you complete all this, you have what every Common Lisp programmer gets
  for free when he starts up his Common Lisp system.  Please think through
  the challenge before you dismiss any of this as trivial.  Basically, a
  major part of the Lisp language follows from the decision to make this
  interactive loop work correctly.  Note that in Common Lisp these
  functions are available from the get go with the names I have suggested.

  If you still think you have any business coming here with "challenges",
  please consider your own reaction to an ignorant splut who came up to you
  and "challenged" you do to something he had just learned.  _I_ find it on
  par with a stupid kid who has just learned a bad word and tries to get
  adults to say it so he can snicker.

I didn't propose any connection between this basic fact regarding
permutations, and calling you an idiot. You are now practising creative
reading comprehension.

Apparently, *you* think you are unique in knowing this factoid, otherwise
why would you deem it necessary to include that warning? Do you think
people are so stupid that they can't estimate for themselves how large
the output will be? If you want a group of people to take you seriously,
you have to take them seriously.

I used the phrase ``C++ spewing idiot'' because the article you wrote
is a pitifully naive apology for an idiotic library that is part of an
idiotic programming language, and because that you appear believe that
that generating permutations of a vector's elements is some kind of hot
computational problem that is out of the reach of the Lisp programming
language.

I wrote a permutation-generating program in elementary school, eighth
grade or thereabouts. Hand-assembled 6502 machine language on an
Apple II+. This is not exactly something that you can use to showcase
the capabilities of a programming language.

But what you are getting at is that it's not an analytic solution, but a
brute force solution; that is true, so be it. I saw in the problem
statement a little Lisp hacking opportunity for a rainy afternoon,
because that's what I was predisposed toward seeing at that time.

Say, how is the C++ version coming along?

*If* "yes", how about this: I wouldn't want to give you the answer,
especially that you might not even know it, but I'll post THE SUM OF ALL
DIGITS here *this* Sunday on the condition that you publicly promise that,
in case mine coincides with the sum of all digits of your answer or turns
out to be the correct one otherwise, you will start a new thread in this NG
with the subject "Wroot is the greatest" in which you will apologize for
your being an ass and a bigot (literally and succinctly). How does this
sound?

Wroot

Something that forces you to struggle bypassing C++'s static type system would
be IMHO a better example. You can even add some multiple inheritance for extra
suffering. };-)

For the OP: This C++ book is _full_ of great examples of things which are
trivial in CL, but atrocious monstruosities in C++.

Generative Programming: Methods, Tools, and Applications
by Krzysztof Czarnecki, Ulrich Eisenecker

PS: I remember reading about a shias religious celebration were people would
slap their heads until they bleed. This is very similar to what the authors of
that book are doing...

BTW, I wonder if there's an analytical solution to the problem, or the more
general n nines one... Totally useless, of course, but interesting. ;-)

Tell me you are only pretending to not understand the point of this!

I happen to develop in C++ for a living; I understand its strengths
and limitations.

My advice to you: see shrink and, also, go back to school, kiddo. Maybe
they'll teach you some respect for people who are smarter than you.

Would you care to unmask yourself of your pseudonym?

I reckon it could probably be done in about 60 (non-blank, non-
-comment) lines of C++ using the STL, but it would take me a factor
of 4 longer to do it than it did in Lisp. Of course, if you
measure productivity in LoC per unit time then C++ would come out
almost as good as Lisp on this exercise. :-)

  I'm trying to understand what it is that people like about LISP and
  whether I should learn it. (I'm interested in AI)

  Could somebody offer an example of a short (a few Kb or less)
  program in LISP that does something useful and that would be
  relatively hard and time-consuming to program in C++? (aside from
  such built-in niceties as arbitrary-precision arithmetic please)

It seems that since that time, you've developed a lot of concrete
ideas about what is and is not possible in Lisp and C++.

bruce@k7:~/programs/perl > cat nineNines.pl
#!/usr/bin/perl
my @nums = ({},{"9/1" => 9});
sub gcd {my ($a,$b)=@_; $a?gcd($a<=$b?($a,$b%$a):($b,$a)):$b};
for (my $n=1;$n<=9;++$n){
  for (my $p=1;$p<=$n/2;++$p){
    for my $a (keys %{$nums[$p]}){
      for my $b (keys %{$nums[$n-$p]}){
        "$a $b" =~ m!(-*\d+)/(-*\d+) (-*\d+)/(-*\d+)!;
        map {my ($a,$b)=@{$_};
             ($a,$b) = (-$a,-$b) if $b<0;
             my $g=gcd(abs($a),$b);
             $nums[$n]{$a/$g."/".$b/$g} = 9 if $b;
        }([$1*$4+$2*$3,$2*$4], [$1*$4-$2*$3,$2*$4], [$2*$3-$1*$4,$2*$4],
          [$1*$3,$2*$4], [$2*$3,$1*$4], [$1*$4,$2*$3]);
      }
    }
  }
  for (my $i=0;;++$i){
    next if $nums[$n]{"$i/1"};
    print "Smallest integer that can't be made from $n nines is $i\n";
    last;
  }

(setq nums (make-array '(10)))
(dotimes (i 10) (setf (aref nums i) (make-hash-table)))
(setf (gethash 9 (aref nums 1)) t)
(dotimes (n 10)
   (loop for p from 1 to (/ n 2) do
      (loop for a being the hash-keys of (aref nums p) do
         (loop for b being the hash-keys of (aref nums (- n p)) do
            (dolist (i (nconc (list (+ a b) (- a b) (- b a) (* a b))
                                    (if (/= a 0) (list (/ b a)))
                                    (if (/= b 0) (list (/ a b)))))
                                (setf (gethash i (aref nums n)) t)))))
   (format t "With ~D nines, can't make ~D~%" n
     (loop for i from 1 unless (gethash i (aref nums n)) do (return i))))

Or take the new Template-Numerical-Library (TNT) which
incorporates things like lu-factorization and therelike
(interestingly, this official libraray is 10 times too slow
compared to normal C). I would  not pay for it that it will run
with all C++ compilers.

What has this all to do with Common Lisp? It is a big plus that
Common Lisp does not show all the before-mentioned weakness. I
really appreciate this fact every day more and more.

A few weeks ago I have been a fanatic Clean fellow. I am not
a programmer for my living (academia...) but I have to use the
computer and numerical simulations for my PhD in climatoly. Okay,
what are the reasons, why I now believe Clean is not useful for
my work (I have to emphasize, that I can speak only for myself):

a) It is nearly ridiculous, that one in Clean is forced to write
floating-point numbers always with a precision of 16 places. There is
no direct way, e.g. to write in a precision-formatted way to a file.
Yes I have  a second-hand (thanks to Fabien T.) library which
can perform at least formatted single-precision output. But this
second hand library does not always work as  required.

b) Absolutely no control over numbers. A floating-point number is a
double-precison representation and an integer-number is a 32byte number.
You cannot say to Clean that you want your calculation with
single-precision, for example. Absolutely no way to round to a specific
precision.

c) No way of exception handling. And this is really severe, because
you cannot print-out intermediate results; there is one starting-
point and one ending-point. In bigger programs, debugging is awfull.

d) The case you have got a function B, which is called by function A,
BUT you do not actually use it (the function A), but you want to use B
with slightly different types, the compiler will complain, that B in A
does not match (even one does not use A). This is the reason why a Clean
programmer often is sitting 8 hours infront of his computer (running
Clean) but only for watching the screen and not typing something useful
in, because he is desperately afraid of Clean's notorious (and in most of
the cases not very informative) compiler complaints.

e) And the biggest problem: Array types and Clean's unique array type
concept (BELIEVE me, C's post-fece error is a pleasure to experience
compared to Clean's unique array concept). There are many array types in
Clean:

e.g. the 2 dimensional real ones:

!*{#*{Real}}, !{{Real}}, !*{#{#Real}}, !{#*{#Real}}, !{!{!Real}},
{#*{Real}}, {{Real}}, *{#{#Real}}, {#*{#Real}}, {{Real}},...

not enough the confusion, you cannot always pass every array to every type.
And array update (in-place) is *only* allowed in unique ones, but this is
often trial-and-error, because you get the wildest compiler errors that
often an unique array is expected but it is not deliverd. And as a programmer
your last chance is to copy the array. AND without any unique informations
one cannot update arrays!
This often absolutely destroys the concept of passing higher-order functions
(which have got as types unique-arrays), because you have then to copy the
array in order to fullfill the array concept. BUT sometimes you may pass
(and the compiler will not complain) arrays as functions, but I haven't
figured out when and why and there is absolutely no documentation discussing
the problem in depth.

f) Files are handeld the same way as unique array ones. I swear you: it is
a nightmare. I get pearls on my forehead when I think that I have
to re-use (addmittedly, a very tiny code base) Clean code (which I am writing for
my PhD). But I will leave Clean programming as soon as possible.

g) And sometimes the compiler produces side-effects (yes!) when updating arrays.
The underlying Clean concept has to be very complicated and error prone.

I write my experience here, because I often read in the computer-language
wars that Common Lispers, C++ victims... are ignorant to new innovations,
but when new innovation actually means that one has to experience the
abovementioned nightmares I think the ignorants are on the right way.

I have been exposed to two programming-language shocks in my life:

- Forth
- Clean

(I did not forget to mention C/C++; C++ is only complicated and maybe
one can learn it in 210 years of hard training, but C++ is not shocking).
I really contemplate to use Allegro Common Lisp for my future PhD work.
The development environment for Windows is really fantastic and even
for students is the expense of updating the license every 60 days
affordable. And when one holds his PhD he can easily buy (wages for
Postdocs are surely better) the complete package.

Corman Lisp shows also a good environment and Roger Corman is surely a very
talented programmer and profi but Corman Lisp is not really useful for
large floating-point arrays.

Will we see code, or is Wroot a pure troll?

It's possible to generate the list of values of all possible expressions
of N nines by combining the values of expressions of K nines (woof!) and
N - K nines over all operators and all relevant values of K.  If N is 1,
the only expression possible is 9, and If N is 2, the expressions are
(+ 9 9), (- 9 9), (/ 9 9) and (* 9 9).  All else follows by combination; for
N = 3, combine the N=1 and N=2 results in every possible way, and so on.

This approach should be a piece of cake in C++; an hour's work at
most.

My Lisp solution actually generates expressions, and evaluates them.
storing only the top level results into a hash table for the purpose of
finding the least positive integer that is not in the list.  My reason
for doing the puzzle in the first place was to explore this technique.

--
--Ed Cashin                     integrit file-verification system:
  ecas...@terry.uga.edu         http://integrit.sourceforge.net/

That's almost identical to my solution. :-) Oh, I forgot
to mention that two of my 16 (or, if you prefer, 21) lines
were FORMATs to keep track of what the program's doing as
it goes.

The other difference is that I wrote a bunch of (setf (gethash ...))
forms explicitly rather than a dolist. This hurt me less than it
would have hurt you because I didn't bother saving a factor of 2
by only looping half way up in the next-to-outer loop.

Is there a better way to set up the array of hashes at the start?  Perl
is *so* convenient for that.  OTOH, all those $$$ make me go blind.

I was also wondering if there was an easy way to bind a variable to
(aref nums n) in the loop that controls n, but I couldn't immediately
find one better than "and h = (aref nums n) then (aref nums n)", which
is no improvement.  I didn't want to use a separate line for a "let".