Algo: Find anagram of given string at a given index in lexicographically sorted order

Question

Need to write an Algo to find Anagram of given string at a given index in lexicographically sorted order. For example:

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

To do this I have written Algo but I think there should be something less complex than this.

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

}

Can someone help me with less complex logic.

Answer 1

I write the following code to solve your problem.

I assume that the given String is sorted.

The permutations(String prefix, char[] word, ArrayList permutations_list) function generates all possible permutations of the given string without duplicates and store them in a list named permutations_list. Thus, the word: permutations_list.get(index -1) is the desired output.

For example, assume that someone gives us the word "aab". We have to solve this problem recursively:

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

That means that we have to solve the problem:

Problem 2: permutations("a","ab"). String "ab" has only two letters, therefore the possible permutations are "ab" and "ba". Hence, we store in permutations_list the words "aab" and "aba".

Problem 2 has been solved. Now we go back to problem 1. We swap the first "a" and the second "a" and we realize that these letters are the same. So we skip this case(we avoid duplicates). Next, we swap the first "a" and "b". Now, the problem 1 has changed and we want to solve the new one:

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

The next step is to solve the following problem:

Problem 4: permutations("b","aa"). String "aa" has only two same letters, therefore there is one possible permutation "aa". Hence, we store in permutations_list the word "baa"

Problem 4 has been solved. Finally, we go back to problem 3 and problem 3 has been solved. The final permutations_list contains "aab", "aba" and "baa".

Hence, findAnagram("aab", 2) returns the word "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;
    }


 }




}

Answer 2

If you create a "next permutation" method which alters an array to its next lexicographical permutation, then your base logic could be to just invoke that method n-1 times in a loop.

There's a nice description with code that can be found here. Here's both the basic pseudocode and an example in Java adapted from that page.

/*
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

I think your problem will become a lot simpler if you considerate generating the anagrams in alphabetical order, so you don't have to sort them afterwards.

The following code (from Generating all permutations of a given string) generates all permutations of a String. The order of these permutations are given by the initial order of the input String. If you sort the String beforehand, the anagrams will thus be added in sorted order.

to prevent duplicates, you can simply maintain a Set of Strings you have already added. If this Set does not contain the anagram you're about to add, then you can safely add it to the list of anagrams.

Here is the code for the solution i described. I hope you find it to be simpler than your solution.

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

}