Suppose I'm given the following array:

{"abc", "mno", "pqrs"}

Now I need to get all the possible combinations from the characters of elements of the array. The output for the following array is:

amp amq amr ams anp anq anr ans aop aoq aor aos bmp bmq bmr bms bnp bnq bnr bns bop boq bor bos cmp cmq cmr cms cnp cnq cnr cns cop coq cor cos

Suggest a recursive solution for the same.

Also, can we reduce the complexity anyhow rather than just looping over and over. It can be done using multiple for loops but it would be a very bad solution. Further, we don't know the number of elements in array. I anyways did it like this using the for loops.

 for(int j = 0; j < arr[0].length(); j  ){
       for(int k = 0; k < arr[1].length(); k  ){
            for(int l = 0; l < arr[2].length(); l  ){
                 System.out.print(""   arr[0].charAt(j)   arr[1].charAt(k)   arr[2].charAt(l)  " ");
                    }
                }
            }

Can someone suggest a better way?

CodePudding user response：

To implement a depth-first tree traversal (without actually building a tree in memory) one could:

• think of the input strings as layers 0..depth-1 in the tree
• think of the characters in a given input string as nodes 0..n on the corresponding layer of the tree
• track the tree traversal by remembering the path from the root to the active leaf node
  • starting with a - m - p (aka [0,0,0] - when using per-layer indices of the nodes on the path)
• update the path according to depth-first traversal rules
  • until it reaches the last leaf node c - o - s (aka [2,2,3])

While not using recursion, this solution can work with any number of input strings:

public static void main(String[ ] args) {
    String[] arr  = {"abc", "mno", "pqrs"};

    int[] path = new int[arr.length];
    do {
        System.out.println(getValue(arr, path));
    } while(traverseDepthFirst(arr, path));
}

public static char[] getValue(String[] arr, int[] path) {
    char[] c = new char[arr.length];
    for(int depth=0; depth<arr.length; depth  ) {
        c[depth] = arr[depth].charAt(path[depth]);
    }
    return c;
}

public static boolean traverseDepthFirst(String[] arr, int[] path) {
    for (int depth = arr.length - 1; depth >= 0; depth--) {
        if (path[depth] < arr[depth].length() - 1) {
            path[depth]  ;
            return true;
        } else {
            path[depth] = 0;
        }
    }
    return false;
}

CodePudding user response：

we can build the data of the question as tree :
letters from first array element are roots. every array element is a level in the tree, the letters are duplicated for each letter in prev element:

            a
    /       |       \
   m        n        o   
/ / \ \  / / \ \  / / \ \
p q r s  p q r s  p q r s 

same tree with root b, c
now to get combinations its a (relatively simple) depth-first tree search, that can be done with recursion. this algorthim supports any number of elements and letters.