import java.util.*;

public class Main{
	private long totalWordsIter=0, totalWordsRec=0, totalWordsRecStack=0;
	private long iterStart, iterEnd, recStart, recEnd, recStackStart, recStackEnd;
	private char[] pool;
	private int minLength, maxLength;
	
	/* From http://stackoverflow.com/a/31177163/5072095 */
	public void buildStringIter(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] = pool[0];
	
	    while(true)
	    {
	        // output the current combination:
	        System.out.println(String.valueOf(combo));
	        totalWordsIter++;
	
	        // move on to the next combination:
	        int place = length - 1;
	        while(place >= 0)
	        {
	            if(++pos[place] == pool.length)
	            {
	                // overflow, reset to zero
	                pos[place] = 0;
	                combo[place] = pool[0];
	                place--; // and carry across to the next value
	            }
	            else
	            {
	                // no overflow, just set the char value and we're done
	                combo[place] = pool[pos[place]];
	                break;
	            }
	        }
	        if(place < 0)
	            break;  // overflowed the last position, no more combinations
	    }
	}
	
	public void buildStringRecStack(Stack<Character> stack, int pos, int length){
		if (length == pos + 1){
			totalWordsRecStack++;
		    System.out.println(String.valueOf(stack.toString()));
		    return;
		}
		for(char c : pool){
		    stack.push(c);
		    buildStringRecStack(stack, pos + 1, length);
		    stack.pop();
		}
	}
	
	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{
	            totalWordsRec++;
				System.out.println(String.valueOf(newRoot));		
	        }
	    }
	}
	
	private void performIteratively(){
		System.out.println("\nPerforming Iteratively...");
		iterStart = System.currentTimeMillis();
		for(int length = minLength; length <= maxLength; length++){
			buildStringIter(length);
		}
		iterEnd = System.currentTimeMillis();
	}
	
	private void performRecursively(){
		System.out.println("\nPerforming Recursively without the Stack...");
	    recStart = System.currentTimeMillis();
	    for(int length = minLength; length <= maxLength; length++){
	        for(char c : pool){
	            if(length == 1){
	                totalWordsRec++;
	                System.out.println(c);
	            }else{
	                char[] root = new char[length];
	                root[0] = c;
	                buildStringRec(root, 1, length);
	            }
	        }
	    }
	    recEnd = System.currentTimeMillis();
	}
	
	private void performRecursivelyWithStack(){
		System.out.println("\nPerforming Recursively using the Stack Method...");
	    recStackStart = System.currentTimeMillis();
	    for(int length = minLength; length <= maxLength; length++){
	        Stack<Character> stack = new Stack<>();
	        buildStringRecStack(stack, 0, length+1);
	    }
	    recStackEnd = System.currentTimeMillis();
	}
	
	public Main(){
		pool = "0123456789".toCharArray();
		minLength = 1;
		maxLength = 3;
		String charCase = "UPPER";
		String set = "NUMERICAL";
		
		
	    System.out.println("Creating a list of words between lengths " + minLength + " and " + maxLength
	        + " using the " + set + " set of characters and using the " + charCase + " case.");
	
	    System.out.println("There will be " + calculateSize(pool, maxLength, minLength) + " words when we are done...");
	
	    performIteratively();
	    performRecursively();
	    performRecursivelyWithStack();
	
	    System.out.println("Iteratively, we created: " + totalWordsIter + " words.");
	    System.out.println("Iteratively, it took: " + (iterEnd-iterStart) + "ms");
	    System.out.println("Recursively, we created: " + totalWordsRec + " words.");
	    System.out.println("Recursively, it took: " + (recEnd - recStart) + "ms");
	    System.out.println("Recursively with stack, we created: " + totalWordsRecStack + " words.");
	    System.out.println("Recursively with stack, it took: " + (recStackEnd - recStackStart) + "ms");
	}
	
	public long calculateSize(char[] pool, int max, int min){
		long total = 0;
	    for(int i = min; i <= max; i++) {
	        if(i == 1){
	            total += pool.length;
	        }else{
	            total += Math.pow(pool.length, i);
	        }
	    }
	    return total;
	}
	
	public static void main(String[] args){
		new Main();
	}
}