Losowe kombinacje - optymalny hashswap.pl

Tym razem podam algorytm optymalny, klasyczny (nie mój! - mój jest tylko kod). Jest w zasadzie maksymalnie szybki, i minimalnie obciąża pamięć (modulo trywialności). Oto kod:

#!/usr/bin/perl
#
# hashswap.pl

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);    $m=$n+1;
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

for (1..$k)
{   $v = $_ + int(rand($m-$_));
    if(!($w=$h{$v}))  { $w = $v }
    if(!($s=$h{$_}))  { $s = $_ }
    $h{$_}=$w;    $h{$v}=$s        ### swap
}
no integer;
$endT = times();
use integer;

for (1..$k)  { print "  $h{$_}" }

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";

# Koniec programu

---

Algorytm zawiera się głównie w pierwszej pętli, której tekst składa się w sumie z 6 linijek. Gdy chce ktoś mierzyć czas dla wielkich parametrów, to linijki pomiędzy instrukcją:

        $endT = times();

oraz instrukcją print, może usunąć (lub zakomentować).

---

A teraz podam ten sam program, tyle że swap będzie dokonany w stylu wczesnego minikomputera PDP:

#!/usr/bin/perl
#
# pdpswap.pl

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);    $m=$n+1;
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

for (1..$k)
{   $v = $_ + int(rand($m-$_));
    if(!$h{$_})  { $h{$_} = $_ }
    if($v != $_)
    {   if(!$h{$v})  { $h{$v} = $v }
        $h{$v} ^= $h{$_} ^= $h{$v} ^= $h{$_}    ### swap
}   }

no integer;
$endT = times();
use integer;

for (1..$k)  { print "  $h{$_}" }

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";

# Koniec programu

Losowe kombinacje (w perlu)

@Przemysławie: moja kobyłka u płotu. Sam zastawiłem na siebie tę pułapkę napisania nieoptymalnego algorytmu. Stosuję w nim linked list dla reprezentacji wybranej losowo kombinacji. Podaję ją uporządkowaną. Wierzę, że w perlu ten algorytm nie zżera pamięci; gorzej byłoby w innych językach.

Algorytm (a), o którym wspomniał @Dziki Wezyr, jest lepszy, chyba optymalny. Oba losują kolejne elementy kombinacji bez zwracania.

Podaję poniżej program w perlu. Nie ma żadnych dodatków, jest w tym sensie minimalny. Można go wpakować w pętlę, dodać mu liczniki i pomiary czasu, itd.

---

#!/usr/bin/perl
#
# A non-optimal program.

use integer;

print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$nxt[0] = $n+1;

for (0..$k-1)
{   $a = int(rand($n-$_));
    $b=0;
    while ($a >= $b)
    {   $b = $nxt[$last = $b];
        ++$a;
    }
    $nxt[$last] = $a;
    $nxt[$a] = $b
}

while(($a=$nxt[$c]) != $n+1)
{   print "  $a";
    $c=$a
}

print "\n\n"

---

---

Dla wygody sportowców (:-) uzupełnię kod o pomiar czasu liczenia kombinacji (bez brania pod uwagę czasu inputu użytkownika oraz drukowania wyniku). Oto program z zegarkiem:

---

#!/usr/bin/perl
#
# A non-optimal program.


print "\n\nThis program selects a random combination\n";
print "\tof k elements out of 1..n.\n\n";
print "Enter max ==> ";
chomp($n=<>);
print "Enter the combination size ==> ";
chomp($k=<>);
print "\n\n";

$start = times();
use integer;

$nxt[0] = $n+1;

for (0..$k-1)
{   $a = int(rand($n-$_));
    $b=0;
    while ($a >= $b)
    {   $b = $nxt[$last = $b];
        ++$a;
    }
    $nxt[$last] = $a;
    $nxt[$a] = $b
}

no integer;
$endT = times();
use integer;

while(($a=$nxt[$c]) != $n+1)
{   print "  $a";
    $c=$a
}

no integer;

print "\n\n\tcomputation time:  ", $endT-$start, "\n\n";