Iteratively find all combinations of size k of an array of characters (N choose K)

Question

I am currently working on this problem as a personal project.

Basically:

• Given an array of elements, e.g. E = {1,2,a,b} and
• Given a number, K, e.g. K = 2
• I want to return all Combinations of E of size K (E choose K)
• E.g. {{1,1}, {1,2}, {1,a}, {1,b}, {2,1}, ... , {b,1}, {b,2}, {b,a}, {b,b}}

I have already achieved this recursively using the following function:

char[] pool = new char[]{'1', '2', '3'};

public void buildStringRec(char[] root, int pos, int length){
    for(char c : pool){
        char[] newRoot = root.clone();
        newRoot[pos] = c;
        if(pos+1 < length){
            buildStringRec(newRoot, pos+1, length);
        } else{
            System.out.println(String.valueOf(root));
        }
    }
}

Where pool is E and length is K.

So we would call: buildStringRec(new char[2], 0, 2); and get

11
12
13
21
22
23
31
32
33

Can this be done iteratively? I have been trying to wrap my head around how I would do this with variable lengths.

Any help would be appreciated! If need be, I can post my code as it is, but it changes so frequently due to my retrying that it's almost useless as soon as I post it.

Also, I do not want to do this using Apache or String Builder as I want to understand the CONCEPT of how to do it. I am not simply asking for code. Pseudo-code is just fine as long as it is clearly explained.

Thanks!

EDIT

I am using this site to test out all options presented to me: https://ideone.com/k1WIa6
Feel free to fork it and try it out!

Answer 1

Recursive solution

As for me, it looks like recursive solution is the best option here.
You can replace cloning your path array with stack to improve performance:

char[] pool = new char[]{'1', '2', '3'};
Stack<int> stack = new Stack<int>();

// Actually, resulting length should be the same length as pool array
int length = pool.length;

public void buildStringRec(int pos)
{
    if (length == pos + 1) 
    {
        System.out.println(String.valueOf(root));
        return;
    }

    for(char c : pool){
        stack.Push(c);
        buildStringRec(pos + 1);
        stack.Pop(c);
    }
}

Iterative solution

Let's suppose that, for some reason, you need to do this iteratively.
I am sure that there is a better solution. However, that's the best I could make.

You can rephrase your task to another one:

How to output ALL numbers in base N of length N.

Let's suppose you have an array of length 3: {'a', 1, 'z'}.
Your desirable answer will be:

a-a-a    a-a-1    a-a-z
a-1-a    a-1-1    a-1-z
a-z-a    a-z-1    a-z-z
1-a-a    1-a-1    1-a-z

Now, let's look at the indices of these values:

0-0-0    0-0-1    0-0-2
0-1-0    0-1-1    0-1-2
0-2-0    0-2-1    0-2-2 
2-0-0    2-0-1    2-0-2

Actually, that's a consecutive numbers in base 3: 000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202.

Keep in mind the formula of their count: base ^ length. In our case, length == base. Thus, it is base ^ base.

Now, our task is becoming easier:

int[] toBase(long bs, long value)
{ 
    int[] result = new int[bs];
    for (long i = bs - 1; i >= 0; i--)
    {
        result[i] = (int)(value % bs);
        value = value / bs;
    }
    return result;
}

long Pow(long a, long b)
{
    long result = 1;
    for (int i = 0; i < b; i++) result *= a;
    return result;
}

char[] pool = new char[] {'a', 'b', 'c'};

void outputAll()
{
    long n = pool.Length;
    for (long i = 0; i < Pow(n, n); i++)
    {
        int[] indices = toBase(n, i);
        for (int j = 0; j < n; j++)
            Console.Write("{0} ", pool[indices[j]]);
        Console.WriteLine();
    }
}

Of course, there could be some optimizations:

• There is no need to calculate toBase every time. It is easier and more performant to initiate from 000 and every time calculate the next number.
• You can change Pow function to use fast exponentiation by squaring algorithm etc.

This is just an example provided to explain an approach.

Keep in mind that array of length 3 will have only 27 such combinations. However, an array of length 7 will have 823543. It grows exponentially.

The working sample

Here is a DotNetFiddle working Demo.

Just change pool array values in order to get your results. In here and in all examples above I have used C#. It can be easily converted to C++ :)

As for me, it works great for length up to 7 (about 1 - 1.5 seconds).
Of course, you will need to remove console output to get such results. Console output works really slow.