Salve a tutti.
Ho un problema, che mi sono dato da solo e a cui sto pensando da un paio di giorni che non riesco a risolvere. Magari qualcuno sa darmi un hint e riesce a trovare l’intuizione per risolverlo.
Il problema è il seguente:
Si vogliono generare ‘m’ combinazioni di numeri casuali uniche, dove ogni combinazione è definita come un insieme di ‘n’ numeri. Ognuno di questi numeri ha un range in cui può variare. Per semplicità ogni range sarà [0, a], con a>0 e valore di ‘a’ diverso per ogni numero della combinazione.
Per esempio presi in input la lunghezza della combinazione e i diversi range:
5
1, 5, 2, 1, 4
Una combinazione valida sarà: 1, 4, 2, 0, 2
Una combinazione non valida sarà invece: 0, 3, 3, 1, 3 (perchè 3>2)
Fin qua tutto semplice, se volessi generare ‘m’ combinazioni uniche casuali composte da ‘n’ numeri dovrei scegliere 5 numeri casuali che soddisfino i range e sceglierle in modo che non ci siano doppioni.
Iniziamo però ad aggiungere delle restrizioni. Ora per ogni singolo numero di ogni range, specifico una percentuale rispetto alle ‘m’ combinazione che devo generare, che mi indica il numero di volte che quel numero può comparire in quella posizione nelle mie combinazioni.
Assumiamo per semplicità che la somma delle probabilità di un elemento siano sempre 100%.
La mia domanda è, riuscirò a generare ‘m’ combinazione con queste restrizioni? Spoiler: NO (almeno credo).
Se la risposta è no mi piacerebbe riuscire a capire come fermare la generazione delle combinazioni e quindi rendermi conto di essere entrato in un loop. In sostanza mi piacerebbe capire a priori quante combinazioni si riescono a generare con queste restrizioni, in modo da fermarmi nel momento giusto per poi riempire quello che rimane fino a ‘m’ con combinazioni uniche casuali.
L’algoritmo quindi prende in input:
- ‘n’: la lunghezza della combinazione
- ‘rng’: un vettore che contiene l’estremo superiore di ogni range
- ‘prob’: un vettore bidimensionale che contiene la probabilità di ogni singolo numero di ogni range
Esempio di input:
n: 5
m: 1000
rng: 2, 21, 7, 12, 9
prob:
30, 50, 20
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 10, 10
12, 12, 12, 12, 12, 12, 12, 16
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 16
11, 11, 11, 11, 11, 11, 11, 11, 12
Output: ‘m’ combinazioni che rispettano le restrizioni se esistono. Nel caso non ne esistessero ‘m’, voglio quelle che rispettano le restrizioni + altre casuali uniche.
Grazie mille, per i coraggiosi che mi aiuteranno. Se avete domande o dubbi chiedete pure.