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

Question

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

Mostly:

• Given an array of elements, for example. E = {1,2, a, b} and
• Given a number, K, for example. K = 2
• I want to return all Combinations E of size K (E select K)
• eg. {{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 got

 11 12 13 21 22 23 31 32 33 

Can this be done iteratively? I am trying to wrap my head in the way I will do this with variable lengths.

Any help would be appreciated! If necessary, I can publish my code as it is, but it changes so often because of my attempt to repeat that it is almost useless as soon as I publish it.

Also, I don't want to do this with Apache or String Builder, as I want to understand the CONCEPT on how to do this. I'm not just asking for a code. Pseudocode is just fine if it is clearly explained.

Thanks!

EDIT

I use this site to check all the options presented to me: https://ideone.com/k1WIa6
Feel free to develop it and try it!

Answer 1

Here's another iterative solution:

You can create an array of integers of size K to act as a counter, recording how much you went through the combinations, and a char array to store the current combination.

After printing each of them, proceed to the next combination, increasing one of the counter values, and if it "overflows", reaching a value equal to the number of elements in E, then reset it is zero and performs the transfer, increasing the counter in the next position, checking for overflows there and so on. It looks like an odometer in a car, except that the numbers are tied to the values ​​in E. After the last position is full, you have created all possible combinations.

I increased the counters, starting from the last value in the array and moving down to get the same result as in your example, but this is not necessary, of course. The algorithm does not check for duplicates.

You do not need to store an array of characters with the current combination, you can simply regenerate it every time in a for loop based on counters, but this may be less efficient. This approach only updates values ​​that change.

 public static void buildStrings(char[] root, int length) { // allocate an int array to hold the counts: int[] pos = new int[length]; // allocate a char array to hold the current combination: char[] combo = new char[length]; // initialize to the first value: for(int i = 0; i < length; i++) combo[i] = root[0]; while(true) { // output the current combination: System.out.println(String.valueOf(combo)); // move on to the next combination: int place = length - 1; while(place >= 0) { if(++pos[place] == root.length) { // overflow, reset to zero pos[place] = 0; combo[place] = root[0]; place--; // and carry across to the next value } else { // no overflow, just set the char value and we're done combo[place] = root[pos[place]]; break; } } if(place < 0) break; // overflowed the last position, no more combinations } } 

demonstration ideone.com

Answer 2

Recursive solution

For me, it looks like a recursive solution. You can replace cloning your path array with stacks 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

Suppose for some reason you need to do iteratively.
I am sure there is a better solution. However, this is the best I could do.

You can rephrase your task differently:

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

Suppose you have an array of length 3: {'a', 1, 'z'} .
Your desired answer would be:

 aaa aa-1 aaz a-1-a a-1-1 a-1-z aza az-1 azz 1-aa 1-a-1 1-az 

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, the consecutive numbers in the base are 3: 000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202 .

Keep in mind the formula for calculating them: base ^ length . In our case, length == base . So this is base ^ base .

Now our task becomes simpler:

 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 may be some optimizations:

• No need to count toBase every time. It is easier and more efficient to initiate from 000 and each time calculate the next number.
• You can change the Pow function to use the fast exponentiation by squaring algorithm, etc.

This is just an example explaining the approach.

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

Working sample

Here is the DotNetFiddle working demo .

Just change the values ​​of the pool array to get the results. Here and in all the examples above, I used C #. It can be easily converted to C ++ :)

As for me, it works great for lengths up to 7 (about 1 - 1.5 seconds).
Of course, you will need to remove console output in order to get such results. The console exit is very slow .

Answer 3

A simple iterative solution would be

• create an array to store the index for each character for the desired output length
• Then iterate over the indices and print each character from the pool corresponding to the indices
• Then add the last index of the index array
• if the last index is equal to the length of the pool
  • set it to zero
  • increases the previous index
  • repeat with the previous index until you reach the beginning of the array, or the index is not equal to the length of the pool

The following is a sample Java code in Java

 char[] pool = new char[]{'1', '2', '3'}; public void buildStrings(int length){ int[] indexes = new int[length]; // In Java all values in new array are set to zero by default // in other languages you may have to loop through and set them. int pMax = pool.length; // stored to speed calculation while (indexes[0] < pMax){ //if the first index is bigger then pMax we are done // print the current permutation for (int i = 0; i < length; i++){ System.out.print(pool[indexes[i]]);//print each character } System.out.println(); //print end of line // increment indexes indexes[length-1]++; // increment the last index for (int i = length-1; indexes[i] == pMax && i > 0; i--){ // if increment overflows indexes[i-1]++; // increment previous index indexes[i]=0; // set current index to zero } } } 

Answer 4

Iterative solution

Here is an algorithm that I developed in C / C ++, with iterative functions and with constant spatial complexity

It processes the indexes of the C array, so it can be used for any data type, here is an array of characters (a C ++ string), which can be a string of numbers

Function 1: generate all possible combinations

 // str: string of characters or digits void GenerateAll(string str, int k) { int n = str.length(); // initialization of the first subset containing k elements int *sub_tab = new int[k]; for(int j(0); j<k; ++j) { sub_tab[j] = j; } do { // Convert combination to string char *sub_str = new char[k]; for(int j(0); j<k; ++j) { sub_str[j] = str[sub_tab[j]]; } // Print combinations of each set Combinations(sub_str); // get next sub string } while (AddOne(sub_tab, k-1, n) == true); delete [] sub_tab; } 

Function 2: Create All Combinations For Each Set

 void Combinations(string str) { int n = str.length(); // Compute all factorials from 0 to n unsigned long int * factorials = new unsigned long int[n+1]; factorials[0] = 1; for(int i = 1; i<=n; ++i) factorials[i] = factorials[i-1] * i; char *tab = new char[n]; // Initialization with the first combination 0123...n-1 for(int i(0); i<n; ++i) { tab[i] = i; cout << str[i] << " "; } cout << endl; for(unsigned long int i(1); i < factorials[n]; ++i) { for (int j(0); j < n; ++j) { if(i % factorials[nj-1] == 0) { // increment tab[j] (or find the next available) SetNextAvailable(tab, j, n); } } for (int j(0); j < n; ++j) { cout << str[tab[j]] << " "; } cout << endl; } delete [] factorials; } 

Function SetNextAvailable ()

 void SetNextAvailable(char *tab, int j, int n) { bool finished; do { finished = true; ++(*(tab+j)); if (*(tab+j) == n) *(tab+j) = 0; for (int i(0); i < j; ++i) { if ( *(tab+i) == *(tab+j) ) { finished = false; break; } } } while(finished == false); } 

Function addone ()

 bool AddOne(int *tab, int k, int n) { int i; for(i=k; i>=0; --i) { if(((++tab[i]) + (ki)) != n) break; } if(i == -1) return false; else { for(int j=i+1; j<=k; ++j) { tab[j] = tab[j-1] + 1; } return true; } }