Finden Sie Zahlen, die eine Liste von Zahlen multiplizieren

Question

Ich habe ein Abstimmungssystem für etwas, wo Leute Dinge von eins bis zehn bewerten. Ich bin in der Lage, die Anzahl der Gesamtstimmen zu erhalten, aber nicht ihre Verteilung. Ich kann jedoch auf die Summen für jede Punktzahl zugreifen (aber nicht für welche Punktzahl sie sind).

Zum Beispiel, sagen zwei Leute stimmten 2 und drei 4 dann würde ich [4, 12] bekommen. Menschlich ist es möglich, herauszufinden, was die Stimmen waren, aber da es viele Daten gibt, brauche ich einen Algorithmus, der es programmatisch machen kann. Um dies menschlich zu lösen, würde ich wissen, dass es 5 Stimmen gab und das würde ich wissen, dass es entweder eins vier oder vier oder zwei zwei und drei Vieren waren. Da dies nicht das beste Beispiel ist, können wir nicht sagen, welches es wäre und deshalb sollte der Algorithmus alle diese Lösungen ausspucken. Mit den realen Daten ist es sehr selten, dass so etwas auftritt.

Die Eingabe hat die Form eines int, das die Gesamtzahl der abgegebenen Stimmen darstellt, und eine Liste aller Zwischensummen der Abstimmung. Die Ausgabe sollte ein Array sein, das pars (x, y) enthält, wobei x Anzahl der abgegebenen y-Stimmen ist. Wenn mehr als eine Lösung vorhanden ist, sollte der Algorithmus alle in einem Array zurückgeben.

EDIT: Hier einige echte Daten (17 Personen stimmten):

Dunkel  - 60 + 18 + 8 + 18 + 10 + 4 + 3 + 1  = 122 
Satomi  - 20 + 14 + 24 + 12 + 3 + 4 + 3   = 80 
Bottersnike - 16 + 28 + 5 + 8 + 6 + 4 + 4   = 71 
Woon  - 40 + 36 + 8 + 21 + 5 + 16    = 126 
Limelier - 10 + 18 + 6 + 15 + 8 + 4 + 6   = 67 
RandomGamer - 16 + 6 + 10 + 4 + 6 + 4 + 7   = 53 
Pillar  - 10 + 8 + 21 + 6 + 15 + 4 + 9 + 4 + 2 = 79 
EdgedPixel - 8 + 28 + 12 + 4 + 18 + 2 + 2   = 74 
Lock  - 20 + 24 + 7 + 18 + 10 + 8 + 6 + 2  = 95 
Huri  - 10 + 8 + 7 + 6 + 15 + 20 + 3 + 2 + 3 = 74 
Sean  - 18 + 32 + 8 + 5 + 4 + 9 + 2   = 78 

Und die Antworten (sorry über die verschiedenen Reihenfolge):

Woon  - 4*10 + 4*9 + 1*8 + 3*7 + 0*6 + 1*5 + 4*4 + 0*3 + 0*2 + 0*1 = 126 
Dunkel  - 6*10 + 2*9 + 1*8 + 0*7 + 3*6 + 2*5 + 1*4 + 1*3 + 0*2 + 1*1 = 122 
Lock  - 2*10 + 0*9 + 3*8 + 1*7 + 3*6 + 2*5 + 2*4 + 2*3 + 0*2 + 2*1 = 95 
Satomi  - 2*10 + 0*9 + 3*8 + 4*7 + 2*6 + 0*5 + 0*4 + 1*3 + 2*2 + 3*1 = 80 
Pillar  - 1*10 + 0*9 + 1*8 + 3*7 + 1*6 + 3*5 + 1*4 + 3*3 + 2*2 + 2*1 = 79 
Sean  - 0*10 + 0*9 + 4*8 + 0*7 + 3*6 + 1*5 + 2*4 + 3*3 + 2*2 + 2*1 = 78 
EdgedPixel - 0*10 + 0*9 + 1*8 + 4*7 + 2*6 + 0*5 + 1*4 + 6*3 + 1*2 + 2*1 = 74 
Huri  - 1*10 + 0*9 + 1*8 + 1*7 + 1*6 + 3*5 + 5*4 + 1*3 + 1*2 + 3*1 = 74 
Bottersnike - 0*10 + 0*9 + 2*8 + 4*7 + 0*6 + 1*5 + 2*4 + 2*3 + 2*2 + 4*1 = 71 
Limelier - 1*10 + 2*9 + 0*8 + 0*7 + 1*6 + 3*5 + 2*4 + 0*3 + 2*2 + 6*1 = 67 
RandomGamer - 0*10 + 0*9 + 2*8 + 0*7 + 1*6 + 2*5 + 1*4 + 2*3 + 2*2 + 7*1 = 53 

Answer 1

Ich habe jetzt mein Problem gelöst. Ich habe den Code von LitePresence als Basis verwendet und dann implementiert, was sie als vierten Schritt beschrieben haben.Für die Zukunft ist dies der Code, den ich verwendet habe:

from random import randint 
from random import shuffle 
import itertools 

NUM_RATINGS = 10 
RATING = [10, 10, 10, 10, 10, 10, 9, 9, 8, 6, 6, 6, 5, 5, 4, 3, 1] 
VOTES = len(RATING) 


ratings = {} 
for i in range(1, (NUM_RATINGS + 1)): 
    ratings[i] = [] 
for i in RATING: 
    ratings[i].append(i) 


subtotals = [] 
for key, values in ratings.iteritems(): 
    subtotals.append(sum(values)) 
subtotals = [i for i in subtotals if i != 0] 
subtotals.sort() 

hidden_subtotals = {} 
for key, values in ratings.iteritems(): 
    hidden_subtotals[key] = sum(values) 

print '===================================' 
print 'Hidden Test Data:' 
print 'unknown actual votes: %s' % ratings 
print 'unknown actual subtotals: %s' % hidden_subtotals 
print '===================================' 
print 'Present Problem:' 
print 'known vote total: %s' % VOTES 
print 'known subtotals: %s' % subtotals 
print 'known total: %s' % sum(subtotals) 
print 'number of ratings used: %s of %s' % (len(subtotals), NUM_RATINGS) 
print '===================================' 

def factors(n):  
    f = list(set(reduce(list.__add__, ([i, n//i] for i in range(
     1, int(n**0.5) + 1) if n % i == 0)))) 
    f.sort() 
    return f 

# Factor Each 
subtotal_factors = {} 
for i in subtotals: 
    subtotal_factors[i]=(factors(i)) 
print 'process 1: %s' % subtotal_factors 

# Remove Factors greater than highest rating 
possible_ratings = {} 
for i in subtotal_factors: 
    possible_ratings[i] = [ 
     z for z in subtotal_factors[i] if z<=NUM_RATINGS] 
print 'process 2: %s' % possible_ratings 

# Remove Factors if not enough votes for that possibility; too small relative to subtotal 
for i in possible_ratings: 
    possible_ratings[i] = [ 
     z for z in possible_ratings[i] if i/z < VOTES] 
print 'process 3: %s' % possible_ratings 


end_res = {} 
other = {} # (count, [poss]) 
for i in possible_ratings.items(): 
    if len(i[1]) == 1: 
     end_res[i[0]] = (i[1][0], i[1][0]) 
    else: 
     other[i[0]] = (subtotals.count(i[0]), i[1]) 

combs = {} 
for i in other.items(): 
    combs[i[0]] = (i[1][0], []) # (count, [data]) 
    for a in i[1][1]: 
     for b in i[1][1]: 
      if (a, b) not in combs[i[0]]: 
       if a * b == i[0]: 
        combs[i[0]][1].append((a, b)) 

lists = [] 
for i in combs.items(): 
    for j in range(i[1][0]): 
     lists.append([]) 
     for n in i[1][1]: 
      lists[-1].append((n[0], n[1], i[0])) 

toprocess = itertools.product(*lists) 
working = [] 

for test in toprocess: 
    works = True 
    seen = [] 
    tot = 0 
    for i in test: 
     if i[1] in seen: 
      works = False 
      break 
     tot += i[0] 
     if tot > VOTES: 
      works = False 
      break 
     seen.append(i[1]) 
    if not works: 
     continue 
    else: 
     working.append(test) 

formattedWs = [] 
for w in working: 
    w = list(w) 
    notseen = [i + 1 for i in range(NUM_RATINGS)] 
    for i in w: 
     notseen.remove(i[1]) 
    for i in notseen: 
     w.append((0, i)) 

    t = "" 
    def f(x, y): 
     return y[1] - x[1] 

    w.sort(cmp=f) 

    for i in w: 
     t += "%d*%d + " % (i[0], i[1]) 
    t = t[:-3] 
    formattedWs.append(t) 

seen = [] 
for w in list(formattedWs): 
    if w in seen: 
     formattedWs.remove(w) 
    else: 
     seen.append(w) 

print "===================================" 
for n, w in enumerate(formattedWs): 
    print "Solution #%d: %s" % (n + 1, w) 

Answer 2

Ich brauche einen Algorithmus das ist programmierbar

Ich würde damit beginnen, Ihre Gesamtwerte zu berücksichtigen.

What is the most efficient way of finding all the factors of a number in Python?

def factors(n):  
    return set(reduce(list.__add__, 
       ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 

Dies wird alle Faktoren zurückkehren, sehr schnell, von einer Anzahl n.

das würde Sie auf Ihrem Weg bekommen; offensichtlich ein aufgelistet Summe, die nicht mehr als 5 hat für einen Faktor kam nicht aus einer Gruppe, die 5 der

Schritt 1) ​​Faktor jede Nummer in der Liste der Summen

Schritt 2 bewertet) erstellen Wörterbuch mit allen möglichen Bewertungen wie die Schlüssel; dh Tasten 1-10; jeweils mit leeren Listen als Werte.

Schritt 3) überprüfen Sie, ob jede Liste von Faktoren einen Faktor hat, der jedem Bewertungsschlüssel entspricht; wenn so die Gesamt hängen Sie ihn für diesen entsprechenden Schlüssel

from random import randint 
from random import shuffle 

VOTES = 200 
RATINGS = 10 

# Generate Test Data 
ratings = {} 
for i in range(1,(RATINGS+1)): 
    ratings[i] = [] 
for i in range(VOTES): 
    rate = randint(1,RATINGS) 
    ratings[rate].append(rate) 

subtotals = [] 
for key, values in ratings.iteritems(): 
    subtotals.append(sum(values)) 
subtotals = [i for i in subtotals if i != 0] 
subtotals.sort() 

hidden_subtotals = {} 
for key, values in ratings.iteritems(): 
    hidden_subtotals[key] = sum(values) 

print '===================================' 
print 'Generate Hidden Test Data' 
print 'unknown actual votes: %s' % ratings 
print 'unknown actual subtotals: %s' % hidden_subtotals 
print '===================================' 
print 'Present Problem' 
print 'known vote total: %s' % VOTES 
print 'known subtotals: %s' % subtotals 
print 'known total: %s' % sum(subtotals) 
print 'number of ratings used: %s of %s' % (len(subtotals), RATINGS) 
print '===================================' 

def factors(n):  
    f = list(set(reduce(list.__add__, ([i, n//i] for i in range(
     1, int(n**0.5) + 1) if n % i == 0)))) 
    f.sort() 
    return f 

# Factor Each 
subtotal_factors = {} 
for i in subtotals: 
    subtotal_factors[i]=(factors(i)) 
print 'process 1: %s' % subtotal_factors 

# Remove Factors greater than highest rating 
possible_ratings = {} 
for i in subtotal_factors: 
    possible_ratings[i] = [ 
     z for z in subtotal_factors[i] if z<=RATINGS] 
print 'process 2: %s' % possible_ratings 

# Remove Factors if not enough votes for that possibility; too small relative to subtotal 
for i in possible_ratings: 
    possible_ratings[i] = [ 
     z for z in possible_ratings[i] if i/z < VOTES] 
print 'process 3: %s' % possible_ratings 

Schritt 4) auf die Werte Liste der Möglichkeiten stellt dann werden Sie ein Problem haben, wo 2 ist in 4 die passen, 6 ist, 8er, 10er Jahre; 4er passen in 8er und 3er passen in 6er und 9er. Sie müssen etwas Logik anwenden, um die Ergebnisse zu bereinigen.