Ordinamento casuale di una lista in cui alcuni stati sono illegali?

Question

Ordinamento casuale di una lista in cui alcuni stati sono illegali?

#1 da (1 voti)
#2 da (0 voti)

1

Voglio creare un randomizzatore per gli elementi nel gioco La-Mulana. Tuttavia, alcune disposizioni sugli oggetti significherebbe che il gioco non può essere completato. A volte c'è solo un gruppo di elementi necessari per superare un ostacolo, altre volte, ci sono più gruppi di oggetti che possono superare un ostacolo.

Per esempio, per raggiungere la Camera di Nascita, devi avere la Piuma, l'Artiglio del Rampino, gli Stivali di Hermes e il Modello dell'Aereo, o avere il Ciondolo dell'Isis e gli Stivali di Hermes, o uccidere il quinto capo e avere il Piano Modello. Ciò significa che tutto ciò che mette gli Stivali di Hermes e il Plane Model nella Camera della Nascita rende il gioco impossibile da completare.

Effettivamente, sto cercando di mettere una lista in ordine casuale dove alcuni articoli non possono mai essere all'interno di un intervallo di indici e alcune voci possono essere solo all'interno di un intervallo di indici se altri si trovano entro un secondo intervallo di indici. C'è un modo migliore per farlo rispetto a rifiutare e rigenerare configurazioni illegali?

random algorithms

posta Smurfton 03.03.2017 - 18:04

fonte

2 risposte

Leggi altre domande sui tag random algorithms

Quali sono i concetti chiave negli algoritmi CPM / Gantt Chart? Come devo caricare e modificare le impostazioni?

score 1 · Answer 1

A volte il modo migliore per generare una configurazione valida è creare configurazioni valide e incrementare in modo incrementale quelle più grandi.

Non ho familiarità con La-Mulana. La prima volta che ne ho sentito parlare è stata circa sessanta secondi fa mentre leggevo la tua domanda. Prenderò in considerazione che le posizioni siano visitate linearmente, ma possiamo forse generalizzare l'algoritmo sottostante.

Supponendo che le posizioni siano ordinate A, B, C e così via, e per ogni posizione X sappiamo che richiede elementi X1, X2 ecc ...:

Metti tutti gli elementi nella posizione A (metaforicamente parlando)
Per la prossima posizione, trova gli elementi nelle posizioni precedenti in cui potrebbe essere spostati (ad esempio gli elementi che non sono necessari prima della posizione corrente). Distribuire casualmente tali elementi tra questa posizione e le posizioni precedenti. (Casuale potrebbe significare 'uniformare i livelli', 'in modo totalmente casuale' ecc ...)
Ripeti (2) finché non ti trovi nell'ultima posizione

A seconda dei particolari di La-Mulana, l'algoritmo di cui sopra dovrà essere ottimizzato.

score 0 · Answer 2

Un approccio che potrebbe funzionare qui è creare una mappatura da interi a configurazioni legali. Cioè, 0 sarebbe la prima configurazione legale, 1 sarebbe la seconda configurazione legale. Quindi si tratta semplicemente di generare un numero casuale in un intervallo e di estenderlo a una configurazione legale.

La funzione che esegue il mapping da un numero a una configurazione è ovviamente il trucco. Non ho familiarità con le regole del gioco in questione, quindi non mi è chiaro che questa è una soluzione possibile qui o se ne vale la pena. Molto dipende da quanto sia probabile generare una configurazione illegale usando il metodo della forza bruta. Se fornisci un po 'più di dettagli sulla forma del problema, dovrebbero essere seguiti consigli più concreti.