Generating all possible combinations of a string using iteration

Question

I am generating all possible combinations from a string concatenated. I have a \$O(n*2^n)\$ solution.

public static String[] combinations(String[] array) {
    String[] res = new String[(1 << array.length) - 1];
    int k = 0;
    int x = 1;
    for (int i = array.length - 1; i >= 0; --i) {
        res[k++] = array[i];
        for (int j = 1; j < x; ++j) {
            res[k++] = array[i] + res[j - 1];
        }
        x *= 2;
    }
    return res;
}

How can this be improved?

Answer 1

Minor changes

As @coderodde already stated, there is not much to improve, nonetheless a few minor things:

You can reduce the scope of the variables x (which has always the same value as k prior entering the inner loop) and k to the inner/outer loop.
for (int i = array.length - 1; i >= 0; --i) can be written as for (int i = array.length; --i >= 0;).
Your inner loop starts at j = 1 but only uses j - 1, you can start the loop at 0 to avoid the subtraction.

Depending on how nulls should be handled, you could use res[k++] = array[i].toString() to throw a NPE if null elements are present. If nulls are permitted, I would prefer that the string "null" is added to the resulting array rather than a null reference.

You could start k and j at -1 and use the (in theory) more efficient preincrement operator instead of the postincrement operator.

Possible implementation (not using preincrement for kand j as I think it makes the code more difficult to read):

public static String[] combinations(String[] array) {
    String[] res = new String[-1 >>> -array.length];
    for (int i = array.length, k = 0; --i >= 0;) {
        String s = res[k] = array[i].toString();
        for (int j = 0, x = k++; j < x;)
            res[k++] = s + res[j++];
    }
    return res;
}

Alternative implementation

Your current implementation supports arrays with a maximum length of 30, you could provide a method #combination(String[] array, long index) to support arrays with up to 64 elements (or a larger datatype than long to support way larger input arrays).

public static String combination(String[] array, long index) {
    // Could iterate twice to determine length (and coder) first
    // to avoid resizing buffer (and could share the resulting
    // byte array), kept this way for simplicity.
    if (array.length > 64 || index == -1 || index + 1 >>> array.length != 0)
        throw new IllegalArgumentException();
    index = index + 1 << -array.length;
    StringBuilder sb = new StringBuilder();
    for (int i = -1; index != 0;) {
        int nlz = numberOfLeadingZeros(index);
        sb.append(array[i += nlz + 1]);
        index = index << nlz << 1;
    }
    return sb.toString();
}

Answer 2

Frankly, no, your code is very nice and I do not see any opportunity for improvement. The only "improvement" is replacing x *= 2 with x <<= 1.

Answer 3

Memory usage

            res[k++] = array[i] + res[j - 1];

This means that every single string is going to be backed by a different char[]. It's trickier, but if you can arrange that where one output string is a substring of another that it should be generated with a call to String.substring(...) then they will share their backing arrays.

Assuming that all of the input strings are the same length (and that it's long enough for the overhead of the pointers to be negligible), this gives a significant reduction in memory use.

number of strings     memory use vs naïve approach
3                     5/12       ~ 0.417
4                     12/32      = 0.375
5                     28/80      = 0.35
6                     64/192     ~ 0.333
7                     144/448    ~ 0.321
8                     320/1024   ~ 0.313
9                     704/2304   ~ 0.306
10                    1536/5120  = 0.3