Permutazioni per il tempo in JSON

Question

Permutazioni per il tempo in JSON

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

-1

Diciamo che ho un file JSON come nell'esempio sotto.

Come farei a trovare tutti i possibili valori della combinazione di articoli somme di tempo esistenti tra diciamo 00:03:04 a 00:25:55 senza trovare ogni singola combinazione di permutazione che esiste e li aggiunge per quel set?

Ad esempio, l'elemento 1 e l'elemento 3 si troveranno in quel vincolo temporale in cui i loro tempi si sommano a 00:20:32 .

Ho provato a utilizzare le permutazioni, ma si incontrano determinati inconvenienti con più oggetti. Se salgo fino a 7 oggetti, mi occorrono chiaramente oltre 13.000 iterazioni di aggiunta di valori temporali e controllo dei limiti di intervallo.

Che cosa posso fare per semplificare l'algoritmo?

 {
"item1":{"time":"00:18:21"},
"item2":{"time":"00:22:22"},
"item3":{"time":"00:02:11"},
"item4":{"time":"01:34:32"}
}

loops javascript algorithms json combinatorics

posta user2676326 23.03.2017 - 04:38

fonte

2 risposte

0

Il problema non ha nulla a che fare con JSON, a meno che l'estrazione di alcuni numeri da JSON in un array sia un problema per te.

Non hai bisogno delle permutazioni dei tempi, hai bisogno di un sottoinsieme. Nel tuo esempio di 7 valori temporali, ci sono 128 sottoinsiemi possibili di questi valori. Quindi il problema può essere facilmente risolto in O (2 ^ n) dove n è il numero di valori; più veloce se il tempo target è così piccolo che è sufficiente considerare i sottoinsiemi con pochi elementi.

Un'alternativa è un algoritmo che impiega circa O (k), dove k è il tempo target, che sarà migliore se k è piccolo rispetto a 2 ^ n: Crea una bitmap di tutti i totali che possono essere creati usando qualsiasi sottoinsieme dei primi 1, 2, 3, ... elementi.

risposta data 23.03.2017 - 22:44

fonte

Leggi altre domande sui tag loops javascript algorithms json combinatorics

La factory ha bisogno di una lista di oggetti disponibili. Dovrebbe essere statico o no? Perché non un motore di rendering standard per risolvere i problemi del browser incrociato [chiuso]

score 0 · Accepted Answer

Principalmente dove stai andando storto sta trovando permutazioni quando hai solo bisogno di cercare combinazioni . Per il tuo esempio, se vengono trovati l'articolo 1 e l'articolo 3, non è necessario verificare in un secondo momento per l'articolo 3 e l'articolo 1, ma il tuo numero di 13.000 indica che lo sei. Se elimini quei controlli duplicati, ci sono solo 120 combinazioni per controllare 7 oggetti.

Puoi anche cercare opportunità per la potatura. Se item 1 + item 2 è maggiore dell'intervallo massimo, non è necessario controllare item 1 + item 2 + item 3 , item 1 + item 2 + item 4 e così via. Se organizzi i tuoi assegni in profondità, sarà più semplice effettuare questa potatura.