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";