Effiziente Möglichkeit, Partitionen mit Wertpaar einer Liste zu erzeugen> 15 Elemente

Question

Ich erstelle eine Liste von Partitionen aus einer Liste von Elementen (ähnlich wie Partitionen einer Gruppe oder setze Partitionen). Das Problem ist, dass für jede dieser Partitionen eine Zufallszahl zugewiesen werden muss, die ihren Wert angibt, damit ich später Berechnungen an den Ausgabedaten durchführen kann, die aus einem partition = value-Paar bestehen.

würde Eine Probe wie unten ein csv mit Beispieleinträge sein:

p,v 
"[[1, 2, 3, 4]]",0.3999960625186746 
"[[1], [2, 3, 4]]",0.49159520559753156 
"[[1, 2], [3, 4]]",0.12658202037597555 
"[[1, 3, 4], [2]]",0.11670775560336522 
"[[1], [2], [3, 4]]",0.006059031164368345 

Hier ist der Code, den ich dafür zusammengestellt haben:

ist, ich bin vor

from collections import defaultdict 
import random 
import csv 

partitions = [] 

elements = input('Please specify number of elements: ') 
size = int(elements) 
fileheader = str(size) 

# simple menu 
if size == 1: 
    partitionlist = range(1,size+1) 
    print ('A one element list have 1 partition') 
elif size < 28: 
    partitionlist = range(1,size+1) 
elif size >= 28: 
    partitionlist = [0] 
    print ("Invalid number. Try again...") 

# generate all partitions 
def partition(elements): 
    if len(elements) == 1: 
     yield [ elements ] 
     return 

    first = elements[0] 
    for smaller in partition(elements[1:]): 
     # insert `first` in each of the subpartition's subsets 
     for n, subset in enumerate(smaller): 
      yield smaller[:n] + [[ first ] + subset] + smaller[n+1:] 
     # put `first` in its own subset 
     yield [ [ first ] ] + smaller 

for p in partition(partitionlist): 
    partitions.append([sorted(p)] + [random.uniform(0,1)]) 

# write the generated input to CSV file 
data = partitions 

def partition_value_data(size): 
    with open(size+'-elem-normaldist.csv','w') as out: 
     csv_out=csv.writer(out) 
     csv_out.writerow(['p','v']) 
     for row in data: 
      csv_out.writerow(row) 

partition_value_data(fileheader) 

Das Problem, dass, wenn die Anzahl der Elemente geht über 13, bekomme ich einen Speicherfehler. Liegt es an meinem Computerspeicher oder an einem Limit innerhalb von Python? Ich benutze Python 2.7.12.

für eine Liste mit 15 Elementen ist die Anzahl der Partitionen ca. 1382958545

Ich versuche, eine Partitionen einer Liste von bis zu 30 Elementen zu generieren, wo die Anzahl der Partitionen ca. wäre. 545717047947902329359

Jeder Rat wird wirklich geschätzt. Danke.

Answer 1

Ihr Problem hier ist, dass Sie einen Generator mit der Umwandlung in eine Liste kombinieren, die total negiert jeden Vorteil von der Erstellung eines Generators.

Stattdessen sollten Sie nur direkt von Ihrem Generator schreiben.

from collections import defaultdict 
import random 
import csv 

elements = input('Please specify number of elements: ') 
size = int(elements) 
fileheader = str(size) 

# simple menu 
if size == 1: 
    partitionlist = range(1,size+1) 
    print ('A one element list have 1 partition') 
elif size < 28: 
    partitionlist = range(1,size+1) 
elif size >= 28: 
    partitionlist = [0] 
    print ("Invalid number. Try again...") 

# generate all partitions 
def partition(elements): 
    if len(elements) == 1: 
     yield [ elements ] 
     return 

    first = elements[0] 
    for smaller in partition(elements[1:]): 
     # insert `first` in each of the subpartition's subsets 
     for n, subset in enumerate(smaller): 
      yield smaller[:n] + [[ first ] + subset] + smaller[n+1:] 
     # put `first` in its own subset 
     yield [ [ first ] ] + smaller 


def partition_value_data(size): 
    with open(size+'-elem-normaldist.csv','w') as out: 
     csv_out=csv.writer(out) 
     csv_out.writerow(['p','v']) 

     for row in partition(partitionlist): 
      csv_out.writerow([sorted(row)] + [random.uniform(0,1)]) 

partition_value_data(fileheader)