Minimalna liczba transformacji aby przekształcić jeden String w drugi

0

Mam za zadanie napisać algorytm który zwróci minimalną liczbę transformacji potrzebną aby przekstałcić jeden string w drugi. Transformacja to zamiana wszystkich wystąpień jednej litery na drugą. Jeśli przekształcenie jednego stringu w drugi nie jest możliwe poprzez same transformacje, to wynikiem jest -1. Czyli np.:

  1. "ggg" -> "hhh": 1 (ponieważ wystarczy jedna transformacja 'g'->'h'
  2. "bbnndd" -> "dddddd": 2
  3. "xx" -> "ga": -1
  4. "ah" -> "ha": 3 (np. 'a'->'b', później 'h'->'a', i na końcu 'b'->'h')

Próbowałem zmodyfikować algorytm Levenshtein'a, tak aby recurrence relation zawierało tylko odniesienie do substytucji (tzn. aby pominąć części odpowiedzialne za insertion/deletion), tj:

dp[i][j] = dp[i - 1][j - 1]  + s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1;

zamiast oryginalnego:

dp[i][j] = min(dp[i][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i - 1][j - 1]  + s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1))

Ale to niestety nie jest takie proste, taki algorytm zwraca błędne odpowiedzi. Najwidoczniej algorytm Levenshtein'a ma sens tylko gdy pozbywamy się jednego z trzech elementów (wstawianie, usuwanie, substytucja)?

W każdym razie, czy ktoś ma pomysł jak optymalnie rozwiązać ten problem?

0

Tu jest błąd:
4."ah" -> "ha": 3 (np. 'a'->'b', później 'h'->'a', i na końcu 'b'->'h')
Wystarczą dwie operacje a -> h i h -> a.

0

Transformacja jest strukturą zawierającą znak szukany i znak docelowy
Transformacja jest tożsama z inną jeżeli obie wykonują to samo działanie na tym samym znaku.
Transformacje sprzeczne, to takie, w których jeden znak szukany jest tłumaczony na różne znaki docelowe (np. w przypadku ciągów "aaa" ->"bcd")
Alfabet - wszystkie możliwe wartości znaków

Na podstawie sIn i sOut wygeneruj zbiór unikalnych transformacji T
Jeżeli występują transformacje sprzeczne zwróć -1
Jeżeli T.size == alphabeth.size zwróć -1
Usuń transformacje niedokonujące zmian (np a ->a) z T
Ustaw licznik koniecznych transformacji c na T.size
Powtarzaj momentu opróżnienia zbioru T:
dopóki się da, usuwaj ze zbioru T transformacje nie powodujące konfliktów (takie, których wyjście nie występuje jako wejście innych)
usuń ze zbioru transformację z największą liczbą konfliktów, zwiększ wartość c o 1 (dodatkowa transformacja "pośrednia")

1

Udało mi się wymyślić stosunkowo prosty algorytm, który działa w czasie O(n^2) (zakładając O(1) iterowanie po stringu):

use std::collections::{HashMap, HashSet};

#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
struct Change {
    from: char,
    to: char,
}

impl Change {
    fn new(from: char, to: char) -> Self {
        Self { from, to }
    }
}

fn transform(from: &str, to: &str) -> Result<Vec<Change>, ()> {
    assert_eq!(from.len(), to.len());

    // Spis transformacji `z jakiego znaku => na jaki znak`
    // (nie możemy tutaj wykorzystać hash-setu albo btree-setu, gdyż istotna
    // jest kolejność operacji)
    let mut changes = Vec::new();

    // Zbiór zużytych transformacji
    // (wykorzystujemy go do de-duplikacji zwróconego wektora tak, abyśmy nie
    // zwracali niepotrzebnie wielokrotnie tych samych transformacji)
    let mut performed_changes = HashSet::new();

    // Zbiór wykorzystanych znaków wyjściowych
    // (wykorzystywany do szybkiego wyszukiwania proxy-znaków)
    let mut used_chars: HashSet<_> = to.chars().collect();

    // Mapa `z jakiego znaku => na jaki znak`
    // (wykorzystujemy ją do wykrywania sytuacji w której transformacja nie jest
    // wzajemnie jednoznaczną)
    let mut used_mappings = HashMap::new();

    let mut pending_changes = Vec::new();

    for (pos, (from_ch, to_ch)) in from.chars().zip(to.chars()).enumerate() {
        if from_ch == to_ch {
            continue;
        }

        if let Some(to_ch2) = used_mappings.insert(from_ch, to_ch) {
            // To porównanie umożliwia nam wykrycie sytuacji, w której
            // transformacja nie jest wzajemnie jednoznaczna dla danych
            // argumentów (np. `aa` -> `bc`)
            if to_ch != to_ch2 {
                return Err(());
            }
        }

        // Aby określić czy wymagany jest proxy znak (np. dla `ab` -> `ba`),
        // sprawdzamy czy *w przyszłości* (w następnych znakach) planujemy
        // wykorzystać zamianę `* -> to_ch`.
        //
        // Dodatkowy warunek `from_ch2 != to_ch2` umożliwia nam zgrabne ogranie
        // sytuacji w stylu `bbnndd` -> `dddddd`, do których bez tego warunku
        // również zostałby zastosowany (niepotrzebnie) proxy-znak
        let requires_proxy = from
            .chars()
            .zip(to.chars())
            .skip(pos)
            .find(|(from_ch2, to_ch2)| {
                from_ch2 != to_ch2
                && *from_ch2 == to_ch
            })
            .is_some();

        if requires_proxy {
            let proxy_ch = ('a'..='z')
                .filter(|char| !used_chars.contains(char))
                .next()
                .ok_or(())?;

            used_chars.insert(proxy_ch);
            changes.push(Change::new(from_ch, proxy_ch));
            pending_changes.push(Change::new(proxy_ch, to_ch));
        } else {
            let change = Change::new(from_ch, to_ch);

            if performed_changes.insert(change) {
                changes.push(change);
            }
        }
    }

    changes.extend(pending_changes);

    Ok(changes)
}

fn main() {
    println!("{:?}", transform("ggg", "hhh"));
    println!("{:?}", transform("bbnndd", "dddddd"));
    println!("{:?}", transform("xx", "ga"));
    println!("{:?}", transform("ah", "ha"));
}

(https://play.rust-lang.org/?v[...]42c78808fe7c891d41b47b2d920a7)

Wydaje mi się, że można by spróbować zamienić pętlę z let requires_proxy = /* ... */; na hashmapę znak => liczba pozostałych transformacji, dzięki czemu całość zamykałaby się w O(n).

Plus, dla optymalizacji pamięci, zdaje się, że można by się również pozbyć performed_changes na rzecz used_mappings.

0

Na oko budowanie grafu da liniówkę od liczby zamian.Idziesz przez każdą pozycję, dokładasz krawędź znakŹródłowy->znakDocelowy. Potem sprawdzasz, czy któryś z wierzchołków ma stopień wyjściowy większy od jedynki (wtedy nie da się rozwiązać i wynikiem jest -1). Potem szukasz cykli, dla każdego będziesz miał znak pośredni, więc rozbijasz ten cykl jakkolwiek (najlepiej użyć jakiegoś znaku spoza alfabetu, a jak musi być w alfabecie, to szukasz dowolnego nieużytego znaku ze stopniem wyjściowym 0 i do niego przepinasz). Jak rozbijesz cykle, to rozwiązaniem jest liczba krawędzi w grafie (plus te dodatkowe rozbicia cykli).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0