🚀 go-pugleaf

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/

> 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.

-- 
Secunia non olet.
Stanislaw Klekot

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

On 2010-12-09, Maciej Misiak <grizzley@poczta.onet.pl> wrote:
>>> 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.

Oj, tam, fistaszki. Złożoność wykładnicza to złożoność wykładnicza,
podstawa już jest mniej istotna :)

Chyba zostałem zepsuty przez swój wydział, skoro tak patrzę na problemy ;p

-- 
Secunia non olet.
Stanislaw Klekot