Tuesday, December 13, 2016

Heap's Algorithm and Generating Perl Code From Pseudocode

I've been researching recursion lately and in particular, permutations algorithms. This interest was spurred by a real-life case where such an algorithm would come in handy (combinations of @clients, @users, @tickets). I came across Wikipedia's entry for Heap's algorithm and the pseudocode illustrating the algorithm. I found the non-recursive version even more interesting specifically for its lack of needing to call itself, so I chose that version of the algorithm to study.

I thought it would be an interesting exercise to convert the pseudocode to Perl code. While I was converting it I was struck by how closely the Perl code could be made to look like the pseudocode, but also how easy idiomatic Perl made it to skip certain parts of the pseudocode altogether, so I wrote two separate Perl implementations of the algorithm: one to mirror the pseudocode as closely as possible, and one to cut corners using idiomatic Perl.

First, the "pseudocode" version:

  1. sub output {
  2. my (@to_print) = @_;
  3. print join( ',', @to_print ), "\n";
  4. }
  5. sub is_even {
  6. return $_[0] % 2 ? 0 : 1;
  7. }
  8. # By referring to $_[0] and $_[1] instead of assigning their values to other
  9. # variables, we can force pass-by-reference here so that the change will
  10. # impact @A directly even though we are in a separate function outside its
  11. # scope.
  12. sub swap {
  13. ($_[0],$_[1]) = ($_[1],$_[0]);
  14. }
  15. sub generate {
  16. my ($n, @A) = @_;
  17. my @c;
  18. for ( my $i = 0; $i < $n; $i += 1 ) {
  19. $c[$i] = 0;
  20. }
  21. output(@A);
  22. my $i = 0;
  23. while ( $i < $n ) {
  24. if ( $c[$i] < $i ) {
  25. if ( is_even($i) ) {
  26. swap( $A[0], $A[$i] );
  27. }
  28. else {
  29. swap( $A[ $c[$i] ], $A[$i] );
  30. }
  31. output(@A);
  32. $c[$i] += 1;
  33. $i = 0;
  34. }
  35. else {
  36. $c[$i] = 0;
  37. $i += 1;
  38. } # end if
  39. } # end while
  40. }
  41. generate( 3, 'work', 'sleep', 'play' );

Output:

work,sleep,play
sleep,work,play
play,work,sleep
work,play,sleep
sleep,play,work
play,sleep,work

Next, the idiomatic Perl version:

  1. sub output {
  2. print join( ',', @_ ), "\n";
  3. }
  4. sub generate {
  5. # We don't need to pass n here because we have @A. That's not at all
  6. # unique to Perl of course but the cool part comes later...
  7. my (@A) = @_;
  8. # I don't need to specify the length of array @c because as soon as we
  9. # refer to an element, it exists. I don't need to initialize @c or $i
  10. # because as soon as we start performing math on their values they will be
  11. # assumed to start at zero.
  12. my (@c,$i);
  13. output(@A);
  14. # The cool part: we can refer to the length of the @A array as simply @A
  15. # in scalar context.
  16. while ( $i < @A ) {
  17. if ( $c[$i] < $i ) {
  18. # Test for is_odd by seeing if modulo 2 of $i is non-zero.
  19. # Since we check for is_odd vs is_even, we swap the code in the
  20. # if-else.
  21. if ( $i % 2 ) {
  22. # The swap function was handy but idiomatic Perl allows us to
  23. # swap variables in place
  24. ( $A[ $c[$i] ], $A[$i] ) = ( $A[$i], $A[ $c[$i] ] );
  25. }
  26. else {
  27. ( $A[0], $A[$i] ) = ( $A[$i], $A[0] );
  28. }
  29. output(@A);
  30. # Nitpicky but it's nice to have ++ instead of += 1. Again, not
  31. # limited to Perl.
  32. $c[$i]++;
  33. $i = 0;
  34. }
  35. else {
  36. $c[$i] = 0;
  37. $i++;
  38. }
  39. }
  40. }
  41. generate( split '', 'abc' );

Output:

a,b,c
b,a,c
c,a,b
a,c,b
b,c,a
c,b,a

In what ways could the program be further reduced?


EDIT: A change by an anonymous commenter makes this even more compact:

  1. sub output {
  2. print join( ',', @_ ), "\n";
  3. }
  4. sub generate {
  5. my (@A) = @_;
  6. output(@A);
  7. while ( $i < @A ) {
  8. if ( $c[$i] < $i ) {
  9. my $x = $i % 2 ? $c[ $i ] : 0;
  10. ( $A[ $x ], $A[$i] ) = ( $A[$i], $A[ $x ] );
  11. output(@A);
  12. $c[$i]++;
  13. $i = 0;
  14. }
  15. else {
  16. $c[$i] = 0;
  17. $i++;
  18. }
  19. }
  20. }
  21. generate( split '', 'abcd' );

2 comments:

Anonymous said...

Consider allowing the use of "pre" tag for code.

Diff follows ...

Simply find the index to use instead of repeating swap ops.
---
heap.pl | 11 ++---------
1 file changed, 2 insertions(+), 9 deletions(-)

diff --git heap.pl heap.pl
index 5ba5508..2fcacb1 100755
--- heap.pl
+++ heap.pl
@@ -37,15 +37,8 @@ sub generate {
# Test for is_odd by seeing if modulo 2 of $i is non-zero. Since we
# check for is_odd vs is_even, we swap the code in the if-else.

- if ( $i % 2 ) {
- # The swap function was handy but idiomatic Perl allows us to swap
- # variables in place
- ( $A[ $c[$i] ], $A[$i] ) = ( $A[$i], $A[ $c[$i] ] );
- }
- else {
- ( $A[0], $A[$i] ) = ( $A[$i], $A[0] );
- }
-
+ my $x = $i % 2 ? $c[ $i ] : 0;
+ ( $A[ $x ], $A[$i] ) = ( $A[$i], $A[ $x ] );
output(@A);

# Nitpicky but it's nice to have ++ instead of += 1. Again, not limited

David M. Bradford said...

Good catch! Also I looked for an option to enable additional tags and I don't see one. Let me know if you happen to know where Google keeps it.