CareerCup

/* 
Observe the problem of cartesian product from arbitrary no.
of lists. Suppose the lists are : L1, L2, L3, ... Ln
with sizes s1, s2, s3, .. sn
Let the element in the i'th position of k'th list is Lk[i].
The configuration of such indices at any point is, then :
0 0 0 0 ... 0 // n times for the first tuple
0 0 0 0 ....1 // for the 2nd tuple...
...
0 0 0 0 ....(sn-1) // for the sn Tuple.
After than, the first column will be reset, and carry will be generated, 
so that the next tuple will be:
0 0 0 0 ...1 0  // for the ( sn + 1) Tuple.

Thus, generating next tuple's index is generating the carry, if any, 
and resetting the indices from the index which generated the carry to the end, 
and incrementing the index of the left one. This again can generate carry, 
so it is a ripple effect from rightmost side to the left most side.
Thus, hasNext() is always possible, till the leftmost list is not exhausted by carry.
next() is the tricky one, where we need to define the carry and the ripple from right to left.
When there is no carry, we can stop having the ripple.
*/
def inc_iterator( some_list, cur_iterator ){
  if ( cur_iterator.hasNext ){
    return [ false , cur_iterator ]
  } else {
    return [ true, some_list.iterator ]
  }
}
def cartesian ( list_of_list ){
  iterators = list ( list_of_list ) as { $.o.iterator } // get the iterators 
  my_tuple = select( iterators ) where { $.o.hasNext() } as  { $.o.next() }
  if ( size( my_tuple) < size(list_of_list) ) return [] // empty tuple  
  println( my_tuple )
  carry = false 
  while ( !carry ){
    for ( i : [ size(list_of_list) - 1 : -1 ] ){
       #(carry,iter) = inc_iterator( list_of_list[i], iterators[i] )
       if ( i == 0 && carry ) { return } // because now I am having carry to the left
       iterators[i] = iter 
       my_tuple[i] = iter.next 
       break ( i != 0 && !carry ) 
    }
    println( my_tuple ) 
  }
}
cartesian ( [ ['a','b', 'c'] , ['p', 'q' ], ['r','s' ] ] )

Evaluate the product of the list and keep popping it off until the list is not empty.
Solution in Python:

class CartesianIterator:
  def __init__(self, sets):
    self.result = [[]]
    for pool in sets:
      self.result = [x + [y] for x in self.result for y in pool]

  def hasNext(self):
    return len(self.result) != 0

  def next(self):
    return self.result.pop(0)

Test Code:

Test code
# Example 1
c = CartesianIterator([[1,2,3], [4,5]])
while c.hasNext():
  print(c.next(), end=', ')
print()

# Example 2
c = CartesianIterator([['a','b','c'], ['p', 'q'], ['r', 's']])
while c.hasNext():
  print(c.next(), end=', ')
print()

Output:

[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5],

['a', 'p', 'r'], ['a', 'p', 's'], ['a', 'q', 'r'], ['a', 'q', 's'], ['b', 'p', 'r'], ['b', 'p', 's'], ['b', 'q', 'r'], ['b', 'q', 's'], ['c', 'p', 'r'], ['c', 'p', 's'], ['c', 'q', 'r'], ['c', 'q', 's'],

Solution in Java, using recursion

import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;

class PermIterator {
		
	private Iterator<Set<String>> it;
    int count = 0;
    
    PermIterator (Set<Set<String>> n) {      
        count =n.size();
        it = n.iterator();
    }
    
    public Set<String> next() {
    	count--;
    	return it.next(); 
    }
    
    public boolean hasNext() {
        if (count > 0)
        	return true;
        return false;
    }
}

public class IteratorForPermKArrays {
	
    public static Set<Set<String>> multiply(String[] x, String[] y, String[] z) {        	
    	List<List<String>> input = new ArrayList<>();
		input.add(Arrays.asList(x));
		input.add(Arrays.asList(y));
		input.add(Arrays.asList(z));			
		Set<Set<String>> result = permK(input);    	
    	return result;
    }
    
	//Time O(nXk) = O(n^2), Space O(n^2), n is the max length of arrays, K is number of arrays
	public static Set<Set<String>> permK(List<List<String>> in) {
		final Set<Set<String>> out = new HashSet<Set<String>>();
		permUtil(new ArrayList<List<String>>(in), new HashSet<String>(), out);
		return out;
	}
	
	private static void permUtil(List<List<String>> in, Set<String> part, Set<Set<String>> out) {
		if (in.isEmpty()) {
			out.add(part);
			return;
		}
		if (out.contains(part)) 
			return;
		List<List<String>> nextIn = new ArrayList<List<String>>(in);
		for (String s : nextIn.remove(0)) {
			Set<String> nextPart = new LinkedHashSet<String>(part);
			nextPart.add(s);
			permUtil(nextIn, nextPart, out);
		}
	}
	 
	public static void main(String[] args) {
		String[] x = {"a","b","c"};
		String[] y = {"p","q"};
		String[] z = {"r","s"};
		
		Set<Set<String>> result = multiply(x,y,z);

		System.out.println("Permutation of arrys:");
		PermIterator k = new PermIterator(result);
        while(k.hasNext()){
            System.out.println(k.next());
        }
	} 
}

import java.util.*;
import java.util.stream.Collectors;

public class CartesianIteration {

    public static void main(String... arg) {
        CartesianIterator<Character> characterCartesianIterator = new CartesianIterator<>(
                Arrays.asList(
                        Arrays.asList('a', 'b', 'c'),
                        Arrays.asList('p', 'q'),
                        Arrays.asList('r', 's')));


        while (characterCartesianIterator.hasNext()) {
            System.out.println(characterCartesianIterator.next());
        }
    }
}

class CartesianIterator<T> implements Iterator<List<T>> {

    private List<List<T>> results;
    private int iterCursor = 0;

    public CartesianIterator(List<List<T>> ListOfLists) {
        results = process(ListOfLists);
    }

    public List<List<T>> process(List<List<T>> lists) {
        List<List<T>> tempResults = new ArrayList<>();
        if (lists.size() == 1) {
            return lists
                    .get(0)
                    .stream()
                    .map(Arrays::asList)
                    .collect(Collectors.toList());
        }
        for (T t : lists.get(0)) {
            for (List<T> recursionInnerList : process(lists.subList(1, lists.size()))) {
                List<T> innerList = new ArrayList<>(Collections.singletonList(t));
                innerList.addAll(recursionInnerList);
                tempResults.add(innerList);
            }
        }
        return tempResults;
    }

    @Override
    public boolean hasNext() {
        return iterCursor < results.size();
    }

    @Override
    public List<T> next() {
        return results.get(iterCursor++);
    }
}