#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
The following is part of faq 4.51.  I am afraid that a good deal of it
is beyond my understanding, and, I suspect, beyond the understaning of a
good many others who read clpm.  It works, but I don't know how. Perhaps
some genius will explain it, line by line, to me and the other dummies.
Perhaps someone will also tell me the source for "The Fischer-Krause
Algorithm", since TAOCP, vol 4 is still unpublished?

Thank you very much, in advance.

~~~~~~~~~~~~~~~~~~~~~~~~~ quote ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Here's a little program that generates all permutations of all the words
on each line of input. The algorithm embodied in the "permute()"
function is discussed in Volume 4 (still unpublished) of Knuth's *The
Art of Computer Programming* and will work on any list:

#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
my \$code = shift;
my @idx = 0..\$#_;
while ( \$code->(@_[@idx]) ) {
my \$p = \$#idx;
--\$p while \$idx[\$p-1] > \$idx[\$p];
my \$q = \$p or return;
push @idx, reverse splice @idx, \$p;
++\$q while \$idx[\$p-1] > \$idx[\$q];
@idx[\$p-1,\$q]=@idx[\$q,\$p-1];
}
}

permute { print "@_\n" } split;

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Pilcrow wrote:

A lot can be discovered on your own by using print and/or
Data::Dumper.  Add a few calls to print or Dumper, to see
you have a specific question about a certain line/syntax,

Perhaps you can find that on your own using your favorite Internet
search engine?

Using on returned: "Results 1 - 10 of about 393 for Fischer-Krause
algorithm.", so there are a lot of possible pages to read.

On Thu, 08 Jan 2009 13:59:26 -0600, "J. Gleixner"

Sorry to have disturbed Your Majesty

wrote:

I don't remember using language remotely as offensive as yours, but
perhaps you have not got the mental facility to insult a person without
yourself crawling into the gutter.

I was sarcastic..  I was not insulting.  I am capable, in several
languages, of saying extremely insulting, vile, things.  But then, I

The American Heritage dictionary defines sarcasm as "1. A cutting,
often ironic remark intended to wound. ... intended to make its victim
the butt of contempt or ridicule.".

I too perceived you as being insulting.  And "look up the algorithm
and dump data while the Perl code executes" is an appropriate first

--
Tim McDaniel, tmcd@panix.com

So did I.

I have taken the appropriate steps.

Even more appropriate was

If so, what
parts are you not understanding?  What parts _do_ you understand?
Knowing this will be helpful to giving you the best answer, without
anyone having to go into great detail or explain every aspect

Surely we weren't expected to

> my \$code = shift;

my declares a variable.
= is an assignment, it stores the expr on the RHS into the
variable on the LHS
shift() with no arguments shifts @_ when called in a subroutine

so altogether, that line stores the subroutine's 1st arg in \$code.

> my @idx = 0..\$#_;

.. is the range operator it creates a list that goes up by 1 starting
from its left operand and ending with its right operand

\$#ARRAYNAME returns the last index of the @ARRAYNAME array

etc...

--
email: perl -le "print scalar reverse qq/moc.noitatibaher0cmdat/"

On Fri, 9 Jan 2009 22:19:15 +0000 (UTC), tmcd@panix.com (Tim McDaniel)
wrote:

After consulting Merriam-Webster  online, I see that I was being
ironic,rather than sarcastic.  I seem often to confuse the two.  It was
not my intention to insult, but the boor who called me a 'swine'
intended insult.

On Fri, 9 Jan 2009 22:19:15 +0000 (UTC), tmcd@panix.com (Tim McDaniel)
wrote:

I have an image, now, of a princess, atop 100 mattresses, atop a pea.
Sorry about that pea, princess.  But you have to make allowances for a
swine like me.  Oink, oink.

Pilcrow wrote:

Majesty",  the other "Your Holiness".  Insulting?  Only if you think

You posted random code, as far as everyone here could know, which you
might have just found and not have known if it's even relevant (believe
it or not, that happens).  You could have quickly mentioned your issue
and goal, and that you know what "this part does" and maybe asked about
some specific function.

You might not have known what the shebang line was and -n, you might
not have known what "sub" meant, or (&@), or "my", "shift", etc.  You
might not have known the difference between = and ==.  You might not
have known what \$var and @var were, or that lines starting with # are
comments.  You might not have known what "while" is, or what --\$q or
++\$q do (or for that matter, the differences between --\$q and \$q--, or
what \$idx[\$p-1] is, or what return does.  You might not have known what
push does, or reverse, or splice, or split, or how curly braces work,
and on and on.  Just exactly where does the answer start or end? Should
I have made a reckless attempt to answer you anyway, and risked
confusion or not actually helping you (after wasting who knows how much
time with the reply, depending on the detail of the answer)?  Granted,
if someone believes they understood and have some theory about what
should be an appropriate answer, that's great, but if someone doesn't
have anything to go on, you run that risk (and probably risk being
insulted in response anyway, if someone's that unreasonable).

I didn't excuse myself from helping, I was asking a genuine question.  I
actually started to reply, but then thought "what good would it do to
break it down, if it'll only lead to more questions or cause the OP
(you) confusion?"  It might not have helped.  Surely, you knew what
_some_ of the code did, so what parts were you asking about?  That
allows people to follow up with more relevant and more
detailed/in-depth responses that contain the answers you are looking
for.  I had no way to determine what level of understanding you were
at, so I didn't know how to reply and chance misleading you.  Not
giving people here the benefit of the doubt, whom are genuinely here
interested in offering help to posters, you start making snide and rude
remarks, which is really immature.

You think people post help here just to try and act superior?  I urged
you to clarify the information you were asking about, so I could offer
help.  Apparently that's not rational regardless of what was said or
the intent, you'd rather pass insults?  You can plainly see that my
asking you was not whatsoever intended to make you feel like less of a
person, but to understand the question so I could help.  There's no
reason to be terse and rude.  I am fully aware that there are arrogant
people on any news group out there, and you pretty much can't go
anywhere online and ask a simple question in a friendly and civil
manner, without some person with "issues" that will want to attack you
or try and act like a know it all, but don't let that fact make you
believe that everyone is like that, or to jump the gun and assume that
about people without some grounds to actually form that opinion.
Seriously, blaming your rudeness and inability to act civil on what
other people do, isn't going to win you any sympathy.  If my reply in
an attempt to gather the information needed to properly assist you came
off as rude or snobbish, than I apologize, because that was absolutely
not the intent.
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

*SKIP*

You know what?  That doesn't matter how old you are, "Posting History"
that what matters.  What you did was childish (even if you had a cause).
And, just in case you care, saying "PLONK" isn't considered as social
requirement.  And now you must find your way out of killfile (as if it
would be possible).

Look, I wasn't born on USENET actually.  There's other world, that world
has rules, accidentally they written in POLICY (even if noone cares).
And there're simple words written (they are in my heart) --

Don't Annoy.  And Don't Be Easily Annoyed.

*CUT*

--
Torvalds' goal for Linux is very simple: World Domination
Stallman's goal for GNU is even simpler: Freedom

Pilcrow wrote:

Why post a question here and wait for hours/days to possibly get
a reply when you can do most of it on your own, in seconds?

Posting to a newsgroup should not be your first stop when you
have a question.  Knowing how to debug code or how to read books
or even how to type three words into your favorite search engine
are useful skills.

Pilcrow wrote:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It says what it does, so I assume you mean the actual code?  If so, what
parts are you not understanding?  What parts _do_ you understand?
Knowing this will be helpful to giving you the best answer, without
anyone having to go into great detail or explain every aspect (since if
you didn't know any of it, it probably wouldn't do you any good to have
someone explain it when it comes down to it).  That is, you must have
looked for or saw this code somewhere and wanted to use it, so you must
have some idea of what it does?
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

Sorry to have disturbed Your Holiness

Pilcrow wrote:

You are making these snide comments in response to everyone that replied
to you.  My reply was genuine, if you can outline what you currently
understand or not, it'll help make it easier.  That is, do you
understand what a sub routine is, what shift does, what while does,
what a hash and an array are, what push does, what reverse does, what
an array splice is, increment and decrement operators, what split does,
etc.?  There's no reason to be so defensive and sarcastic in response.
Honestly, why post the question if you're going to insult people that
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

not everyone

Pilcrow wrote:

Okay then, everyone except one.  Anyway, I hope you found your answer.
--
Tim Greer, CEO/Founder/CTO, BurlyHost.com, Inc.
Shared Hosting, Reseller Hosting, Dedicated & Semi-Dedicated servers
and Custom Hosting.  24/7 support, 30 day guarantee, secure servers.
Industry's most experienced staff! -- Web Hosting With Muscle!

I will explain the parts peculiar to Perl.

I'm surprised there isn't a wikipedia entry, but there doesn't seem to
be one.  Hunh.  It is quite subtle, and I can't explain other than to say

Takes a code block/anonymous subroutine reference and a list.

Executes the code block on each permutation of the list.  If the
code block ever returns false, then it aborts the permutations early
(your code block should not return false, as printing to STDOUT rarely
fails. so you probably don't take advantage of this feature).  This could
also be written something like:

while ( 1 ) {
return unless \$code->(@_[@idx]);

Subtle code that implements Fischer-Krause, not peculiar to Perl.

If \$p is zero, then you have finished all permutations.  "return"
terminates the execution of this subroutine at that point.

reverses the part of @idx from \$p on.  I think it might be better written
as:

@idx[\$p..\$#idx]=reverse @idx[\$p..\$#idx];

More subtle code that implements Fischer-Krause, not peculiar to Perl.
(The last line swaps the elements of @idx at \$p-1 and \$q).

{ print "@_\n" } is the code block that gets executed for each permutation.
If you wanted to do something other than printing the permutations, you
would use a different block here.

split with no arguments splits the contents of \$_ on whitespace, stripping

Xho

--
The costs of publication of this article were defrayed in part by the