java - 算法 : Find anagram of given string at a given index in lexicographically sorted order

Question

需要编写一个算法来查找给定字符串在给定索引处的 Anagram，并按字典顺序排序。例如:

Consider a String: ABC then all anagrams are in sorted order: ABC ACB BAC BCA CAB CBA. So, for index 5 value is: CAB. Also, consider the case of duplicates like for AADFS anagram would be DFASA at index 32

为此，我编写了 Algo，但我认为应该有比这更简单的东西。

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);
}

谁能帮我解决不那么复杂的逻辑。

Answer 1

我写了下面的代码来解决你的问题。

我假设给定的字符串已排序。

permutations(String prefix, char[] word, ArrayList permutations_list) 函数生成给定字符串的所有可能排列，不重复并将它们存储在名为 < strong>permutations_list。因此，单词:permutations_list.get(index -1) 是所需的输出。

例如，假设有人给了我们单词“aab”。我们必须递归地解决这个问题:

问题 1:排列(“”，“aab”)。

这意味着我们必须解决问题:

问题 2:排列(“a”，“ab”)。字符串“ab”只有两个字母，因此可能的排列是“ab”和“ba”。因此，我们在 permutations_list 中存储单词“aab”和“aba”。

问题2已经解决。现在我们回到问题1。我们交换第一个“a”和第二个“a”，我们意识到这些字母是相同的。所以我们跳过这种情况(我们避免重复)。接下来，我们交换第一个“a”和“b”。现在，问题 1 已经改变，我们要解决新的问题:

问题 3:排列 ("","baa")。

下一步是解决以下问题:

问题 4:排列(“b”，“aa”)。字符串“aa”只有两个相同的字母，因此存在一种可能的排列“aa”。因此，我们在 permutations_list 中存储单词“baa”

问题4已经解决。最后，我们回到问题3，问题3已经解决了。最终的 permutations_list 包含“aab”、“aba”和“baa”。

因此，findAnagram("aab", 2) 返回单词“aba”。

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;
    }


 }




}