zennon zennon - 1 month ago 12
Java Question

Java, combination algorithm with arrays

I am trying to implement an algorithm to calculate all combinations of an Array where one character is replaced by '*' without changing the order of the Arrays entries.

For example the following Array with two entries:

{"A", "B"}

Should reproduce this Output:

[A, B]
[*, B]
[A, *]
[*, *]


My current code is:

public class TestCombination {

public static void combinations(List<String[]> values, String[] attr, String all, int iteration) {
String[] val = new String[attr.length];
for (int i = 0; i < attr.length; i++) {
val[i] = attr[i];
}
if (iteration < attr.length) {
val[iteration] = all;
}

values.add(val);
iteration = iteration + 1;

if (Math.pow(attr.length, 2) != iteration) {
combinations(values, attr, all, iteration);
}
}

public static void main() {
String[] values = new String[] {"A", "B"};
List<String[]> resultValues = new ArrayList<String[]>();
combinations(resultValues, values, "*", 0);

for (String[] res : resultValues) {
System.out.println(Arrays.deepToString(res));
}
}

}


The Output i get is:

[*, B]
[A, *]
[A, B]
[A, B]


This is especially because of this not correct code:

if (iteration < attr.length) {
val[iteration] = all;
}


I do not have any idea, how the next possible index can be calculated to replace the Array value at that index by '*'.

Can you give me please some hints on that?

Answer

One simple approach is to use a bit mask of length n. Iterate all n-digit binary numbers, and then for each of the n positions do the following:

  • If position i has one, output an asterisk *
  • If position i has zero, output the original value.

This will cover all combinations.

String[] a = new String[] {"A", "B", "C"};
for (int mask = 0 ; mask != 1<<a.length ; mask++) {
    for (int i = 0 ; i != a.length ; i++) {
        if ((mask & 1<<i) != 0) {
            System.out.print("* ");
        } else {
            System.out.print(a[i]+" ");
        }
    }
    System.out.println();
}

Demo.

Comments