Come generare un sacco casuale di numeri interi positivi che riassumono in un numero di input?

Penso che un problema sia che è abbastanza facile che non ci siano soluzioni valide, se a è vicino a b

Non ci sono risultati validi se N < a , e c'è solo un risultato valido per N = a . Allo stesso modo, non ci sono risultati validi se N < 2 * a e N > b

Se hai richiesto b > 2 * a , il tuo metodo è garantito per trovare un risultato valido e può essere semplificato in questo modo:

def greedy(N, a, b):
    while N > 0:
        next = randint(a, b)
        N -= next
        if N < a:
            next += N
            N = 0
        yield next

Mi sto concentrando sulla vera domanda dell'OP, che è la velocità, in particolare il numero di volte in cui viene chiamata la funzione di randomizzazione e quanto è veloce (o lento). Non vedo alcun problema con la correttezza funzionale.

L'algoritmo originale genera solo un numero casuale per elemento, e non vedo alcun modo per generare meno di quello. Ma ho un paio di suggerimenti.

1. Assicurati di non eseguire nuovamente il seeding del generatore di numeri casuali ogni volta. Devi solo seminarlo una volta.

2. In che modo la tua funzione casuale genera valori all'interno dell'intervallo? Se lo fa iterativamente (cercando valore dopo valore fino a quando ne trova uno nell'intervallo), questo potrebbe essere il problema. Invece di tentativi ed errori, utilizzare la funzione di randomizzazione per generare un numero all'interno del proprio intervallo nativo, quindi ridimensionarlo nell'intero dominio di destinazione. Per esempio. se genera numeri compresi tra 0 e 2 ^ 16, dividi il risultato per 2 ^ 16 e moltiplicalo per (b-a), quindi aggiungi un, quindi arrotondalo al numero intero più vicino.

3. Se il problema è la scalabilità-- cioè hai bisogno di un numero molto grande di set di risultati per un singolo valore N-- quindi avvicina il problema all'indietro: genera (non a caso) tutti i possibili insiemi di numeri interi che soddisfano i criteri, memorizzarli in una serie di set, quindi utilizzare una funzione di randomizzazione per scegliere un indice nell'array. Ci sono vari modi per calcolare l'elenco completo, il più semplice dei quali è un insieme di m loop n-1 dove m = il numero massimo di elementi in un set (l'ultimo elemento è calcolato come differenza tra l'accumulatore e N). Degno di nota di questo approccio è che offrirà prestazioni completamente prevedibili. Tuttavia questa è una soluzione scadente se hai bisogno solo di un piccolo numero di set, o se ti aspetti che m sia molto grande.

Controlla la soluzione qui sotto, uso minimo di random per trovare la sequenza di numeri tra un & b che riassumerebbe fino a N;

1. sum = 0; previous = 0; previousIdx=0; begin = 0;  (0:index of a; s:index of b)
2. selectArray (array of numbers which sums to N)
3. loop i : begin through s
4.  if sum+number(i)<=N
5.    previous = number(i)
6.    previousIdx = i
7.    sum = sum + number(i)
8.    add number(i) in selectArray
9. if sum < N
10.   sum = sum - previous 
11.  remove last from selectArray
12.  begin = random number between 0 & s
13.  go to step 3 
14. if sum =  N
15.   return selectArray  

Avvolgi questo algoritmo in un ciclo esterno per continuare diverse volte a dare più combinazioni formando la somma su N, cambiando ogni volta l'indice begin .

Penso che questo sia casuale senza ricominciare

while (true)
{
    next = rand.Next(a, b);  // inclusive
    if(sum + next == c)
    {
        list.Add(next);
        return list;
    }
    if(sum + next + a == c)
    {
        list.Add(next);
        list.Add(a);
        return list;
    }
    if(sum + next + a > c)
    {
        list.Add(c - sum);
        return list;
    }
    list.Add(next);
}