Specific element permutation within an array of characters in JAVA?

Question

How can I list all uppercase/lowercase permutations for any letter specified in a character array? So, say I have an array of characters like so: ['h','e','l','l','o'] and I wanted print out possible combinations for say the letter 'l' so it would print out [hello,heLlo,heLLo,helLo].

This is what I have so far(the only problem is that I can print the permutations however I'm not able to print them inside the actual word. so my code prints [ll,lL,Ll,LL] instead of the example above.

my code:

import java.util.ArrayList;
import java.util.HashSet;

public class Main {

public static void main(String[] args) {
    //Sample Word
    String word = "Tomorrow-Today";

    //Sample Letters for permutation
    String rule_char_set = "tw";


    ArrayList<Character> test1 = lettersFound(word, rule_char_set);

    printPermutations(test1);







}

public static void printPermutations(ArrayList<Character> arrayList) {
    char[] chars = new char[arrayList.size()];
    int charIterator = 0;

    for(int i=0; i<arrayList.size(); i++){
        chars[i] = arrayList.get(i);
    }

    for (int i = 0, n = (int) Math.pow(2, chars.length); i < n; i++) {
        char[] permutation = new char[chars.length];
        for (int j =0; j < chars.length; j++) {
            permutation[j] = (isBitSet(i, j)) ? Character.toUpperCase(chars[j]) : chars[j];
        }
        System.out.println(permutation);
    }
}

public static boolean isBitSet(int n, int offset) {
    return (n >> offset & 1) != 0;
}

public static ArrayList<Character> lettersFound(String word, String rule_char_set) {

    //Convert the two parameter strings to two character arrays
    char[] wordArray = word.toLowerCase().toCharArray();
    char[] rule_char_setArray = rule_char_set.toLowerCase().toCharArray();

    //ArrayList to hold found characters;
    ArrayList<Character> found = new ArrayList<Character>();

    //Increments the found ArrayList that stores the existent values.
    int foundCounter = 0;


    for (int i = 0; i < rule_char_setArray.length; i++) {
        for (int k = 0; k < wordArray.length; k++) {
            if (rule_char_setArray[i] == wordArray[k]) {
                found.add(foundCounter, rule_char_setArray[i]);
                foundCounter++;

            }
        }
    }
    //Convert to a HashSet to get rid of duplicates
    HashSet<Character> uniqueSet = new HashSet<>(found);

    //Convert back to an ArrayList(to be returned) after filtration of duplicates.
    ArrayList<Character> filtered = new ArrayList<>(uniqueSet);

    return filtered;
}

}

Answer 1

You need to make few changes in your program. Your logic is perfect that you need to find first the characters to be changed in the given word. After finding them, find powerset of characters to print all the permutation but this will only print permuatation of the characters of rule-char-set which are present in the given word.

Few changes you need to make is that first find all the indexes of word which contains characters of rule-char-set. Then find all subsets of indexes stored in an ArrayList and then for each element of each of the subsets, make the character present on that index to uppercase letter which will give you all permutation you require.

Consider an example that word = "Hello" and rule-char-set="hl" Then here first you need to find all indexes of h and l in the String word.

So here indexes are 0,2,3. Store it in ArrayList and then find its powerset.Then for each subset ,make the character present on that index to the uppercase letter.

Word[] = {'h','e','l','l','o'}
indexes =  0 , 1 , 2 , 3 , 4


index[]= { 0 , 2 ,3}  //Store the indexes of characters which are to be changed


BITSET      |       SUBSET      |       word

000         |         -         |       hello 
001         |        {3}        |       helLo 
010         |        {2}        |       heLlo 
011         |       {2,3}       |       heLLo 
100         |        {0}        |       Hello 
101         |       {0,3}       |       HelLo 
110         |       {0,2}       |       HeLlo 
111         |      {0,2,3}      |       HeLLo 

Code :

import java.util.ArrayList;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) {
        //Sample Word
        String word = "Tomorrow-Today";

        //Sample Letters for permutation
        String rule_char_set = "tw";


        ArrayList<Integer> test1 = lettersFound(word, rule_char_set); //To store the indexes of the characters

        printPermutations(word,test1);

    }

    public static void printPermutations(String word,ArrayList<Integer> arrayList) {
        char word_array[]=word.toLowerCase().toCharArray();
        int length=word_array.length;
        int index[]=new int[arrayList.size()];

        for(int i=0; i<arrayList.size(); i++){
            index[i] = arrayList.get(i);
        }

        for (int i = 0, n = (int) Math.pow(2, index.length); i < n; i++) {
            char[] permutation = new char[length];

            System.arraycopy(word_array,0,permutation,0,length);    

            //First copy the original array and change 
            //only those character whose indexes are present in subset

            for (int j =0; j < index.length; j++) {
                permutation[index[j]] = (isBitSet(i, j)) ? Character.toUpperCase(permutation[index[j]]) : permutation[index[j]];
            }
            System.out.println(permutation);
        }
    }

    public static boolean isBitSet(int n, int offset) {
        return (n >> offset & 1) != 0;
    }

    public static ArrayList<Integer> lettersFound(String word, String rule_char_set) {

        //Convert the two parameter strings to two character arrays
        char[] wordArray = word.toLowerCase().toCharArray();
        char[] rule_char_setArray = rule_char_set.toLowerCase().toCharArray();

        //ArrayList to hold found characters;
        ArrayList<Integer> found = new ArrayList<Integer>();

        //Increments the found ArrayList that stores the existent values.
        int foundCounter = 0;


        for (int i = 0; i < rule_char_setArray.length; i++) {
            for (int k = 0; k < wordArray.length; k++) {
                if (rule_char_setArray[i] == wordArray[k]) {
                    found.add(foundCounter, k);       //Store the index of the character that matches
                    foundCounter++;

                }
            }
        }
        return found;
    }

}

Output :

tomorrow-today
Tomorrow-today
tomorrow-Today
Tomorrow-Today
tomorroW-today
TomorroW-today
tomorroW-Today
TomorroW-Today

Answer 2

Sanket Makani answer is perfect.

I may offer a more objective approach of this problem.

As an input you have a string to modify, and characters, which should be replaced with the modified case ( upper or lower ). As an output you will have all permutated strings.

I would create a structure which contains index, and possible values to change with:

class Change {
int index;
char values[];
}

We will need to make all possible combinations, so lets include field which will tell which character is currently used in to our structure, and add some methods:

class Change {
int index;
char values[];
int cur;

void reset() {cur=0;}
boolen isMax(){return cur==values.length-1;}
void next(){cur++;}
char getValue(){ return values[cur]; }
} 

We will have a list or array of these classes then, which we will put in to a separate class

class Combination {
Change changes[];

  void reset() { for (Change c: changes) c.reset();}

  boolean next() {
   for ( int i=0; i<changes.length; i++)
      if ( changes[i].isMax())
         changes[i].reset(); // next change will be taken in cycle, with "next()"
      else {changes[i].next(); return true;}

   return false; // all changes are max
  }
}

So when you initialize your "Combination" class by your input data, you may use it in cycle then.

Combination c = new Combination();
.... // initialization here 
c.reset();
do {
 ... //  update and print your string
} while ( c.next()  );

The initialization of "Combination" and using of values for updating the input string I leave after you :)

Answer 3

For the permutation case, I think recursion is the best fit in terms of readability, taking into account that maybe is not best in terms of performance.

My approach would be this:

public static void main(String[] args) {
    generateCombinations("hello", "l", "");
}

public static void generateCombinations(String text, String changingLetters, String current) {
    if (0 == text.length()) {
        System.out.println(current);
        return;
    }
    String currentLetter = text.substring(0, 1);
    if (changingLetters.contains(currentLetter)) {
        generateCombinations(text.substring(1), changingLetters, current + currentLetter.toUpperCase());
    }
    generateCombinations(text.substring(1), changingLetters, current + currentLetter);
}

The output for the main execution will be:

heLLo
heLlo
helLo
hello