Velocity Reviews > Perl > please help me to understand this code?

# please help me to understand this code?

Pilcrow
Guest
Posts: n/a

 01-08-2009
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
Guest
Posts: n/a

 01-08-2009
Pilcrow wrote:
> 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
Guest
Posts: n/a

 01-08-2009
Pilcrow wrote:

> 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?
--
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!

xhoster@gmail.com
Guest
Posts: n/a

 01-08-2009
Pilcrow <(E-Mail Removed)> wrote:

> 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
Guest
Posts: n/a

 01-09-2009
On Thu, 08 Jan 2009 13:59:26 -0600, "J. Gleixner"
<(E-Mail Removed)> wrote:

>Pilcrow wrote:
>> 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.

Sorry to have disturbed Your Majesty

Pilcrow
Guest
Posts: n/a

 01-09-2009
On Thu, 08 Jan 2009 13:08:57 -0800, Tim Greer <(E-Mail Removed)> wrote:

>Pilcrow wrote:
>
>> 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
Guest
Posts: n/a

 01-09-2009
On 08 Jan 2009 22:36:19 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

>Pilcrow <(E-Mail Removed)> wrote:
>
>> 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
Guest
Posts: n/a

 01-09-2009
Pilcrow wrote:

>
> 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?
--
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!

Pilcrow
Guest
Posts: n/a

 01-09-2009
On Fri, 09 Jan 2009 10:31:35 -0800, Tim Greer <(E-Mail Removed)> wrote:

>Pilcrow wrote:
>
>>
>> Sorry to have disturbed Your Holiness

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

not everyone

Tim Greer
Guest
Posts: n/a

 01-09-2009
Pilcrow wrote:

> On Fri, 09 Jan 2009 10:31:35 -0800, Tim Greer <(E-Mail Removed)>
> wrote:
>
>>Pilcrow wrote:
>>
>>>
>>> Sorry to have disturbed Your Holiness

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

>
> not everyone

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!

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post HalcyonWild Java 4 09-30-2005 05:44 AM needin4mation@gmail.com ASP .Net 4 08-31-2005 07:35 AM success_ny@yahoo.com Java 12 08-29-2005 06:06 PM thelisa martin Computer Support 2 08-18-2005 06:40 AM KK C++ 2 10-14-2003 02:08 PM

Advertisments