Calcolo combinatorio :Raggruppamento Caratteri Sfide

https://stackoverflow.com/questions/1127249

13-09-2019
|

Domanda

Stavo lavorando su alcuni raggruppamento problemi al mio lavoro.Ci sono un paio di domande, si prega di portare con me.Io li trovo molto interessante.Se qualcuno qui è interessato anche in combinatoria, si prega di aiutarmi.

Ok, quindi abbiamo un sacco di personaggi , qui ho preso un i d s.

Quali sono i modi in cui possiamo raggruppare gli elementi ?Diciamo che ci sono 4 caratteri a i d s.Gruppi validi(conservando l'ordine) sarebbe:

a i d s
ho un ds
un id s
ia d s
ai ds
un ids
aiuto s
aids

Come si fa a enumerare tutti i gruppi?Potreste dirmi quante combinazioni ci sono per ogni n lettere?

2 .Casi Particolari

Che cosa succede se il caso ha fatto la differenza come Ai sd e ai sd sono due gruppi?
Quanto tempo ci vuole per enumerare tutti i casi?Quale sarebbe la differenza di tempo tra la ricerca di 4 lettere e 5, lettere a caso?
Se si prendono lo spazio vuoto come un personaggio.Dopo tutto, l'enumerazione, come molti personaggi che hai scritto?
Se si definisce una trasformazione da una parola a un'altra parola in termini di distanza.Dire "ai ds" e "i ds" ha 1 distanza, perché si dovrebbe spostato la lettera "i" di un passo.Hai potuto trovare le parole in n passi in entrambi i lati di ogni parola?

Edit:
"l'aids" è una sola parola.
"una id" gli "aiuti" sono due parole che sono a 1 distanza dal originale parola "aids".
"un id s" è una parola che è a due passi dalla parola originale "aids".
"a i d s" è una parola che è a tre passi dalla parola.

Questo problema sembra essere una miniera d'oro.

Bonus:Qual è la distanza minima tra due parole.Come "l'aids" è una distanza da "un'id", e anche a due passi.C'è un "punto medio" parola da cui è possibile raggiungere qualsiasi altra parola nell'enumerazione con distanza minima?Quanti sentieri ci sono da una parola a un'altra?

Soluzione

Il calcolo del numero di combinazioni è banale. In sostanza, si dispone di una tra ogni due lettere. Potrebbe essere "epsilon" (vuoto), o spazio. Quindi, per n lettere si dispone di n-1 tali caratteri separatori. Poiché ogni carattere può avere solo due valori, che è lo stesso di un numero binario di n-1 cifre. Così si può avere 2 alla potenza di n-1 combinazioni.

aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations

Ora, per i casi particolari. Se ciascun carattere può essere maiuscolo o minuscolo, che è 2 alla potenza di variazioni n per i caratteri (purché siano lettere). Ora, ogni combinazione trovi sopra 2 n variazioni basate sulla capitalizzazione, in modo che il risultato finale è (2 (n-1)) * (2 ** n), che è uguale a 2 ** (2 * n -1).

Per ogni lettera adizionale si sia doppia o quadrupla (a seconda della cosa capitalizzazione) il tempo necessario per enumerare loro, come si può facilmente comprensibile dalla formula.

Il numero totale di caratteri è un po 'più difficile, ma è sufficiente a notare che ogni "spazio" è la metà "epsilon" il tempo. Quindi abbiamo (2 ** (n-1)) * n (lettere) + ((2 ** (n-1)) * (n-1)) / 2 (spazi). Nell'esempio:

(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters

Infine, il problema della distanza è legato alla Levenshtein distanza . Ho pensato di usare un Burkhard-Keller albero , ma vedo ora questo non è necessario a tutti, come il problema è piuttosto semplice.

In primo luogo, il numero minimo di inserti / delezioni / modifiche necessarie per rendere una stringa uguale all'altro viene chiamato Levenshtein distanza. Questo è direttamente applicabile al problema: si aggiungono gli spazi, eliminare gli spazi, cambiare minuscole / maiuscole, se necessario. Di solito, questo è meglio risolto con programmazione dinamica, che può essere generalmente considerato mantenere dati sulla soluzione per piccole parti del problema, che poi vengono riutilizzati calcolando altre parti / parti più grandi.

Ma date le particolari restrizioni del nostro problema, possiamo semplicemente confrontare i numeri "binari" che rappresentano spazi / Epsilon.

Inserisci una funzione f (word) restituirà ambienti numero che rappresenta binari in quella parola. Ad esempio, verrà restituito "010" per "Ai ds" e "111" a "a i d s". Il numero di modifiche tra ciascuna combinazione è data come XOR i risultati di f (010 xor 111 = 101), e quindi contando il numero di bit pari a 1. Scriviamo un paio di funzioni in Scala che:

def spacesToBinary(s: String) = {
  (s zip s.drop(1)) // transform "ai ds" into ((a,i), (i, ), ( ,d), (d, s))
  .foldLeft(0) { (binary, pair) => pair match {
      case (' ', _) => binary            // A space is always followed by a letter,
                                         // so we ignore it
      case (_, ' ') => (binary << 1) | 1 // If a letter is followed by a space, bit = 1
      case _ => binary << 1              // If not, bit = 0
  }}
}

def numberOfOnes(d: Int) = {
  var bits = 0
  var n = d
  while(n != 0) {
    if ((n & 1) == 1)
      bits += 1
    n >>= 1
  }
  bits
} 

def spaceDistance(s1: String, s2: String) = 
  numberOfOnes(spacesToBinary(s1) ^ spacesToBinary(s2))

Ora, confrontando minuscole / maiuscole è abbastanza facile, una volta che scartiamo spazi:

def caseDistance(s1: String, s2: String) = {
  val ns1 = s1 filter (_ != ' ')
  val ns2 = s2 filter (_ != ' ')
  (ns1 zip ns2).foldLeft(0){(acc, pair) => acc + (if (pair._1 == pair._2) 0 else 1)}
}

Quindi, la distanza Levenshtein è:

def levenshtein(s1: String, s2: String) = spaceDistance(s1, s2) + caseDistance(s1, s2)

Sappiamo anche le seguenti proprietà circa la distanza Levenshtein. Say d (x, y) è la distanza Levenshtein tra xey. Poi sappiamo:

d(x, y) = 0 if, and only if, x = y
d(x, y) = d(y, x)
d(x, y) + d(y, z) >= d(x, z)

Gli ultimi criteri i conosciuto come la disuguaglianza triange. In poche parole, il percorso da x a z è almeno piccolo come il percorso da x a y oltre al percorso da y a z (pensare un triangolo con vertici x, yez).

Ok, quindi cerchiamo di pensare alle domande bonus.

Quanti percorsi ci sono tra due parole? Beh, se la distanza è Levenshtein n, che significa che hai "n" modifiche uniche, a1, a2, ..., an. Per ogni diverso ordinamento di queste modifiche si dispone di un percorso. Il numero di permutazioni di elementi di "n" è il fattoriale di "n" (o n!):

def factorial(n: Int): Int = n match {
  case 0 => 1
  case _ => n * factorial(n-1)
}

2! = 2
3! = 6
4! = 24
5! = 120
etc

C'è una combinazione "centrale"? In realtà, no. Se andiamo indietro e pensiamo di combinazioni come coppie di numeri binari che rappresentano gli spazi / no-spazi e bassi / uppercases, allora dovrebbe essere ovvio che si può semplicemente invertire i bit per produrre un nuovo Combinatisu cui distanza a quella prescelta è la massima possibile.

O, in altre parole, per ogni combinazione di lettere n, v'è uno e uno solo, combinazione corrispondente, in modo che la distanza Levenshtein tra i due combinazioni è 2 * n - 1, la massima distanza tra due qualsiasi combinazioni.

Vedo che ho dimenticato di calcolare tutte le combinazioni il cui (minima) distanza s è n. Ebbene, sappiamo ogni combinazione può essere rappresentato come due numeri binari, rappresentano gli spazi e la capitalizzazione di ogni lettera, la prima delle quali n-1 cifra lunga, e lungo le seconde n cifre.

Sappiamo anche che possiamo semplicemente invertire una qualsiasi di queste "cifre" per ottenere una differenza. Quindi, se vogliamo ottenere un unico grande numero binario 2 * n - lunga 1 cifre, e noi enumerare tutte le sue cifre, le combinazioni ad una distanza minima d da esso sono date dalla combinazione dei 2 * n-1 cifre in gruppi di dimensioni "d", senza ripetizioni. Per N = 2 * n-1, il numero di tale combinazione è N! / ((N-d) * d!).

Ad esempio, per la distanza e 2 "aids", n = 4, D = 2, N = 2 * 4-1 = 7, e il numero di combinazioni è 7! / (5 * 2!) = 7 * 6/2 = 21.

Possiamo comporre le combinazioni in questo modo:

def computeCombinations(n: Int, d: Int): List[List[Int]] = {
  def gen(d: Int, l: List[Int]): List[List[Int]] = d match {
    case 0 => List(List())
    case _ => for(el <- l;
                  sl <- gen(d-1, l.dropWhile(_ != el).tail))
              yield el :: sl
  }

  gen(d, (0 until n).toList)
}

Ciò restituirà elenchi delle liste di lettera / spazi per cambiare. Indichiamo quale lettera o spaziali mutevoli esigenze attraverso il numero di bit che vogliamo attivare. Per semplificare le cose, si assume il numero binario per la capitalizzazione e il numero binario per lo spazio / no-spazio sono concatenati in un unico numero binario.

Avanti, dobbiamo trovare un modo per produrre le variazioni da queste informazioni. Il maiuscole / minuscole è semplice, supponendo che riceviamo la parola senza spazi:

def toggleCharCase(c: Char) = (c ^ ('A' ^ 'a')).toChar
def toggleCases(s: String, bits: List[Int]) = (
  s.zipWithIndex
  map (t => if (Set(bits: _*) contains t._2) (toggleCharCase(t._1), t._2) else t)
  map (_._1)
)

Commutazione spazi è più difficile. Useremo spacesToBinary, sopra definito, che converte in una lista di numeri di bit che sono impostati, spostare il bit richiesti e ritorno che. In seguito, si usa una funzione diversa per inserire gli spazi nei luoghi corretto:

def toggleSpaces(s: String, bits: List[Int]): List[Int] = {
  val before = spacesToBinary(s)
  val beforeBits = Set() ++ 
                   (for(i <- 0 to 30; // Assuming 32 bits, 1 for sign
                        if (scala.Math.pow(2, i).toInt & before) != 0)
                    yield i)
  val afterBits = (beforeBits union Set(bits: _*)) diff 
                  (beforeBits intersect Set(bits : _*))
  afterBits.toList
}

def addSpaces(s: String, bits: List[Int]): String = (
  s.filter(_ != ' ').zipWithIndex 
  map (t => t._1.toString + (if (bits contains t._2) " " else ""))
  mkString
)

Ora dobbiamo calcolare la differenza di spazio, rimuovere gli spazi, alternare i casi, e quindi aggiungere gli spazi indietro. Vediamo:

def changeCombination(s: String, n: Int, bits: List[Int]) = {
  // Split the binary number with all changes into case changes and space changes
  val spaceBits = bits filter (_ >= n) map (_ - n)
  val caseBits = bits filter (_ < n)

  // Compute the set of spaces after changing them
  val newSpaces = toggleSpaces(s, spaceBits)

  // Remove spaces and toggle case
  val noSpaces = s filter (_ != ' ')
  val caseChanged = toggleCases(noSpaces, caseBits).mkString

  // Now add the spaces as computed before
  val spacesAdded = addSpaces(caseChanged, newSpaces).mkString
  spacesAdded
}

Infine, calcoliamo tutte le combinazioni, e quindi produrre una stringa modificata per ciascuno di essi:

def makeCombinations(s: String, d: Int) = {
  val n = (s filter (_ != ' ')).length
  for(combination <- computeCombinations(n*2-1, d))
  yield changeCombination(s, n, combination)
}

Questo codice è stato testato su tutti i Scala 2.8 (a parte qualche cambiamento titolo che ho appena fatto). Ecco il risultato di una corsa:

scala> makeCombinations("ai ds", 2) foreach println
AI ds
Ai Ds
Ai dS
A i ds
Aids
Ai d s
aI Ds
aI dS
a I ds
aIds
aI d s
ai DS
a i Ds
aiDs
ai D s
a i dS
aidS
ai d S
a ids
a i d s
aid s

Altri suggerimenti

Come le altre risposte già detto, ci sono 2 ^ (n-1) possiblities per il punto 1. A proposito di alcuni dei casi particolari (punto 2):

Che cosa succede se il caso ha fatto la differenza come Ai sd e ai sd sono due gruppi?

Bene, in questo caso si ha avuto 2 ^ n diverse combinazioni di casi, quindi si doveva 2 ^ n * 2 ^ (n-1) = 2 ^ (2 * n - 1) possibilità a tutti

Se si prende il "spazio vuoto", come un personaggio. Dopo tutto l'enumerazione, quanti caratteri avresti scritto?

Questa è una domanda più interessante. Hai 1 possibilità di inserire nessuno spazio, 3 possibilità di inserire 1 posto, 3 possibilites di inserire 2 posti e 1 possibilità di posizionare 3 spazi. Si tratta di una distribuzione binomiale, se ricordo bene, e ci sono formule per calcolare i numeri. È inoltre possibile utilizzare di Pascal triangolo per questo:

   1
  1 1
 1 2 1
1 3 3 1 <- your case (4th row)
  ...

Dopo aver ottenuto questi numeri, calcolare il numero totale dei caratteri in questo modo:

1*4 + 3*5 + 3*6 + 1*7 = 44

http: //www-cs-faculty.stanford. edu / ~ Knuth / fasc3b.ps.gz (download Ghostscript / Ghostview se non è possibile visualizzare PostScript) discute le partizioni in dettaglio.

Per una sequenza di lunghezza n, ci sono 2 ^ (n-1) partizioni. Pensare ad un bit tra ciascuna coppia di elementi consecutivi. Se il bit è impostato, poi sono separati (da uno spazio, come li avete elencato). "Aiuti" (lunghezza 4) ha 2 ^ 3 partizioni possibili.

In risposta alle vostre domande:

Ora per enumerare: O (n * 2 ^ n) - costante nella lunghezza dell'uscita. Non solo il numero di elementi aumenta con la lunghezza di ingresso, ma il numero di caratteri in ogni elemento aumenta pure.

Numero di caratteri scritti: cerchiamo di non contare a capo (se lo fate, aggiungere un altro 2 ^ (n-1) caratteri). Poi ci sono n * 2 ^ (n-1) caratteri non-spazio, più il numero di 1s in tutte le uniche n-1 stringhe di bit cifre. Le stringhe di bit k cifra, quando trascritto, hanno bit k * 2 ^ k, e la metà di questi sono 1. Così il numero totale di caratteri è [n + (n-1) / 2] * 2 ^ (n-1) ), senza contare a capo. Nell'elenco degli 8 Variazioni su "AIDS", ci sono 32 caratteri non-spazio, e 12 spazi -. 4 * 2 ^ 3, e (3/2) * 2 ^ 3 rispettivamente

Modifica distanza: dovrete essere più precisi circa le trasformazioni e il loro costo. Con il termine "parola" Presumo si intende una singola partizione (una delle 8 linee di esempio). Se una modifica è la rimozione o l'aggiunta di un singolo spazio, allora si sta parlando di Hamming distanza su n-1 stringhe di bit cifre.

Un semplice algoritmo per visitare ciascuna delle parole all'interno di distanza k o meno:utilizzando una tabella di hash, per visitare ogni bitstring solo una volta (o un array di 2^(n-1) bit, ma che potrebbe essere troppo grande), in modo ricorsivo visitare ciascuno dei adiacente singola modifica differenze (supponendo distanza di Hamming:per i da 1..(n-1), XOR 2^i con la fonte bitstring, tra l'i-esimo bit).

Fare questo fino a una profondità di k (la profondità è passato con il vostro ricorsione), e avrete visitato tutte le modifiche all'interno di distanza k.Naturalmente, se si desidera solo quelli di esattamente profondità k, ti consigliamo di utilizzare la larghezza di ricerca:invece di immediatamente in visita ogni vicino di casa, tenerli in coda per essere visitato.Durante la visita la coda per gli elementi di una data generazione (j) (aventi tutti lo stesso best modifica di distanza), coda futuro di elementi in una coda diversa per la prossima generazione (j+1).In questo modo si visita ogni stringa prima di impiegare il minor numero possibile di modifiche (breadth first = meglio prima quando ogni transizione ha lo stesso costo).

Se non vuoi fare l'ampiezza di ricerca, allora si può sempre calcolare l'insieme di parole all'interno di k o meno, e situato all'interno di k-1 o meno, e prendere in considerazione la differenza (che si potrebbe utilizzare due tabelle separate).Questo è effettivamente "approfondimento iterativo di ricerca".

B-K alberi non sono appropriati qui a meno che non stai considerando un non strutturati insieme di parole (un dizionario generale).Sappiamo esattamente la struttura delle partizioni per una singola parola già.

Gli argomenti di conteggio sono di destra.

C'è un modo generale programmo problemi come questo, utilizzando branch-and-bound. Ecco un esempio.

In sostanza, invece di scrivere un ciclo per eseguire la scansione della stringa, si scrive una funzione ricorsiva, e tenere traccia dei costi come uno dei suoi argomenti. Poi ad ogni passo, è possibile 1) dimettersi la stringa, per un costo aggiuntivo pari a zero, quindi 2) fare qualche piccola modifica alla stringa, aggiungere un incremento del costo, e poi fare un passo in avanti, e 3) ripetere 2 per come molti diversi tipi di modifiche che si desidera prendere in considerazione.

Quindi avere un bilancio complessivo dei costi, e si rifiutano di prendere qualsiasi filiale dove il costo supererebbe il bilancio.

Infine, come un ciclo esterno, fare il tutto una volta con un budget pari a 0. Se ciò non produce alcun partite, farlo di nuovo con un costo di 1, e così via, fino ad ottenere una o più partite.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow