CareerCup

Here is my code for the odoMeter. You only need to map the odoValue to the cartesian product you want.

int odoNext(int *pOdoMax, int len, int* pOdoValue)
{
        int inc;
        if(NULL==pOdoMax || NULL==pOdoValue || 1>len)
                return -1;
        len=len-1;
        inc=1;
        for(;len>=0 && inc;len--)
        {
                pOdoValue[len]=(pOdoValue[len]+inc)%pOdoMax[len];
                inc=!pOdoValue[len];
        }
        return (inc&&(len<0));
}

void odoInit(int *pOdoValue, int len)
{
        memset((void*)pOdoValue, 0, sizeof(int)*len);
}

void odoPrint(int* pOdoValue, int len)
{
     int count;
     printf("Odo Print :\n");
     for(count=0;count<len;count++)
        printf("%d ", pOdoValue[count]);
     printf("\n");
}

Still Use Odometer

import java.util.ArrayList;
import java.util.List;

public class Cartesian {

	public static void generateCartesian(String[] strs) {
		int K = strs.length;

		int[] sizes = new int[K];
		for (int i = 0; i < sizes.length; i++) {
			sizes[i] = strs[i].length();
		}

		List<Integer> odometer = new ArrayList<Integer>();
		for (int index = 0; index < K; index++) {
			odometer.add(index, 0);
		}

		List<Integer> max_indexes = new ArrayList<Integer>();
		for (int index = 0; index < K; index++) {
			max_indexes.add(index, sizes[index]);
		}

		while (true) {
			// output based on current odometer
			for (int index = 0; index < odometer.size(); index++) {
				int pos = odometer.get(index);
				System.out.print(strs[index].charAt(pos));
			}
			System.out.println();
			// advance odometer
			if (!advance_odometer(odometer, max_indexes)) {
				break;
			}
		}
	}

	private static boolean advance_odometer(List<Integer> odometer,
			List<Integer> max_indexes) {
		int i = odometer.size() - 1;
		while (i >= 0) {
			odometer.set(i, odometer.get(i) + 1);
			if (odometer.get(i) < max_indexes.get(i)) {
				return true;
			} else {
				// roll over to next index
				odometer.set(i, 0);
				i = i - 1;
				if (i < 0) {
					return false;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		String[] strs = { "ABCD", "123", "ZX" };
		generateCartesian(strs);
	}

}

//*a[] = k diff arrays.
char * cart(char *a[], int start, int end)
{
int mid;
if(start==end)
{
return a[start];
}
else
{ mid=(start+end)/2;
char *a1=cart(a, start, mid);
char *b1=cart(a, mid+1, end);
return(product(a1,b1));
}
}
char * product(char *a1, char *b1)
{
// return cartesian product of a1,b1 in a char *product;
}

Python recursive solution:

def cartesian(lst):
    if not lst: return
    def f(i, prefix):
        if i == len(lst) - 1:
            for c in lst[i]:
                yield prefix + c
        else:
            for c in lst[i]:
                for s in f(i+1, prefix+c):
                    yield s

    for s in f(0, ''):
        yield s

strings = [
    'abcd',
    '123',
    'XY'
]
for s in cartesian(strings):
    print s

Python Odometer Solution:

Using an odometer-based approach is arguably overkill for this problem, but it's a good technique to have in your bag of tricks. An odometer function yields the cartesian product of a bunch of integer ranges. It comes up in other problems. For example, suppose you have a prime factorization for a number, and you want to generate all the composite factors of the number. You can use an odometer to generate all the combinations of exponents.

def test():
    strings = [
        'abcd',
        '123',
        'XY'
    ]
    for s in cartesian(strings):
        print s

def cartesian(strings):
    max_indexes = map(len, strings)
    for indexes in odometer(max_indexes):
        letters = [strings[i][j] for i, j in enumerate(indexes)]
        yield ''.join(letters)

def odometer(max_indexes):
    odometer = [0] * len(max_indexes)
    def advance_odometer():
        i = len(odometer) - 1
        while i >= 0:
            odometer[i] += 1
            if odometer[i] < max_indexes[i]:
                return True
            else:
                # roll over to next index
                odometer[i] = 0
                i -= 1
                if i < 0:
                    return False
    while True:
        yield odometer
        if not advance_odometer():
            break
test()

I think. If there are k arrays of different lengths (l1,l2...lk) then best case complexcity can not be less than O(l1*l2...lk), because we need to generate all at least such results. lets say if we have 3 char arrays of size 2,3,4 then result should contain 2*3*4=24 strings. so here we can use bottom to top approach. algo should be:
1- mutliply k & k-1 char arrays
2- multiply results of step 1 to k-2
3-and so on till k=1.

As per our example. k= 3, l1= 2, l2=3;l3 =4
l3(3)*l(4)
\ /
l(12)*l(2)
\ /
l(24)