Algo: Suchen Sie ein Anagramm der gegebenen Zeichenfolge in einem gegebenen Index in lexikografisch sortierter Reihenfolge

Question

Sie müssen einen Algo schreiben, um Anagram der gegebenen Zeichenfolge in einem bestimmten Index in lexikographisch sortierter Reihenfolge zu finden. Zum Beispiel:

Betrachten wir einen String: ABC dann alle Anagramme in sortierter Reihenfolge sind: ABC ACB BAC BCA CAB CBA. Also, für Index 5 Wert ist: CAB. Auch sei der Fall Duplikate wie für AADFS Anagramm wäre DFASA bei Index 32

Um dies zu tun, die ich geschrieben habe Algo aber ich denke, es sollte etwas weniger komplex als das sein.

import java.util.*; 
public class Anagram { 

static class Word { 
    Character c; 
    int count; 

    Word(Character c, int count) { 
     this.c = c; 
     this.count = count; 
    } 
} 

public static void main(String[] args) { 
    System.out.println(findAnagram("aadfs", 32)); 
} 


private static String findAnagram(String word, int index) { 
    // starting with 0 that's y. 
    index--; 

    char[] array = word.toCharArray(); 
    List<Character> chars = new ArrayList<>(); 
    for (int i = 0; i < array.length; i++) { 
     chars.add(array[i]); 
    } 
    // Sort List 
    Collections.sort(chars); 

    // To maintain duplicates 
    List<Word> words = new ArrayList<>(); 
    Character temp = chars.get(0); 
    int count = 1; 
    int total = chars.size(); 
    for (int i = 1; i < chars.size(); i++) { 
     if (temp == chars.get(i)) { 
      count++; 
     } else { 
      words.add(new Word(temp, count)); 
      count = 1; 
      temp = chars.get(i); 
     } 
    } 
    words.add(new Word(temp, count)); 

    String anagram = ""; 
    while (index > 0) { 
     Word selectedWord = null; 
     // find best index 
     int value = 0; 
     for (int i = 0; i < words.size(); i++) { 
      int com = combination(words, i, total); 
      if (index < value + com) { 
       index -= value; 
       if (words.get(i).count == 1) { 
        selectedWord = words.remove(i); 
       } else { 
        words.get(i).count--; 
        selectedWord = words.get(i); 
       } 
       break; 
      } 
      value += com; 
     } 
     anagram += selectedWord.c; 
     total--; 
    } 
    // put remaining in series 
    for (int i = 0; i < words.size(); i++) { 
     for (int j = 0; j < words.get(i).count; j++) { 
      anagram += words.get(i).c; 
     } 
    } 
    return anagram; 
} 

private static int combination(List<Word> words, int index, int total) { 
    int value = permutation(total - 1); 
    for (int i = 0; i < words.size(); i++) { 
     if (i == index) { 
      int v = words.get(i).count - 1; 
      if (v > 0) { 
       value /= permutation(v); 
      } 
     } else { 
      value /= permutation(words.get(i).count); 
     } 
    } 
    return value; 
} 

private static int permutation(int i) { 
    if (i == 1) { 
     return 1; 
    } 
    return i * permutation(i - 1); 
} 

}

Kann mir jemand mit weniger komplexen Logik helfen.

Answer 1

Ich denke, Ihr Problem wird viel einfacher, wenn Sie die Anagramme in alphabetischer Reihenfolge erstellen, so dass Sie sie danach nicht sortieren müssen.

Der folgende Code (von Generating all permutations of a given string) generiert alle Permutationen eines Strings. Die Reihenfolge dieser Permutationen ergibt sich aus der ursprünglichen Reihenfolge der Eingabezeichenfolge. Wenn Sie den String vorher sortieren, werden die Anagramme in sortierter Reihenfolge hinzugefügt.

Um Dubletten zu vermeiden, können Sie einfach einen Satz von Strings pflegen, den Sie bereits hinzugefügt haben. Wenn dieses Set nicht das Anagramm enthält, das Sie hinzufügen möchten, können Sie es sicher zur Liste der Anagramme hinzufügen.

Hier ist der Code für die Lösung, die ich beschrieben habe. Ich hoffe, Sie finden es einfacher als Ihre Lösung.

public class Anagrams { 

private List<String> sortedAnagrams; 
private Set<String> handledStrings; 

public static void main(String args[]) { 
    Anagrams anagrams = new Anagrams(); 
    List<String> list = anagrams.permutations(sort("AASDF")); 
    System.out.println(list.get(31)); 
} 

public List<String> permutations(String str) { 
    handledStrings = new HashSet<String>(); 
    sortedAnagrams = new ArrayList<String>(); 
    permutation("", str); 
    return sortedAnagrams; 
} 

private void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0){ 
     if(! handledStrings.contains(prefix)){ 
      //System.out.println(prefix); 
      sortedAnagrams.add(prefix); 
      handledStrings.add(prefix); 
     } 
    } 
    else { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)); 
    } 
} 

public static String sort(String str) { 
    char[] arr = str.toCharArray(); 
    Arrays.sort(arr); 
    return new String(arr); 
} 

} 

Answer 2

Wenn Sie eine „nächste Permutation“ Methode erstellen, die eine Anordnung zu seiner nächsten lexikographischer Permutation ändert, dann könnte Ihre Basis Logik sein, nur diese Methode n-1 mal in einer Schleife aufrufen.

Es gibt eine nette Beschreibung mit Code, der gefunden werden kann here. Hier ist sowohl der grundlegende Pseudocode als auch ein Beispiel in Java, das von dieser Seite übernommen wurde.

/* 
1. Find largest index i such that array[i − 1] < array[i]. 
    (If no such i exists, then this is already the last permutation.) 
2. Find largest index j such that j ≥ i and array[j] > array[i − 1]. 
3. Swap array[j] and array[i − 1]. 
4. Reverse the suffix starting at array[i]. 
*/ 

boolean nextPermutation(char[] array) { 
    int i = array.length - 1; 
    while (i > 0 && array[i - 1] >= array[i]) i--; 
    if (i <= 0) return false; 
    int j = array.length - 1; 
    while (array[j] <= array[i - 1]) j--; 
    char temp = array[i - 1]; 
    array[i - 1] = array[j]; 
    array[j] = temp; 
    j = array.length - 1; 
    while (i < j) { 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 
    return true; 
} 

Answer 3

Ich schreibe den folgenden Code, um Ihr Problem zu lösen.

Ich nehme an, dass der angegebene String sortiert ist.

Die Permutationen (String prefix, char [] Wort Array permutations_list) Funktion erzeugt alle möglichen Permutationen der gegebenen Zeichenkette ohne Duplikate und speichert diese in einer Liste permutations_list benannt. So ist das Wort: permutations_list.get (Index -1) ist die gewünschte Ausgabe.

Angenommen, jemand gibt uns das Wort "aab". Wir müssen dieses Problem rekursiv lösen:

Problem 1: Permutationen ("", "aab").

Das bedeutet, dass wir das Problem zu lösen haben:

Problem 2: Permutationen ("a", "ab"). String "ab" hat nur zwei Buchstaben, daher sind die möglichen Permutationen "ab" und "ba". Daher speichern wir in permutations_list die Wörter "aab" und "aba".

Problem 2 wurde gelöst. Jetzt gehen wir zurück zu Problem 1. Wir tauschen das erste "a" und das zweite "a" und wir erkennen, dass diese Buchstaben gleich sind. Also überspringen wir diesen Fall (wir vermeiden Duplikate). Als nächstes tauschen wir das erste "a" und "b". Nun hat sich das Problem 1 geändert und wir wollen das neue lösen:

Problem 3: Permutationen ("", "baa").

Der nächste Schritt besteht darin, das folgende Problem zu lösen:

Problem 4: Permutationen ("b", "AA"). String "aa" hat nur zwei gleiche Buchstaben, daher gibt es eine mögliche Permutation "aa". Daher speichern wir in permutations_list das Wort "baa"

Problem 4 wurde gelöst. Schließlich gehen wir zurück zu Problem 3 und Problem 3 wurde gelöst. Die endgültige permutationsliste enthält "aab", "aba" und "baa".

Daher gibt findAnagram ("aab", 2) das Wort "aba" zurück.

import java.util.ArrayList; 
import java.util.Arrays; 

public class AnagramProblem { 

public static void main(String args[]) { 
    System.out.println(findAnagram("aadfs",32)); 
} 

public static String findAnagram(String word, int index) { 
    ArrayList<String> permutations_list = new ArrayList<String>(); 
    permutations("",word.toCharArray(), permutations_list); 
    return permutations_list.get(index - 1); 
} 

public static void permutations(String prefix, char[] word, ArrayList<String> permutations_list) { 

    boolean duplicate = false; 

    if (word.length==2 && word[0]!=word[1]) { 
     String permutation1 = prefix + String.valueOf(word[0]) + String.valueOf(word[1]); 
     permutations_list.add(permutation1); 
     String permutation2 = prefix + String.valueOf(word[1]) + String.valueOf(word[0]); 
     permutations_list.add(permutation2); 
     return; 
    } 
    else if (word.length==2 && word[0]==word[1]) { 
     String permutation = prefix + String.valueOf(word[0]) + String.valueOf(word[1]); 
     permutations_list.add(permutation); 
     return; 
    } 

    for (int i=0; i < word.length; i++) { 
     if (!duplicate) { 
      permutations(prefix + word[0], new String(word).substring(1,word.length).toCharArray(), permutations_list); 
     } 
     if (i < word.length - 1) { 
      char temp = word[0]; 
      word[0] = word[i+1]; 
      word[i+1] = temp; 
     } 
     if (i < word.length - 1 && word[0]==word[i+1]) duplicate = true; 
     else duplicate = false; 
    } 


} 




}