Einzigartige Permutationen von Ganzzahl-Partitionen mit fester Länge, wobei jedes Element ein Maximum hat

Question

Diese Frage ähnelt einer Frage, die ich vor einigen Monaten hatte: Generating a numpy array with all combinations of numbers that sum to less than a given number. In dieser Frage wollte ich alle Zahlen, die höchstens zu einer Konstante summierten, generieren, da jedes Element ein bestimmtes Maximum hatte.

Dieses Mal möchte ich alle Permutationen berechnen, die genau zu dieser Konstante summieren. Dies kann als Berechnung der einzigartigen Permutationen von Ganzzahlpartitionen angesehen werden, bei denen jedes Element ein bestimmtes Maximum aufweist. Das Endergebnis sollte in einem Nummernfeld gespeichert werden.

einen Generator, ein Motto erreicht, was wir wollen:

import numpy as np 
from itertools import product 
K = 3 
maxRange = np.array([1,3,2]) 

states = np.array([i for i in product(*(range(i+1) for i in maxRange)) if sum(i)==K]) 

array([[0, 1, 2], 
     [0, 2, 1], 
     [0, 3, 0], 
     [1, 0, 2], 
     [1, 1, 1], 
     [1, 2, 0]]) 

geben Ich habe recht geringe Leistung, wenn K=20 und maxRange = [20]*6. Die Anzahl der Permutationen ist mit 53130 begrenzt, dauert aber schon 20 Sekunden. Mein Bauchgefühl sagt mir, das sollte viel weniger als eine Sekunde dauern.

Hat jemand eine schnellere Lösung zur Verfügung? Ich habe Probleme, die Lösung zu meiner früheren Frage zu ändern, um dies zu berücksichtigen, weil ich nicht weiß, wie man die Permutationen abschneidet, für die es nicht mehr möglich ist, genau zu K hinzuzufügen.

Ich habe nichts gegen Lösungen, die den @jit Operator von Numba verwenden ... solange sie schneller sind als das, was ich jetzt habe!

Vielen Dank im Voraus.

Answer 1

Ich hatte darüber ziemlich lange denken, aber ich habe es geschafft, um die Lösung zu Generating a numpy array with all combinations of numbers that sum to less than a given number für dieses Problem zu ändern:

Für die Anzahl der Partitionen, die Idee ist das Array feasible_range, der angibt, berechnen wie viel wir mindestens insgesamt in einem bestimmten Stadium brauchen, um noch max_sum zu erreichen. Zum Beispiel, wenn wir insgesamt 3 und max_range[0] == 1 erreichen wollen, müssen wir mindestens 2 haben, bevor wir mit dem letzten Element beginnen. Dieses Array ergibt sich aus einer kumulativen Summe:

feasible_range = np.maximum(max_sum - np.append(np.array([0]),np.cumsum(max_range)[:-1]),0) 

Jetzt können wir die Anzahl der Partitionen wie zuvor berechnet werden, indem die Elemente Einstellung, die nie auf eine machbare Partition 0.

def number_of_partitions(max_range, max_sum): 
    M = max_sum + 1 
    N = len(max_range) 
    arr = np.zeros(shape=(M,N), dtype = int)  
    feasible_range = max_sum - np.append(np.array([0]),np.cumsum(max_range)[:-1]) 
    feasible_range = np.maximum(feasible_range,0)  

    arr[:,-1] = np.where(np.arange(M) <= min(max_range[-1], max_sum), 1, 0) 
    arr[:feasible_range[-1],-1] = 0 
    for i in range(N-2,-1,-1): 
     for j in range(max_range[i]+1): 
      arr[j:,i] += arr[:M-j,i+1] 
     arr[:feasible_range[i],i]=0 #Set options that will never add up to max_sum at 0. 
    return arr.sum(axis = 0),feasible_range 

Die Trennwand führen kann Funktion hat auch eine ähnliche Interpretation wie zuvor.

def partition(max_range, max_sum, out = None, n_part = None,feasible_range=None): 
    #Gives all possible partitions of the sets 0,...,max_range[i] that sum up to max_sum. 
    if out is None: 
     max_range = np.asarray(max_range, dtype = int).ravel() 
     n_part,feasible_range = number_of_partitions(max_range, max_sum) 
     out = np.zeros(shape = (n_part[0], max_range.size), dtype = int) 

    if(max_range.size == 1): 
     out[:] = np.arange(feasible_range[0],min(max_range[0],max_sum) + 1, dtype = int).reshape(-1,1) 
     return out 

    #Copy is needed since otherwise we overwrite some values of P. 
    P = partition(max_range[1:], max_sum, out=out[:n_part[1],1:], n_part = n_part[1:],feasible_range=feasible_range[1:]).copy()  


    S = max_sum - P.sum(axis = 1) #The remaining space in the partition 
    offset, sz = 0, 0 
    for i in range(max_range[0]+1): 
     #select indices for which there is remaining space 
     #do this only if adding i brings us within the feasible_range. 
     ind, = np.where(np.logical_and(S-i>=0,S-i <= max_sum-feasible_range[0])) 
     offset, sz = offset + sz, ind.size 
     out[offset:offset+sz, 0] = i 
     out[offset:offset+sz, 1:] = P[ind] 
    return out 

Für K=20maxRange = [20]*6 und nimmt partition(maxRange,K) 13ms im Vergleich zu 18,5 Sekunden zuerst.

Ich mag nicht wirklich den Teil, wo ich kopieren muss; das kann wahrscheinlich vermieden werden, indem die Reihenfolge umgekehrt wird. Die Geschwindigkeit ist jetzt gut genug.