import java.util.*;

public class IteratorForPermKArrays implements Iterator<Set<String>>{
	
	private Set<Set<String>> permResult;
	private Iterator<Set<String>> it;
	
	//Call recursion, Time O(n*k), Space O(n*k), n is the max length of arrays, k is number of arrays
	public IteratorForPermKArrays(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));
		permResult = permKArrays(input); 
	}
	    
	//Recursion, Time O(n*k), Space O(n*k)
	public static Set<Set<String>> permKArrays(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;
	}
	
	//recursion helper, Time O(n*k), Space O(n*k)
	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);
		}
	}
	
	//Call set iterator, Time O(1), Space O(1)
    Iterator<Set<String>> PermIterator() {      
    	it = permResult.iterator();
    	return it;
    }
    
    //Time O(1), Space O(1)
    @Override
	public Set<String> next() {
    	return it.next(); 
    }
    
    //Time O(1), Space O(1)
    @Override
    public boolean hasNext() {
        return it.hasNext();
    }
	 
	public static void main(String[] args) {
		String[] x = {"a","b","c"};
		String[] y = {"p","q"};
		String[] z = {"r","s"};		
		IteratorForPermKArrays obj = new IteratorForPermKArrays(x, y, z);
		Iterator<Set<String>> ite = obj.PermIterator();
        while(ite.hasNext()) {
            System.out.println(ite.next());
        }
	} 
}