in reply to permutation algorithm

Here is the loop structure to your problem:

use strict; my @list = (-25, 14, 50, 20, -7, -8, -10); my @result = (); my $sum; for my $elem (@list) { for (@{[@result]}) { push @result, [ @$_, $elem ]; $sum = eval join '+' => @{$result[-1]}; print join(',', @{$result[-1]}), "\n" unless $sum; } push @result, [ $elem ]; print $elem, "\n" unless $elem; }

Result:

-25,50,-7,-8,-10

You will need some additional work in order to obtain array indexes instead of values.

How it works:

  • In first pass, it will ignore the inner for and it will push [ -25 ] into @result. Result is [ [-25] ]
  • In second pass, it will push 14 into a copy of what it already has, and then it will push [ 14 ]. Result is: [ [-25], [-25,14], [14] ]
  • In second pass, it will push 50 into a copy of what it already has, and then it will push [ 50 ]. Result is: [ [-25], [-25,14], [14], [-25,50], [-25,14,50], [14,50], [50] ]
  • While it does that, it will print whatever combinations that sum zero.
  • That's it!

    Replies are listed 'Best First'.
    Re: permutation algorithm
    by Abigail-II (Bishop) on Jul 12, 2002 at 13:39 UTC
      That's a memory hungry program! For 10 elements, you will create 1024 arrays, 20 elements give you 1048576 arrays, and 30 elements give you 1073741824 arrays.

      The problem as given is in NP (and probably not in P), but that means it's in P-SPACE. Your solution however uses exponential memory.

      Abigail

        Mmmm, I was trying to solve the problem without a recursion.

        You are right. I am building the tree, instead of traversing it. We'd better use a recursion for this.