Reversal Distance

CombinatoricsGenome Rearrangements

Descrizione

Una reversal (inversione) di una permutazione crea una nuova permutazione invertendo un intervallo della permutazione stessa. La reversal distance tra due permutazioni π e σ è il numero minimo di reversal necessarie per trasformare π in σ (permutazioni della stessa lunghezza).

Given

Una collezione di al massimo 5 coppie di permutazioni, tutte di lunghezza 10.

Return

La reversal distance tra ogni coppia di permutazioni.

Sample Dataset

1 2 3 4 5 6 7 8 9 10
3 1 5 2 7 4 9 6 10 8

3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9

8 6 7 9 4 1 3 10 2 5
8 2 7 6 9 1 5 3 10 4

3 9 10 4 1 8 6 7 5 2
2 9 8 5 1 7 3 4 6 10

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Sample Output

9 4 5 7 0

Nota

Lo script Python tenta di precalcolare via BFS i livelli di distanza per tutte le permutazioni di 10 elementi (salvandoli in una cache locale, sets10.txt, per evitare di rifare il calcolo ad ogni esecuzione) - ma quel calcolo è così pesante che il file di cache non viene generato in tempi ragionevoli, né in locale né tanto meno nel browser (Pyodide/WebAssembly). La soluzione JavaScript di questo catalogo risolve lo stesso problema con un Web Worker, senza bisogno di cache persistente: richiede qualche minuto ma completa senza bloccare la pagina.

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

3 8 6 2 7 4 1 9 10 5
1 6 9 5 3 4 7 10 2 8

6 8 10 7 3 9 5 4 2 1
2 1 5 6 4 8 3 10 9 7

5 2 10 1 6 7 8 4 3 9
10 5 6 2 8 1 3 7 9 4

9 5 8 6 10 2 1 3 4 7
3 6 10 4 9 5 2 1 8 7

3 6 4 8 2 7 5 10 9 1
3 5 7 4 6 9 10 8 1 2

Output · run_log.txt

6 6 9 4 5

Esegui nel browser

Non disponibile per questo problema: BFS esaustivo su tutte le permutazioni di 10 elementi (3.628.800 nodi): non completa in tempi ragionevoli sotto Pyodide/WebAssembly. Usa la soluzione JavaScript qui sotto, che esegue lo stesso calcolo in un Web Worker (qualche minuto, ma senza bloccare la pagina).

Mostra il codice sorgente (problem.py)

#http://rosalind.info/problems/rear/

def lettura(filename):
    dati = []
    with open(filename) as f:
       for riga in f:
         riga = riga.replace("\n", "")
         if len(riga) > 0:
            lista = riga.split(" ") 
            dati.append(lista)
    return dati 



def print_table(nodes, rules, cache):
    news = []
    for v in nodes:
        row = []
        for rule in rules:
            w = transform(v, rule)
            if not w in cache:
               cache.add(w)
               news.append(w)
            row.append(w)
        #print(v, row)
    return news

stringify = lambda x: ('').join([str(i) for i in range(x)])
 
def f_adiacents(v):
    z = [v]
    for i in range(len(v)):
       for j in range(i+1, len(v)):
         w = ""
         for k in range(len(v)):
           if k<i or k>j:
            w += v[k]
           else:
            w += v[j-k+i]
         z.append(w)
    return z

def transform(v, rule):
    return ''.join([v[int(i)] for i in rule]) 

def path_score(sets, end): 
    #print(len(sets), start, end)
    for i in range(len(sets)):
        if end in sets[i]:
           return i

def trans(a, b):
    n = len(a)
    return (stringify(n), "".join([str(b.index(x)) for x in a]))	

def main_write():
 with open('sets10.txt', 'w') as the_file:
    n = 10
    unit = stringify(n)
    maxloops = 100
    rules = f_adiacents(unit)
    sets = []
    news = [unit]
    loops = 1
    cache = set()
    while len(news) > 0 and loops < maxloops:
       sets.append(news)
       news = print_table(news, rules, cache)
       the_file.write(str(news))
       the_file.write("\n")
       loops += 1
    return sets    

def main_read():
 n = 10
 unit = stringify(n)
 sets = [unit]
 try:
    with open('sets10.txt', 'r') as the_file:
        sets.extend(the_file)
        return sets 
 except FileNotFoundError:
    return main_write()

def main():
    sets = main_read() 
    f = lambda a: ('').join([str(int(x)-1) for x in a])
    dati = lettura("dataset.txt")
    solution = []
    for index in range(0, len(dati), 2):
        start =  f(dati[index+0])
        end = f(dati[index+1])
        #print(start, end)
        start, end = trans(start, end)
        #print(start, end)
        #print()
        score = path_score(sets, end)
        solution.append(str(score))
    print(" ".join(solution))

if __name__ == "__main__":
    # execute only if run as a script
    #start_time = time.time()
    main() 
    #end_time = time.time()
    #print(round(end_time - start_time, 2))

Soluzione JavaScript

Esegui ora, live

Qui il JS è l'unica opzione praticabile nel browser, ma richiede una elaborazione molto lunga.

Mostra il codice sorgente

// Reversal Distance (Rosalind ID: REAR) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py.
//
// Il calcolo vero e proprio (BFS sull'intero grafo delle permutazioni
// di 10 elementi, 3.628.800 nodi) gira in rear.worker.js, un Web
// Worker su un thread separato - vedi i commenti lì per l'algoritmo
// completo e le note di correttezza. Farlo girare sul thread
// principale (come nella prima versione di questo file) bloccava la
// UI della pagina finché il calcolo non finiva; su un worker la pagina
// resta reattiva, anche se il calcolo stesso richiede comunque lo
// stesso tempo (da decine di secondi a qualche minuto, a seconda
// dell'hardware).
//
// Compatibilità: rear.worker.js è un worker "classico" (non un ES
// module worker), per il supporto più ampio possibile tra browser.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).

// Worker persistente a livello di modulo: se l'utente preme "Esegui
// ora" più volte nella stessa sessione di pagina, si riusa lo stesso
// worker (che ha già la sua cache interna del BFS) invece di crearne
// uno nuovo ogni volta.
let _worker = null;

function getWorker() {
  if (!_worker) {
    _worker = new Worker(new URL("./rear.worker.js", import.meta.url));
  }
  return _worker;
}

export default function solve(datasetText) {
  return new Promise((resolve, reject) => {
    const worker = getWorker();

    function onMessage(evento) {
      worker.removeEventListener("message", onMessage);
      worker.removeEventListener("error", onError);
      const { ok, result, error } = evento.data;
      if (ok) resolve(result);
      else reject(new Error(error));
    }

    function onError(err) {
      worker.removeEventListener("message", onMessage);
      worker.removeEventListener("error", onError);
      reject(new Error(err?.message ?? "Errore nel Web Worker"));
    }

    worker.addEventListener("message", onMessage);
    worker.addEventListener("error", onError);
    worker.postMessage(datasetText);
  });
}