Znajdowanie anagramów dla danego słowa

Chyba wymyśliłem nowe rozwiązanie. Wykorzystuje podstawowe twierdzenie arytmetyki. Chodzi więc o użycie tablicy 26 pierwszych liczb pierwszych. Następnie dla każdej litery w słowie wejściowym otrzymujemy odpowiednią liczbę pierwszą A= 2, B = 3, C = 5, D = 7 ... a następnie obliczamy iloczyn naszego słowa wejściowego. Następnie robimy to dla każdego słowa w Słowniku i jeśli słowo pasuje do naszego słowa wejściowego, dodajemy je do listy wynikowej. Wszystkie anagramy będą miały ten sam podpis, ponieważ

Każda liczba całkowita większa od 1 jest albo liczbą pierwszą, albo może być zapisana jako unikalny iloczyn liczb pierwszych (ignorując kolejność).

private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
        37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
        107, 109, 113 };

Oto Metoda:

 private long calculateProduct(char[] letters) {
    long result = 1L;
    for (char c : letters) {
        if (c < 65) {
            return -1;
        }
        int pos = c - 65;
        result *= PRIMES[pos];
    }
    return result;
}

Wiemy, że jeśli dwa słowa nie mają tej samej długości, nie są anagramami. Możesz więc podzielić słownik na grupy słów o tej samej długości.

Teraz skupiamy się tylko na jednej z tych grup i w zasadzie wszystkie słowa mają dokładnie taką samą długość w tym mniejszym wszechświecie.

Jeśli każda pozycja litery jest wymiarem, a wartość w tym wymiarze jest oparta na literze (powiedzmy kod ASCII). Następnie można obliczyć długość wektora słowa.

Na przykład, say 'A' = 65, 'B' = 66, then length("AB") = sqrt(65*65 + 66*66). Oczywiście, length("AB") = length("BA").

Oczywiście, jeśli dwa słowa są anagramami, to ich wektory mają tę samą długość. Kolejne pytanie brzmi: jeśli dwa wektory wyrazowe (o tej samej liczbie liter) mają tę samą długość, to czy są anagramami? Intuicyjnie powiedziałbym, że nie, ponieważ wszystkie wektory o tej długości tworzą sferę, jest ich wiele. Nie jestem pewien, ponieważ w tym przypadku jesteśmy w przestrzeni całkowitej, ile ich jest w rzeczywistości.

Ale przynajmniej pozwala na podzielenie twojego słownik jeszcze dalej. Dla każdego słowa w słowniku Oblicz odległość wektora: for(each letter c) { distance += c*c }; distance = sqrt(distance);

Następnie utwórz mapę dla wszystkich słów o długości n i wprowadź do niej odległość, a wartość jest listą słów o długości n, które dają określoną odległość.

Utworzysz mapę dla każdej odległości.

Wtedy twoje wyszukiwanie staje się następującym algorytmem:

1. użyj poprawnej mapy słownikowej na podstawie długości słowa
2. Oblicz długość wektor twojego słowa
3. wyszukuje listę słów, które pasują do tej długości
4. Przejrzyj listę i wybierz anagramy używając naiwnego algorytmu, teraz lista kandydatów jest znacznie zmniejszona

Well Tries ułatwiłoby sprawdzenie, czy słowo istnieje. Więc jeśli umieścisz cały słownik w trie:

Http://en.wikipedia.org/wiki/Trie

Następnie możesz wziąć swoje słowo i wykonać proste backtracking, pobierając znak i rekurencyjnie sprawdzając, czy możemy "przejść" w dół Trie z dowolną kombinacją pozostałych znaków (dodając jeden znak na raz). Gdy wszystkie znaki są używane w gałęzi rekurencyjnej i w Trie była ważna ścieżka, wtedy słowo istnieje.

W pseudo-kodzie

checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
    if (restOfWord == 0)
    {
         AddWord(currentlyUsedChar)
    }
    else 
    {
        foreach (char in restOfWord)
        {
            nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
            if (nextPositionInTrie != Positions.NOT_POSSIBLE)
            {
                checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
            }
        }   
    }

Oczywiście potrzebujesz ładnej struktury danych Trie, która pozwoli Ci stopniowo "chodzić" po drzewie i sprawdzać przy każdym węźle, czy istnieje ścieżka z podanym znakiem do dowolnego następny węzeł...

static void Main(string[] args)
{

    string str1 = "Tom Marvolo Riddle";
    string str2 = "I am Lord Voldemort";

    str2=  str2.Replace(" ", string.Empty);
    str1 = str1.Replace(" ", string.Empty);
    if (str1.Length != str2.Length)
        Console.WriteLine("Strings are not anagram");
    else
    {
        str1 = str1.ToUpper();
        str2 = str2.ToUpper();
        int countStr1 = 0;
        int countStr2 = 0;
        for (int i = 0; i < str1.Length; i++)
        {
            countStr1 += str1[i];
            countStr2 += str2[i];

        }
        if(countStr2!=countStr1)
            Console.WriteLine("Strings are not anagram");
        else Console.WriteLine("Strings are  anagram");

    }
    Console.Read();
}

• zmniejsz słowa do - powiedz-małe litery (clojure.string/lower-case).
• Sklasyfikuj je (group-by) według częstotliwości liter-map (frequencies).
• zrzuć mapy częstotliwości,
• ... pozostawiając zbiory anagramów.

(These) są odpowiednimi funkcjami w dialekcie Lispu Clojure.

Cała funkcja może być wyrażona tak:

(defn anagrams [dict]
  (->> dict
       (map clojure.string/lower-case)
       (group-by frequencies)
       vals))

Na przykład,

(anagrams ["Salt" "last" "one" "eon" "plod"])
;(["salt" "last"] ["one" "eon"] ["plod"])

Funkcja indeksująca, która odwzorowuje każdą rzecz do jej zbioru is

(defn index [xss]
  (into {} (for [xs xss, x xs] [x xs])))

Tak, że np.

((comp index anagrams) ["Salt" "last" "one" "eon" "plod"])
;{"salt" ["salt" "last"], "last" ["salt" "last"], "one" ["one" "eon"], "eon" ["one" "eon"], "plod" ["plod"]}

... gdzie comp jest operatorem kompozycji funkcjonalnej.

Generowanie wszystkich permutacji jest łatwe, chyba obawiasz się, że sprawdzenie ich istnienia w słowniku jest częścią "wysoce nieefektywną". Ale to w rzeczywistości zależy od tego, jakiej struktury danych użyjesz W słowniku: oczywiście lista słów byłaby nieefektywna dla Twojego przypadku użycia. Mówiąc o próbach , prawdopodobnie byłyby one idealną reprezentacją, a także całkiem skuteczną.

Inną możliwością byłoby wykonanie jakiegoś wstępnego przetworzenia w słowniku, np. zbudowanie hashtable, gdzie klucze są literami słowa posortowane, a wartości są listami słów. Możesz nawet serializować tę hashtable, dzięki czemu możesz zapisać ją do pliku i szybko przeładować później. Następnie, aby wyszukać anagramy, po prostu posortujesz dane słowo i wyszukujesz odpowiedni wpis w tabeli hashtable.

To zależy od sposobu przechowywania słownika. Jeśli jest to prosta tablica słów, żaden algorytm nie będzie szybszy niż liniowy.

Jeśli jest posortowane, to oto podejście, które może zadziałać. Właśnie to wymyśliłem, ale myślę, że to szybsze niż liniowe podejście.

1. Oznacz słownik jako D, bieżący prefiks jako S. S = 0;
2. tworzysz mapę częstotliwości dla swojego słowa. Oznaczmy go przez F.
3. używając wyszukiwania binarnego znajdź Wskaźniki na początek każdej litery w słowniku. Lets oznacza tę tablicę wskaźników przez P.
4. dla każdego znaku c od A do Z, jeśli F [c] = = 0, pomiń go, else
   • S + = c;
   • F [c]--;
   • P
   • rekurencyjnie wywołaj Krok 4, dopóki nie znajdziesz dopasowania dla Twojego słowa lub dopóki nie stwierdzisz, że takie dopasowanie nie istnieje.

I tak bym to zrobił. Powinno być bardziej konwencjonalne podejście, ale jest to szybsze niż liniowe.

Próbowałem zaimplementować rozwiązanie hashmap

public class Dictionary {

    public static void main(String[] args){

    String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};

    HashMap<String,String> h=new HashMap<String, String>();

    QuickSort q=new QuickSort();

    for(int i=0;i<Dictionary.length;i++){

        String temp =new String();

        temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog

        if(!h.containsKey(temp)){
           h.put(temp,Dictionary[i]);
        }

        else
        {
           String s=h.get(temp);
           h.put(temp,s + " , "+ Dictionary[i]);
        }
    }

    String word=new String(){"tolo"};

    String sortedword = q.quickSort(word);

    if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive

        System.out.println("anagrams from Dictionary   :  " + h.get(sortedword.toLowerCase()));
    }

}

• Oblicz wektor liczby częstotliwości dla każdego słowa w słowniku, wektor długości listy alfabetu.
• Wygeneruj losowy Wektor Gaussa długości listy alfabetu

• Wyświetl wektor liczenia każdego słowa słownikowego w tym losowym kierunku i zapisz wartość (Wstaw tak, aby tablica wartości została posortowana).

• Biorąc pod uwagę nowe słowo testowe, wyświetl je w tym samym losowym kierunku, w którym zastosowano słowa słownikowe.

• Zrób plik binarny Szukaj, aby znaleźć listę słów, które mapują do tej samej wartości.
• Sprawdź, czy każde słowo uzyskane jak powyżej jest prawdziwym anagramem. Jeśli nie, usuń go z listy.
• zwraca pozostałe elementy listy.

PS: powyższa procedura jest uogólnieniem procedury liczby pierwszej, która może potencjalnie prowadzić do dużych liczb (a tym samym problemów z precyzją obliczeniową)

Jednym z rozwiązań jest - Mapuj liczby pierwsze do znaków alfabetu i pomnóż liczbę pierwszą

For ex - 

    a -> 2
    b -> 3
    ......
    .......
    ......
    z -> 101

Więc

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36

Get MUL_number for Given word. zwraca wszystkie słowa ze słownika, które mają ten sam numer MUL_number co podane słowo

Najpierw sprawdź, czy długość łańcuchów jest taka sama. następnie sprawdź, czy suma znaków w obu łańcuchach jest taka sama (tj. suma kodu ascii) wtedy słowa są anagramami else not anagram