Generate all possible string combinations by replacing the hidden “#” number sign

Question

My task is to generates all possible combinations of that rows without the hidden # number sign. The input is XOXX#OO#XO and here is the example of what the output should be:

XOXXOOOOXO 
XOXXOOOXXO 
XOXXXOOOXO 
XOXXXOOXXO

I am only allowed to solve this solution iteratively and I am not sure how to fix this and have been working on this code for a week now.

Here is my code:

import java.lang.Math;

public class help {
    public static void main(String[] args) {
        String str = new String("XOXX#OO#XO");
        UnHide(str);
    }

    public static void UnHide(String str) {
        //converting string to char 
        char[] chArr = str.toCharArray();
        //finding all combinations for XO 
        char[] xo = new char[]{'X', 'O'};

        int count = 0;
        char perm = 0;
        String s = "";

        //finding amount of times '#' appears in string
        for (int i = 0; i < str.length(); i++) {
            if (chArr[i] == '#')
                count++;
        }

        int[] combo = new int[count];
        int pMax = xo.length;

        while (combo[0] < pMax) {
            // print the current permutation
            for (int k = 0; k < count; k++) {
                //print each character
                //System.out.print(xo[combo[i]]);
                perm = xo[combo[k]];
                s = String.valueOf(perm);

                char[] xoArr = s.toCharArray();
                String strChar = new String(xoArr);
                //substituting '#' to XO combo
                for (int i = 0; i < chArr.length; i++) {
                    for (int j = 0; j < s.length(); j++) {
                        if (chArr[i] == '#') {
                            chArr[i] = xoArr[j];
                            strChar = String.copyValueOf(chArr);
                            i++;
                        }
                    }
                    i++;
                    if (i == chArr.length - 1) {
                        System.out.println(strChar);
                        i = 0;
                    }
                }
            }

            System.out.println(); //print end of line

            // increment combo
            combo[count - 1]++; // increment the last index
            //// if increment overflows
            for (int i = count - 1; combo[i] == pMax && i > 0; i--) {
                combo[i - 1]++;  // increment previous index
                combo[i] = 0;   // set current index to zero  
            }
        }
    }
}

Shimmery

Answer 1

Since your input has 2 #'s, there are 2ⁿ = 4 permutations.

If you count from 0 to 3, and look at the numbers in binary, you get 00, 01, 10, and 11, so if you use that, inserting O for 0 and X for 1, you can do this using simple loops.

public static void unHide(String str) {
    int count = 0;
    for (int i = 0; i < str.length(); i++)
        if (str.charAt(i) == '#')
            count++;
    if (count > 30)
        throw new IllegalArgumentException("Too many #'s found. " + count + " > 30");
    char[] buf = str.toCharArray();
    for (int permutation = 0, end = 1 << count; permutation < end; permutation++) {
        for (int i = buf.length - 1, bit = 0; i >= 0; i--)
            if (str.charAt(i) == '#')
                buf[i] = "OX".charAt(permutation >>> bit++ & 1);
        System.out.println(buf);
    }
}

Test

unHide("XOXX#OO#XO");

Output

XOXXOOOOXO
XOXXOOOXXO
XOXXXOOOXO
XOXXXOOXXO

Fetter

I’d save the positions of the # in an array during the first loop, that will simplify the second’s inner loop. – Pivoting

Answer 2

You can iteratively generate all possible combinations of strings using streams as follows:

public static String[] unHide(String str) {
    // an array of substrings around a 'number sign'
    String[] arr = str.split("#", -1);
    // an array of possible combinations
    return IntStream
            // iterate over array indices
            .range(0, arr.length)
            // append each substring with possible
            // combinations, except the last one
            // return Stream<String[]>
            .mapToObj(i -> i < arr.length - 1 ?
                    new String[]{arr[i] + "O", arr[i] + "X"} :
                    new String[]{arr[i]})
            // reduce stream of arrays to a single array
            // by sequentially multiplying array pairs
            .reduce((arr1, arr2) -> Arrays.stream(arr1)
                    .flatMap(str1 -> Arrays.stream(arr2)
                            .map(str2 -> str1 + str2))
                    .toArray(String[]::new))
            .orElse(null);
}

// output to the markdown table
public static void main(String[] args) {
    String[] tests = {"XOXX#OOXO", "XOXX#OO#XO", "#XOXX#OOXO#", "XO#XX#OO#XO"};
    String header = String.join("</pre> | <pre>", tests);
    String matrices = Arrays.stream(tests)
            .map(test -> unHide(test))
            .map(arr -> String.join("<br>", arr))
            .collect(Collectors.joining("</pre> | <pre>"));

    System.out.println("| <pre>" + header + "</pre> |");
    System.out.println("|---|---|---|---|");
    System.out.println("| <pre>" + matrices + "</pre> |");
}

XOXX#OOXO	XOXX#OO#XO	#XOXX#OOXO#	XO#XX#OO#XO
XOXXOOOXO XOXXXOOXO	XOXXOOOOXO XOXXOOOXXO XOXXXOOOXO XOXXXOOXXO	OXOXXOOOXOO OXOXXOOOXOX OXOXXXOOXOO OXOXXXOOXOX XXOXXOOOXOO XXOXXOOOXOX XXOXXXOOXOO XXOXXXOOXOX	XOOXXOOOOXO XOOXXOOOXXO XOOXXXOOOXO XOOXXXOOXXO XOXXXOOOOXO XOXXXOOOXXO XOXXXXOOOXO XOXXXXOOXXO

Wuhsien

Answer 3

The process would probably be best to calculate the number of permutations, then loop through each to define what combination of characters to use.

For that, we'll have to divide the permutation number by some value related to the index of the character we're replacing, which will serve as the index of the character to swap it to.

public static void test(String word) {
    // Should be defined in class (outside method)
    String[] replaceChars = {"O", "X"};
    char replCharacter = '#';

    String temp;
    int charIndex;
    int numReplaceable = 0;

    // Count the number of chars to replace
    for (char c : word.toCharArray())
        if (c == replCharacter)
            numReplaceable++;

    int totalPermutations = (int) Math.pow(replaceChars.length, numReplaceable);

    // For all permutations:
    for (int permNum = 0; permNum < totalPermutations; permNum++) {
        temp = word;
        // For each replacement character in the word:
        for (int n = 0; n < numReplaceable; n++) {
            // Calculate the character to swap the nth replacement char to
            charIndex = permNum / (int) (Math.pow(replaceChars.length, n))
                    % replaceChars.length;
            temp = temp.replaceFirst(
                    replCharacter + "", replaceChars[charIndex]);
        }
        System.out.println(temp);
    }
}

Which can produces:

java Test "#TEST#"
OTESTO
XTESTO
OTESTX
XTESTX

This can also be used with any number of characters, just add more to replaceChars.

Lowermost