please help me to understand this code?

[Pilcrow]

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;

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

 

[J. Gleixner]

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.

A lot can be discovered on your own by using print and/or
Data:umper. Add a few calls to print or Dumper, to see
various values, to help you see what's happening. If
you have a specific question about a certain line/syntax,
then ask.

Perhaps someone will also tell me the source for "The Fischer-Krause
Algorithm", since TAOCP, vol 4 is still unpublished?

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.

 

[Tim Greer]

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;

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

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?

 

[xhoster]

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.

I will explain the parts peculiar to Perl.

Perhaps someone will also tell me the source for "The Fischer-Krause
Algorithm", since TAOCP, vol 4 is still unpublished?

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
"Just follow the pointer math"

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

sub permute (&@) {

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

my $code = shift;
my @idx = 0..$#_;
while ( $code->(@_[@idx]) ) {

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]);

my $p = $#idx;
--$p while $idx[$p-1] > $idx[$p];

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

my $q = $p or return;

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

push @idx, reverse splice @idx, $p;

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

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

++$q while $idx[$p-1] > $idx[$q];
@idx[$p-1,$q]=@idx[$q,$p-1];

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

}
}


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

{ 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
leading and trailing empty strings.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.

 

[Pilcrow]

A lot can be discovered on your own by using print and/or
Data:umper. Add a few calls to print or Dumper, to see
various values, to help you see what's happening. If
you have a specific question about a certain line/syntax,
then ask.


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.

Sorry to have disturbed Your Majesty

 

[Pilcrow]

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;

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

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?

Sorry to have disturbed Your Holiness

 

[Pilcrow]

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.

I will explain the parts peculiar to Perl.

Perhaps someone will also tell me the source for "The Fischer-Krause
Algorithm", since TAOCP, vol 4 is still unpublished?

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
"Just follow the pointer math"

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

sub permute (&@) {

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

my $code = shift;
my @idx = 0..$#_;
while ( $code->(@_[@idx]) ) {

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]);

my $p = $#idx;
--$p while $idx[$p-1] > $idx[$p];

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

my $q = $p or return;

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

push @idx, reverse splice @idx, $p;

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

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

++$q while $idx[$p-1] > $idx[$q];
@idx[$p-1,$q]=@idx[$q,$p-1];

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

}
}


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

{ 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
leading and trailing empty strings.

Xho

Thank you so much for your help!

 

[Tim Greer]

Sorry to have disturbed Your Holiness

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
reply to it?

 

[Pilcrow]

You are making these snide comments in response to everyone that replied
to you.

not everyone

 

[Tim Greer]

not everyone

Okay then, everyone except one. Anyway, I hope you found your answer.

 

[cartercc]

Sorry to have disturbed Your Majesty

You have needlessly offended two people who regularly post to c.l.p.m.
and prove helpful on a regular basis. If you have read this group for
a while, you know that the usual method of 'helping' is to point those
who ask for help to the appropriate resources. The theory is that
those needing help also need to learn how to help themselves. I
thought G's advice was very good. You need to know how to use Data
Dumper, and you need to know how to print intermediate values from
your programs. These are pearls (or perls) of wisdom, but I suppose
that G got what he deserved by casting his pearls before swine, or a
swine, which is exactly what you seem by your response. My guess is
that he will be reluctant to respond to your posts in the future,
which is very much to your loss.

My response to your question is similar: type the code into your
interpreter and see how it runs. Except I would have recommended using
the Perl debugger ... run the program with the -d switch.

The proverb is: Give a hungry man a fish and you feed him for a day;
teach him to fish and you feed him for a lifetime. Except in you case
it becomes: Set a cold man before a fire and you warm him for an hour;
set him on fire and you warm him for a lifetime.

CC

 

[Pilcrow]

I suppose
that G got what he deserved by casting his pearls before swine, or a
swine, which is exactly what you seem by your response.

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
would become your comrade in filth, and I prefer not to.

 

[Tim McDaniel]

I was sarcastic. I was not insulting.

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
answer.

 

[Tad J McClellan]

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.

So did I.

I have taken the appropriate steps.

And "look up the algorithm
and dump data while the Perl code executes" is an appropriate first
answer.

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...

 

[J. Gleixner]

Sorry to have disturbed Your Majesty

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.

 

[J. Gleixner]

You have needlessly offended two people who regularly post to c.l.p.m.
and prove helpful on a regular basis. If you have read this group for
a while, you know that the usual method of 'helping' is to point those
who ask for help to the appropriate resources. The theory is that
those needing help also need to learn how to help themselves. I
thought G's advice was very good. You need to know how to use Data
Dumper, and you need to know how to print intermediate values from
your programs. These are pearls (or perls) of wisdom, but I suppose
that G got what he deserved by casting his pearls before swine, or a
swine, which is exactly what you seem by your response. My guess is
that he will be reluctant to respond to your posts in the future,
which is very much to your loss.

Nah, I just laugh, and wonder how some people never learn to
do anything on their own. Either that or it's their
first day using this here Internet/Usenet thingamajig.

My response to your question is similar: type the code into your
interpreter and see how it runs. Except I would have recommended using
the Perl debugger ... run the program with the -d switch.

Yeah, I was going to suggest that, however if someone doesn't know
that they can use a few calls to 'print' in their code to help them
see what it's doing, then the debugger is likely a few levels
above their knowledge of the language.

 

[Pilcrow]

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.".

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.

 

[Pilcrow]

I too perceived you as being insulting.

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.

 

[cartercc]

All this is OT, and I had decided to reply, waiting for two days, but
now I will reply. Please note that this is NOT to be interpreted as
personally insulting, as I have no wish to insult you.


This is what you wrote, a sarcastic and offensive reply to someone who
I cannot recall ever being sarcastic or offensive himself. You said
'Your Majesty' when you really meant, 'Peon: Who are you to decline to
give Me, My Majesty, exactly what I want.'

In point of fact, Gleixner gave you some very good advice, which is a
lot more useful to you that would have been a line by line exposition
of the algorithm. I, too, had a similar issue with a very neat little
trick called a Schwartzian Transform. I stared at it for (literally)
years trying to understand it before I ran it (with the debugger) and
examined the state of the runtime stack value by value. The BAST way
to understand an algorithm is to step through it, examining the state
of each data item as you go.

If you don't know how to do this, or don't think it's a legitimate
approach to understanding a piece of code, well, you've just
embarrassed yourself a second time in c.l.p.m.

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.  

Okay, I was making a literary reference. The book is very well known -
you may have heard of it - it's called the Bible. My reference was to
a conversation one of the major characters, Jesus, had with some
friends. It's actually a two part quote, but I omitted the second part
in order to emphasize it, thinking that you would complete the quote
in your mind. Since you appear not to be familiar with this, or too
dimwitted to recognize it, I'll do this for you.

The second part goes like this: "... lest they trample them underfoot
and then turn and devour you." My point was that G. had attempted to
bestow a precious gift to you which you not only threw back in his
face but added personal insult. Please think about these words before
you reply.

I was sarcastic..  I was not insulting.  I am capable, in several
languages, of saying extremely insulting, vile, things.  But then, I
would become your comrade in filth, and I prefer not to.

I didn't say that you WERE a swine, simply that your words SEEMED to
make you so. There is a difference. You are not your words, and if by
some chance you use words (out of thoughtlessness or irritation,
maybe) that you don't mean, you can always take them back. I guess
that in this case you meant the remark about 'Your Majesty' so I'll
have nothing further to say on the subject.

CC

 

[Pilcrow]

All this is OT, and I had decided to reply, waiting for two days, but
now I will reply. Please note that this is NOT to be interpreted as
personally insulting, as I have no wish to insult you.



This is what you wrote, a sarcastic and offensive reply to someone who
I cannot recall ever being sarcastic or offensive himself. You said
'Your Majesty' when you really meant, 'Peon: Who are you to decline to
give Me, My Majesty, exactly what I want.'

In point of fact, Gleixner gave you some very good advice, which is a
lot more useful to you that would have been a line by line exposition
of the algorithm. I, too, had a similar issue with a very neat little
trick called a Schwartzian Transform. I stared at it for (literally)
years trying to understand it before I ran it (with the debugger) and
examined the state of the runtime stack value by value. The BAST way
to understand an algorithm is to step through it, examining the state
of each data item as you go.

If you don't know how to do this, or don't think it's a legitimate
approach to understanding a piece of code, well, you've just
embarrassed yourself a second time in c.l.p.m.


Okay, I was making a literary reference. The book is very well known -
you may have heard of it - it's called the Bible. My reference was to
a conversation one of the major characters, Jesus, had with some
friends. It's actually a two part quote, but I omitted the second part
in order to emphasize it, thinking that you would complete the quote
in your mind. Since you appear not to be familiar with this, or too
dimwitted to recognize it, I'll do this for you.

The second part goes like this: "... lest they trample them underfoot
and then turn and devour you." My point was that G. had attempted to
bestow a precious gift to you which you not only threw back in his
face but added personal insult. Please think about these words before
you reply.


I didn't say that you WERE a swine, simply that your words SEEMED to
make you so. There is a difference. You are not your words, and if by
some chance you use words (out of thoughtlessness or irritation,
maybe) that you don't mean, you can always take them back. I guess
that in this case you meant the remark about 'Your Majesty' so I'll
have nothing further to say on the subject.

CC

I was hoping not to have to do this, but (sigh)..

Last month I happened to see an article asking for help with homework.
"Camel" <[email protected]> in article
<[email protected]> asked how to print all the
permutations of a string of digits of arbitrary length. Several
people replied, but seemed more interested in preening themselves in
their superiority to "Camel" than in actually helping him.

Not knowing how to do it myself, I started playing around. It is
relatively easy to write a program to print all the permutations of a
list, or array (yes I know the difference) if you already know the
length of the input list. But to permute a list whose length is not
known in advance is more difficult.

Eventually I came across perlfaq 4.51 (perldoc -q permute), and the
code that I quoted in my original message.

I tried to understand both the algorithm (Fischer-Krause Algorithm)
and most of the perl idiom implementing it. The code worked as
advertized, but how?

My enquiry started by a search of Wikipedia. No luck. Then I tried a
google search. Almost all the documents returned were various
mirrors, throughout the world, of perlfaq4 or perlfaq 4.51. Several
documents were in Japanese, several in German. I read neither. Some
documents mention it in passing. From one of those I learned that the
algorithm dated from 1819! One result,from ACM, wanted me to pay $198
before downloading a PDF document (without being sure of its
relevance).

In the meantime I was playing with the code from faq 4.51, with very
small results.

Then I posted my query. I didn't want to recite the details of my
lengthy investigation, so I simply asked my questions.

The first two responses assumed I had done nothing to help myself. Mr
Gleichner told me about Data:umper and print, both familiar to me
for a number of years. Then he told me to search the internet.

Mr Greer said:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Did he not see that I had told him the source of the code? And then he
excused himself from helping, since it wouldn't do any good!

So I made a couple of quick remarks to both of those snobs. Am I
depriving myself of their help? What help? I called one "Your
Majesty", the other "Your Holiness". Insulting? Only if you think
comparison to majesty and holiness is insulting.

Now to you: I knew the provenience of 'pearls before swine', and I
probably came into contact with the Bible several decades before you
did. (You don't know how ancient I am.) Perhaps you don't realize that
Jesus was Jewish, and the Jews have a profound revulsion to anything
having to do with swine. To call someone 'swine' was an insult then
and it is an insult now. But I forgive you, for you know not what you
do.

I also came into contact with the "Schwartzian Transform" a number of
years ago, but I didn't need the debugger to understand it.
Incidentally, Wikipedia has an excellent article on it, in which it is
explained that the idea is not original with Randal L. Schwartz, nor
with perl.

Now that I have a better understanding of the Fischer-Krause
Algorithm, thanks largely to xhoster, perhaps I will write an article
about it on Wikipedia, unless, of course, one of you folks, in your
infinite superiority to me, beats me to it. The race is on!


__
Evybuddy needs sumbuddy that they kin look down on.
Eff yo aint got no wun else, why, hep yoseff to me.