La ricerca delle possibili combinazioni di x cambia da y vero

Question

La ricerca delle possibili combinazioni di x cambia da y vero

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

1

Sto lavorando su un algoritmo per trovare possibili riempimenti di spazi vuoti nel testo. La mia funzione riceverà come input: (Esempio)

[false,"o",false,"b",false,"r"]

che rappresenta la stringa "foobar" con alcuni valori tagliati. La mia funzione dovrebbe trovare opportunità per i possibili modi per colmare gli spazi vuoti dati un massimo di caratteri (e un minimo di uno spazio vuoto). quindi, dato un massimo di 2 dovrebbe tornare:

[
[true,"o",false,"b",false,"r"],
[false,"o",true,"b",false,"r"],
[false,"o",false,"b",true,"r"],
[true,"o",true,"b",false,"r"],
[true,"o",false,"b",true,"r"],
[false,"o",true,"b",true,"r"]
]

Qualcuno può darmi una spinta nella giusta direzione?

Oh, e ho pianificato di eseguire i risultati attraverso un'altra funzione per sistemarli, ma se NON POSSO ottenere risultati dove c'è un falso tra gli spazi vuoti (cioè, da sopra, [true,"o",false,"b",true,"r"] ) sarebbe un enorme bonus.

Questo è in un ambiente javascript / jQuery

javascript jquery

posta Chris O'Kelly 10.03.2013 - 06:30

fonte

2 risposte

Leggi altre domande sui tag javascript jquery

Includo i collegamenti di associazione per gli oggetti che hanno solo l'ambito del metodo nei diagrammi delle classi UML Strutture dati del database per RESTful api

score 1 · Answer 1

Ho trovato la mia risposta, era particolarmente curioso per la mia soluzione, non ho un esempio di codice di una soluzione più generale (come quello che MichaelT ha collegato nei commenti) ma in pseudocodice era essenzialmente:

/*
Find the free(false) cells in the array and create an array of their indices
check the array is not empty 
if it is return false (if there's no free space you cannot fill anything)
(now check the combinations...)
for n=1..the maximum number of fills (for each possible number of fills)
    for each of the free cells (for each possible first fill)
        check the number of free cells after this one
        if it is less than n-1 break (no room for this many fills)
        for 1..n-1 (for each fill left after the first)
            fill this spot
        add the result to the list of results
*/

come ho detto, abbastanza specificata per la mia soluzione di sostituzione solo in linea, penso che alcuni seri nidificati sarebbero obbligati a farlo al contrario.

Qualunque cosa, segnerò la mia corretta perché è come ho risolto il mio, ma probabilmente non è rilevante per molte persone ...

score 0 · Answer 2

C'è un modo più semplice, dato il tuo limite di non-spazio.

Ci sono due posizioni rilevanti, first_true e last_true . Questi non possono essere più distanti rispetto a max_chars-1 . Le tue 6 soluzioni possono quindi essere riassunte come {0,0}, {1,1}, {2,2}, {0,1}, {0,2} e {1,2}.

Generali come

FOR ( BEGIN = 0 TO LENGTH)
  FOR (END = 0 TO MINIMUM(MAXCHARS, LENGTH-BEGIN) )
    PRINT BEGIN, END