[Python] itertools.product e segmentaton fault

[Alessandro Re]

2015-02-25 15:03 GMT+00:00 Carlos Catucci <carlos.catucci a gmail.com>:
> Salve gente
>
> stavolta non so dove sbattere la testa.
> Devo avere le combinazioni possibili di una seire di liste.
>
> Esempio
> L1 = [a,b,c,]
> L2 = [d,e]
> L3 = [f,g]
>
> Mi servono
>
> [a.d.f],[a.d.g],[a.e.f],[a.e.g],
> [b.d.f],[b.d.g],[b.e.f],[b.e.g.],
> [c.d.f],[c.d.g],[c.e.f],[c.e.g]
>
> solo che la lista che mi crea problemi e'
>
>
> [[3760], [3759, 3762, 3763, 3770], [3769, 3778], [7607, 3781, 3780, 3779,
> 3777, 3773, 3774, 14617], [7476, 3788, 7475, 3786, 7472, 16514, 3784, 7470,
> 3783, 3789, 7477, 7608], [3806, 3805, 3804, 3803, 3802, 7532, 7530, 7534,
> 3813], [17164, 7486, 7490, 7491, 7492, 3814, 7495, 3818], [3819, 4216],
> [4217, 4220], [4219, 4268], [4267, 6475, 4273], [4271, 4272, 18235], [18236,
> 18244], [18245, 18246, 20232], [20234, 20237], [20236, 34978], [8389]]
>
> Ho idea che un totale di 13 liste di cui la piu' lunga conta 12 elementi e
> un'altro paio 8 o 9 elemnti, sia piu' di quanto il povero itertools.product
> (che suppongo a questo punto usi la ricorsivita') possa reggere, infatti mi
> tira fuori un bellissimo segmentation fault.
>
> Mi choiedo, c'e' quna strada alternativa per fare la stessa cosa che fa
> product con una diversa libreria?
>
> Carlos

Il prodotto cartesiano di N liste di dimensioni N1, N2, N3.. è un
elemento di dimension N1*N2*N3*... Ha complessità esponenziale, quindi
occhio ai numeri :)

Nel tuo caso:

import functools
liste = [[3760], [3759, 3762, 3763, 3770], [3769, 3778], [7607, 3781,
3780, 3779, 3777, 3773, 3774, 14617], [7476, 3788, 7475, 3786, 7472,
16514, 3784, 7470, 3783, 3789, 7477, 7608], [3806, 3805, 3804, 3803,
3802, 7532, 7530, 7534, 3813], [17164, 7486, 7490, 7491, 7492, 3814,
7495, 3818], [3819, 4216], [4217, 4220], [4219, 4268], [4267, 6475,
4273], [4271, 4272, 18235], [18236, 18244], [18245, 18246, 20232],
[20234, 20237], [20236, 34978], [8389]]
functools.reduce(lambda a,b: a*len(b), liste, 1)

Esce 95'551'488

Se ci aggiungi un'altra lista da 10 elementi, diventano 950 milioni di
disposizioni.

Ora, io suppongo che il tuo problema non sia dovuto alla ricorsione,
ma proprio alla scala del problema... 95 milioni di oggetti non sono
necessariamente facili da gestire.

Non so com'é implementata itertools.product, ma secondo me non usa la
ricorsione. Ed è pure un generatore, quindi non si incanta neanche a
fare tutti i conti prima del necessario (quindi, anche fosse
ricorsiva, il problema è legato a quante next() usi).

Sei sicuro di stare usando il metodo giusto per risolvere il problema?
Non hai alternative a visitare tutte le combinazioni?
~Ale