🚀 go-pugleaf

W dniu 2010-12-09 08:29, Stachu 'Dozzie' K. pisze:
> On 2010-12-09, Maciej Misiak<grizzley@poczta.onet.pl>  wrote:
>> Nie będę pokazywał palcem kto mnie zaraził project Eulerem
>> (www.projecteuler.net), ale wdrożyłem się z racji takiej, że wymagana
>> jest tylko odpowiedź, a nie sposób rozwiązania. Zważywszy na to,
>> postanowiłem trochę się zaznajomić z różnorodnymi pakietami, które
>> dopomogłyby w rozwiązaniu zadań bez wynajdywania koła na nowo.
>> Piękne jest chociażby to, że można do woli używać 'use bigint' i nikt
>> złego słowa nie powie :)
>> Anyway, jest kilka zadań z kombinatoryki, np.
>> http://projecteuler.net/index.php?section=problems&id=307
>>
>> Pytanie brzmi czy ktoś natknął się na moduł CPANa, który potrafiłby
>> poiterować po wszystkich możliwych "kombinacjach"?
>>
>> Jedyne, co znam i znalazłem, to Algorithm::Permute, ale tam tylko umiem
>> podać listę elementów i permutowana jest ta lista i tyle. A tu trzeba
>> wrzucić w n kubków m kulek na wszystkie sposoby.
>
> A szukałeś pod hasłem "combinatorics"? Choćby to wygląda ciekawie:
> http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.25/

Ooo, fajne! Popróbujemy...

>> Albo: http://projecteuler.net/index.php?section=problems&id=105
>> czyli z listy liczb (zbiór Q) wybieramy część do zbioru A, pozostała to
>> zbiór B.
>> Sumujemy zbiór A i zbiór B i coś tam robimy z tymi sumami, czyli
>> potrzebna jest iteracja po wszystkich możliwych podzbiorach A zbioru Q.
>
> Tych będzie 2^|Q|, wystarczy coś do dodawania jedynki na bitach. Ino
> tego będzie w pytę dużo dla zbioru Q więcej niż 20-elementowego
> i wykonanie będzie zabierać lata.

Właściwie 3^|Q|, bo mogą być jeszcze elementy nienależące do A i 
nienależące do B. Więc ja to robiłem generując wszystkie liczby w 
systemie trójkowym.
Oczywiście, że zestarzałbym się za bardzo zanim bym zobaczył choćby 
ułamek rozwiązania :) Mi chodzi o sprawdzanie na mniejszej ilości danych 
jak dany problem się zachowuje.

#!perl -l

use Algorithm::Combinatorics qw/partitions/;

@data = (1,2,3,4);

my $iter = partitions(\@data, 2);
while(my $p = $iter->next)
	{ print join ", ", map { "[@$_]" } @$p }

my $iter = partitions(\@data, 3);
while(my $p = $iter->next)
{
	print join ", ", map { "[@$_]" } @$p[0,1];
	print join ", ", map { "[@$_]" } @$p[0,2];
	print join ", ", map { "[@$_]" } @$p[1,2]
}

wygląda obiecująco.

-- 
grizzley