I am currently working on this problem as a personal project.
Basically:
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!
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!
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);
}
}
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:
toBase
every time. It is easier and more performant to initiate from 000 and every time calculate the next number.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.
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.