Re^2: Please help me understand this permutation sub?

Thanks LanX,

Your added print statements are very similar to what I had been using myself, but far more visually helpful.

My problem stems from this point in the output:

 1:
  2:a
   3:ab
    4:abc
     5:abcd
abcd
    4:abd
     5:abdc
[download]

I understand the 1:-5: lines, and the bare abcd. I get how they were generated and where they came from. But I am not following the logic of how it then goes from $perm = abcd and @set=[] to $perm = abd and @set=[c], or how $level went from 5 back to 4.

Any way you would be able to clarify that?

Thanks!

Matt

Comment on Re^2: Please help me understand this permutation sub? Select or Download Code

Replies are listed 'Best First'.
Re^3: Please help me understand this permutation sub? by LanX (Saint) on Dec 09, 2020 at 12:26 UTC
Hi here new code to highlight whats happening. Please note the recursion here is effectively used to implement 4 nested loops, see second part of the code #https://perlmonks.org/?node_id=11124854 use strict; use warnings; use Data::Dump qw/pp dd/; use 5.10.0; sub permutation { my ($perm,@set) = @_; my $level = 5 - @set; my $marker = " "x$level . "$level: " ; say "$marker ENTER perm='$perm' set=(@set)"; unless (@set) { say "$marker RESULT: $perm"; } else { permutation( $perm.$set[$_], @set[0..$_-1], @set[$_+1..$#set] ) for (0..$#set); } say "$marker RETURN"; return; } my @input = (qw/a b c d/); permutation('',@input); my @set = @input; my $perm = ""; for (0..3) { # level 1 my @set =@set; my $perm = $perm . splice @set,$_,1; for (0..2) { # level 2 my @set =@set; my $perm = $perm . splice @set,$_,1; for (0..1) { # level 3 my @set =@set; my $perm = $perm . splice @set,$_,1; for (0..0) { # level 4 my @set =@set; my $perm = $perm . splice @set,$_,1; say $perm; # level 5 } } } } [download] (shortened) output -- mode: compilation; default-directory: "d:/tmp/pm/" -- Compilation started at Wed Dec 9 13:22:51 C:/Perl_524/bin\perl.exe -w d:/tmp/pm/permute.pl 1: ENTER perm='' set=(a b c d) 2: ENTER perm='a' set=(b c d) 3: ENTER perm='ab' set=(c d) 4: ENTER perm='abc' set=(d) 5: ENTER perm='abcd' set=() 5: RESULT: abcd 5: RETURN 4: RETURN 4: ENTER perm='abd' set=(c) 5: ENTER perm='abdc' set=() 5: RESULT: abdc 5: RETURN 4: RETURN 3: RETURN 3: ENTER perm='ac' set=(b d) 4: ENTER perm='acb' set=(d) 5: ENTER perm='acbd' set=() 5: RESULT: acbd 5: RETURN 4: RETURN 4: ENTER perm='acd' set=(b) 5: ENTER perm='acdb' set=() 5: RESULT: acdb 5: RETURN 4: RETURN 3: RETURN ### shortened ... ### Nested Loops abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba Compilation finished at Wed Dec 9 13:22:51 [download] Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re^4: Please help me understand this permutation sub? by mdunnbass (Monk) on Dec 09, 2020 at 14:06 UTC
That output is gorgeous. And makes it crystal clear! Thank you!!!	[reply]
Re^3: Please help me understand this permutation sub? by LanX (Saint) on Dec 09, 2020 at 08:39 UTC
The variables at each call frame level are independent and reestablished after returning from a sub call. The for loop at level 3 calls the recursion at level 4 each time twice before returning to level 2 `3:ab # for @set=(c,d); return to 2 4:abc # ... 4:abd # ...` [download] Level 4 calls level 5 once and returns to 3 `4:abc # for @set=(d); return to 3 5:abcd # print result; return to 4 # ... later 4:abd # for @set=(c); return to 3 5:abdc # print result; return to 4` [download] update > But I am not following the logic of how it then goes from $perm = abcd and @set=[] to $perm = abd and @set=c, or how $level went from 5 back to 4. ... 5 printed "abcd" and returned to 4; 4's loop over (d) was exhausted and returned to 3; 3 looping over (c,d) stepped to the second element and called 4, i.e. `perm("abd", "c")` 4 loops over (c) and calls 5; 5 printed "abdc" and returned to 4; ... HTH :) update Bill's remark is spot on, the explicit "return" is fake, the real return happens implicitly after the loop. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l] [select]
Re^4: Please help me understand this permutation sub? by mdunnbass (Monk) on Dec 09, 2020 at 14:04 UTC
This: 5 printed "abcd" and returned to 4; 4's loop over (d) was exhausted and returned to 3; 3 looping over (c,d) stepped to the second element and called 4, i.e. perm("abd", "c") 4 loops over (c) and calls 5; 5 printed "abdc" and returned to 4; This is what triggered understanding in my brain. Thank you! Your explanation was just what I needed! I really appreciate the effort you went through to help me get this. Thanks.	[reply]

update

update