array_permutation_hun.pl

#! /usr/bin/perl
use warnings;
use strict;

sub swap_arr($$$)
{
  my ($arr, $i, $k) = @_;
  if ($i != $k)
  {
    my $temp = $arr->[$i];
    $arr->[$i] = $arr->[$k];
    $arr->[$k] = $temp;
  }
}

my $counter = 0;
sub req_permut($$);
sub req_permut($$)
{
  my ($arr, $i) = @_;
  my $n = $#{$arr} + 1;
  if ($i >= $n)
  {
    print '  ' . join(', ', @{$arr}) . "\n";
    # print "  " . join('', @{$arr}) . "\n";
    $counter ++;
  }
  else
  {
    for (my $k = $i; $k < $n; $k++)
    {
      swap_arr($arr, $i, $k);
      req_permut($arr, $i + 1);
      swap_arr($arr, $i, $k);
    }
  }
}


my @arr = qw( a b c d );
req_permut(\@arr, 0);
warn '' . ($#arr + 1) . "! = $counter\n";



=pod
  PERMUTACIO

-----------
  Rekurzív módszer (Robert Sedgewick)
  Kiindulunk a 0, 1, 2, ..., N - 1 permutációból, és minden lehetséges elemet becserélünk az első helyre, majd a mögötte lévő szakaszt rekurzív "permutáljuk".

  A rekurzív eljárás egy i indexű elemtől kezdődően, a tömb végéig tartó szakaszt rendezgeti. Az elsö indexre kell elindítani az eljárást.

  RekurzívPermutáció(i)
      Ha i nagyobb a maximális indexnél akkor az aktuális permutáció feldolgozása
      különben
          Ciklus k := i-től az utolsó indexig
              swap_arr(i, k)
              RekurzívPermutáció(i + 1)
              swap_arr(i, k)
          Ciklus vége
  Eljárás vége

=cut

=pod
  Iteratív módszer - lexikografikus sorrend (Donald Knuth)
  - Elvégezzük teendőnket az aktuális permutációval. (Például kiírjuk.)
  - Ha a sorozat csökkenően rendezett, akkor vége a permutációk felsorolásának.
  - Különben
      * Jobbról megkeressük az első elemet, ami kisebb a nála jobbra állónál. (Ezen a pozíción fogunk növelni.)
        Indexe: j
      * Jobbról megkeressük az első elemet, ami nagyobb, mint az előbb kiválasztott a[ j ] elem
        Indexe: m
      * Felcseréljük az a[ j ] és a[ m ] elemeket.
        Most a (j+1)-től a sorozat végéig tartó szakasz fordítottan rendezett
      * Megfordítjuk a (j+1)-től a sorozat végéig tartó szakaszt.
  - Ezután az első ponttól folytatódik az eljárás

=cut