Trovare anagrammi interessanti

cs.stackexchange https://cs.stackexchange.com/questions/2259

Domanda

dire che $ a_1a_2 \ ldots a_n $ e $ b_1b_2 \ ldots b_n $ sono due stringhe della stessa lunghezza. Un anagrammi di due stringhe è un biunivoca mappatura $ p: [1 \ ldots n] \ a [1 \ ldots n] $ tale che $ A_i = b_ {p (i)} $ per ogni $ i $.

Non ci potrebbe essere più di un'anagrammi per la stessa coppia di stringhe. Ad esempio, se $ a = $ `abcab` e $ b = $ cabab abbiamo $ P_1 [1,2,3,4,5] \ a [4,5,1,2,3] $ e $ P_2 [ 1,2,3,4,5] \ a [2,5,1,4,3] $, tra gli altri.

Si dirà che il di peso $ w (p) $ di anagrammi $ p $ è il numero di tagli si deve fare nella prima stringa per ottenere pezzi che possono essere riorganizzate per ottenere la seconda stringa. Formalmente, questo il numero di valori di $ i \ in [1 \ ldots n-1] $ per cui $ p (i) +1 \ ne p (i + 1) $. Che è, è il numero di punti in cui $ p $ non aumento da esattamente 1.Per esempio $ w (P_1) = 1 $ e $ w (P_2) = 4 $, perché $ P_1 $ tagli 12345 una volta, nei pezzi 123 e 45, e $ $ P_2 tagli 12345 quattro volte, in cinque pezzi.

Si supponga che esiste un anagrammi per due stringhe $ a $ e $ b $. Poi almeno un anagrammi deve avere almeno il peso. Diciamo che questo questo è leggero . (Ci potrebbe essere più anagrammings leggeri;. Non mi interessa perché sono interessati solo i pesi)

Domanda

Voglio un algoritmo che, dato due stringhe per i quali esiste un anagrammi, in modo efficiente cede il peso esatto del anagrammi più leggero delle due stringhe. E 'tutto a posto se l'algoritmo produce anche un'anagrammi più leggero, ma non è necessario.

E 'una questione abbastanza semplice per generare tutti anagrammings e pesarli, ma ci possono essere molti, così io preferirei un metodo che trova anagrammings luce direttamente.

Motivazione

Il motivo di questo problema è di interesse è la seguente. E 'molto facile fare ricerca al computer il dizionario e trovare anagrammi, coppie di parole che contengono esattamente le stesse lettere. Ma molti degli anagrammi prodotte sono poco interessanti. Per esempio, gli esempi più lunga trovata in Second dizionario Webster Internazionale sono:

cholecystoduodenostomy
duodenocholecystostomy

Il problema dovrebbe essere chiaro: sono poco interessante perché ammettono un'anagrammi molto leggero che semplicemente scambi il cholecysto, sezioni duedeno e stomy, per un peso di 2. D'altra parte, questo esempio molto più breve è molto più sorprendente e interessante:

costa
sezione

Qui l'anagrammi più leggero ha un peso 8.

Ho un programma che utilizza questo metodo per individuare anagrammi interessanti, in particolare quelli per i quali tutti sono anagrammings di peso elevato. Ma fa generando e pesatura tutte le possibili anagrammings, che è lento.

È stato utile?

Soluzione

Questo problema è noto come il “problema minima della partizione comune stringa.” (Più precisamente, la risposta al problema minimo comune partizione stringa è uguale la risposta nel vostro problema più 1.) Purtroppo, è NP-difficile, anche con la restrizione che ogni lettera si verifica al massimo due volte in ciascuna delle stringhe di input, come è dimostrato da Goldstein, Kilman, e Zheng [GKZ05]. Ciò significa che nessun algoritmo polinomiale esiste meno che P = NP. (Naturalmente, se ogni lettera si verifica al massimo una volta, allora il problema è banale, perché c'è un solo anagrammi.)

Sul lato positivo, gli stessi autori [GKZ05] invia un algoritmo polinomiale 1,1037-approssimazione sotto la stessa restrizione. (A “1.1037- ravvicinamento algoritmo ” si intende un algoritmo che possono non emettere la risposta corretta A ma è garantito per uscita un valore B tale che a = B = 1,1037 a .) danno anche un tempo lineare algoritmo 4 approssimazione sotto la restrizione debole che ogni lettera si verifica più di tre volte in ciascuna delle stringhe di input.

[GKZ05] Avraham Goldstein, Petr Kolman, e Jie Zheng. Minimo problema partizione comune stringa: durezza e approssimazioni. elettronico ufficiale combinatorio , 12, articolo R50, 2005. http : //www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Altri suggerimenti

Questo è un follow-up per la risposta di Tsuyoshi Ito sopra , che riassume la parte più rilevante del carta GKZ05 ha citato.

Il documento dimostra una riduzione della massima Independent Set ( MIS ) problema. Costruzione di un grafico $ G $ i cui vertici sono coppie $ (i, j) $ tale che $ a_i = b_j $ e $ a_ {i + 1} = b_ {j + 1} $. Connect vertici $ (i, j) $ e $ (k, \ ell) $ (dove $ i=k $) con un bordo ogni volta che è impossibile che un Anagrammare potrebbe mappare tutti $ i \ mapsto j $ e $ i + 1 \ mapsto j + 1 $ e $ k \ mapsto \ ell $ e $ k + 1 \ mapsto \ ell + 1 $. Questo è facile da rilevare; una tale mappatura è impossibile esattamente se una delle seguenti vale:

  1. $ i = k $ e $ j \ ne \ ell $
  2. $ i + 1 = k $ e $ j + 1 \ ne \ ell $
  3. $ i + 1

Say il grafico risultante $ G $ ha un insieme indipendente massimale di formato $ s $. Poi il peso minimo anagrammi è esattamente $ n-s-1 $, dove $ n $ è la lunghezza delle stringhe $ a $ e $ b $. (L'inverso vale anche:... Un Anagrammare basso peso traduce direttamente in una grande MIS per $ G $ Per dettagli, vedere pp 4-5 della carta)

Per esempio, prendere in considerazione i due stringhe yttrious e touristy. Il grafico corrispondente ha due vertici, uno per la coppia ou condiviso e uno per la coppia ri condivisa. Non v'è alcun margine tra i vertici, perché è possibile avere un anagrammi che mappa sia ou a ou e ri a ri; oppure si può verificare che le tre condizioni soprattutto sicuro. Quindi il grafico ha ovviamente un MIS di formato $ s = 2 $ e il peso minimo Anagrammare è infatti 8-2-1 = 5, corrispondente al Anagrammare y|t|t|ri|ou|s ? t|ou|ri|s|t|y '.

D'altra parte, si consideri derater e treader. Questa volta il grafico ha tre vertici:

  1. DErater + treaDEr
  2. dERater + treadER
  3. deratER + treadER

2 e 3 sono incompatibili, e 1 e 3 sono incompatibili, ma 1 e 2 sono compatibili. Così l'unica MIS ha formato $ s = 2 $ e contiene i vertici 1 e 2. La corrispondente anagrammi di peso 7-2-1 = 4 è der|a|t|e|r ? t|r|e|a|der.

E non copre l'algoritmo esatto che aveva in mente (che la risposta di Tsuyoshi Ito fa ), ma cercando di arrivare il problema di fondo di trovare "interessante" anagrammi ...

Il mio primo pensiero è stato quello di utilizzare qualche variazione su Edit-distanza, dove i cambiamenti atomiche sono ponderati in base alla loro "interestingness" piuttosto che il solito "difficoltà" o ponderazioni "confondibilità". Certo, sembra improbabile che si può codificare in modo efficiente le trasformazioni veramente interessanti in questo modo, dato che sono suscettibili di essere non locale e quindi incorrere in problemi NP-completi di MIS, ecc.

Quindi, secondo pensiero sarebbe quello di costruire un allineamento lettera a lettera tra le parole (à l'allineamenti traduzione automatica), e quindi di segnare allineamenti stessi per "interestingness" (ad esempio, contando gli allineamenti che prendono lettere adiacenti alle lettere non adiacenti, o quanti allineamenti ciascuno croci di allineamento, ecc;. e poi combinarli tutti i modelli tramite log-lineare o tali)

Terzo idea è quella di abbandonare completamente guardando la struttura del anagrammi in sé, e invece guardate la semantica delle parole. Spesso ciò che rende un anagramma "interessante" è l'incongruenza tra i significati delle parole coinvolti. Quindi, provare qualcosa di simile calcolare la loro distanza in WordNet, o simili.

Il problema può essere formulata in termini di permutazione gruppi .

Ora un gruppo di permutazioni contiene tutti i "anagramma mosse", sia primitivo (scambiando due lettere) e composto di sequenze di movimenti primitivi. Sembra che ti interessa solo un sottoinsieme delle possibili permutazioni. Cercherò di definire questi.

In primo luogo, richiamare la notazione per permutazioni, cioè, il cosiddetto ciclo notazione :

  • $ () $ mezzi non permutazione.
  • $ (1) $ mezzo 1 viene scambiato con 1, che è anche non permutazione.
  • $ (12) $ mezzi 1 e 2 vengono scambiati.
  • $ (123) $ mezzi 1 sostituisce 2 che sostituisce 3 che sostituisce 1 (a rotazione).
  • e così uno

Queste semplici 'cicli' sono composti da descrivere permutazioni più complessi.

Sembra che le mosse a cui sei interessato sono (per una parola di lunghezza $ n $):

Queste mosse costituiscono la base per il vostro algoritmo. Quello che ci interessa è trovare la più piccola sequenza di queste mosse per passare da una parola alla successiva.

Non so qualsiasi algoritmo per calcolare questo, a parte la ricerca di forza bruta, ma almeno ora c'è una chiara (spero) descrizione di ciò che le mosse sono primitivi. (E forse un po 'teorico del gruppo tra di noi può puntare a un algoritmo appropriato.)

Per cholecystoduodenostomy / duodenocholecystostome, mi accorgo che se è stato assegnato un numero ad ogni personaggio che descrive quanto è stato spostato come un delta, si avrebbe qualche cosa come 7 7 di, poi 8, poi -7s 6 0 di. Questo non è giusto, perché alcuni caratteri potrebbero essere stati ripetuti (il secondo c solo spostato in avanti 2, non indietro 7), ecc, ma ancora molto "run length codificabili" perché si vede lo stesso delta di fila.

Confronto a coste / sezione, in cui si vede qualcosa di simile (2) (+ 5) (+ 5) (- 3) (- 1) (+ 3) .... molto meno "lunghezza codificabili run".

Forse la casualità dei delta potrebbe darvi un "punteggio" di come interessante l'anagramma è?

Non affiliato a cs.stackexchange
scroll top