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

i working on problem personal project.

basically:

• given array of elements, e.g. e = {1,2,a,b} and
• given number, k, e.g. k = 2
• i want return 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 achieved recursively using 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 e , length k.

so call: buildstringrec(new char[2], 0, 2); , get

11 12 13 21 22 23 31 32 33 

can done iteratively? have been trying wrap head around how variable lengths.

any appreciated! if need be, can post code is, changes due retrying it's useless post it.

also, not want using apache or string builder want understand concept of how it. not asking code. pseudo-code fine long explained.

thanks!

edit

i using site test out options presented me: https://ideone.com/k1wia6
feel free fork , try out!

here's iterative solution:

you can create array of integers of size k act counter recording how far through combinations, , char array store current combination.

after printing each one, move on next combination increasing 1 of counter values, , if "overflows" reaching value equal number of elements in e, reset 0 , perform carry incrementing counter in next position, checking overflows there , on. kind of odometer in car, except numbers tied values in e. once last position overflows have generated possible combinations.

i've incremented counters starting last value in array , moving downwards same output in example, isn't necessary of course. algorithm doesn't check duplicates.

you don't have store array of chars current combination, re-generate each time in loop based on counters, might less efficient. approach updates values change.

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

ideone.com demo