package Permute;

#  Accept an array reference (arrayref), and return an arrayref of
#  arrayrefs of all of the possible permutations of the original
#  array. Recursive code.
#
#  T. Alex Beamish / August 11, 2016

sub possibilities {

    my ( $list ) = @_;

    my $len = scalar @{$list};

    #  This is the trivial case: if there's just a single element
    #  in the array, then there's only a single permutation.

    if ( $len == 1 ) { return [ [ $list->[0] ] ]; }

    my @output;

    #  OK -- there are at least two elements in the array. Here's
    #  the approach: each of the elements is going to get a chance
    #  to be the first element. We're calling that element the
    #  pivot in the comments below.

    for my $p ( 0 .. $len-1 ) {

      my @work;

      #  We're building a work array consisting of everything after
      #  the pivot, followed by everything before the pivot.

      if ( $p < $len-1 ) { push @work, @{$list}[$p+1..$len-1]; }
      if ( $p > 0 ) {      push @work, @{$list}[0..$p-1]; }

      #  We call ourselves recursively to get all permutations of
      #  the work array, then add each of those possibilities to
      #  the list, with our pivot as the first element.

      my $poss = possibilities ( \@work );
      foreach my $soln ( @{$poss} ) {

        push ( @output, [ $list->[$p], @{ $soln } ] );
      }
    }

    return \@output;
}

1;