Permutation of multiple arrays and iterator has two tasks. First is the permutation of multiple arrays and output as an array of new combinations. The second is to implement the iterator of this new array.
Permutation is an important topic in the fields of combinatorics. It is usually implemented using recursion. The wrapper method declares the variables to store output and calls helper method. The helper calls itself to retrieve elements in arrays and re-compose them. The output is Set of Set to eliminate any duplicates.
To implement iterator, in Java, we need override hasNext() and next() methods. In JavaScript, we implement [Symbol.iterator](). In Python, we override __iter__(self) and __next__(self). Since the element is Set in the Set, we can use underlying Set iterator provided by each language’s library.
Amazon Interview Question:
x={a,b,c}, y={p,q}, z={r,s}
Define a Operation, x * y * z = {{a,p,r},{a,p,s},{a,q,r},{a,q,s}……{c,q s}}
Is to output all the results in the order of each subset, implementing a class iterator that has Next() and hasNext() methods
Facebook interview question:
Interleave list of lists in Java
Example:
input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
output = [1,9,5,-4,2,0,-5,3,-2,-3,-1]
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | import java.util.*; public class IteratorForPermKArrays implements Iterator<Set<String>> { private Set<Set<String>> permResult; private Iterator<Set<String>> it; //Constructor, 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); } //Call 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)) //memoization return; List<List<String>> nextIn = new ArrayList<List<String>>(in); //new copy 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()); } } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | class IteratorForPermKArrays { //Constructor, Time O(n*k), Space O(n*k), n is the max length of arrays, k is number of arrays constructor(x, y, z) { var input = []; input.push(x); input.push(y); input.push(z); this.permResult = this.permKArrays(input); } //Call recursion, Time O(n*k), Space O(n*k) permKArrays(input) { var out = new Set(); this.permUtil(input.slice(), new Set(), out); return out; } //recursion helper, Time O(n*k), Space O(n*k) permUtil(input, part, out) { if (input.length==0) { out.add(part); return; } if (out.has(part)) //memoization return; var nextIn = input.slice(); //new copy for (let s of nextIn.shift()) { let nextPart = new Set(part); nextPart.add(s); this.permUtil(nextIn, nextPart, out); } } //Call set iterator, Time O(1), Space O(1) [Symbol.iterator]() { let it = this.permResult[Symbol.iterator](); let count = this.permResult.size return { next: () => { if (count>=0) { count--; return {value: it.next(), done:false}; } return {value: null, done: true} } } } } x = ["a","b","c"] y = ["p","q"] z = ["r","s"] let obj = new IteratorForPermKArrays(x, y, z); for(let i of obj) console.log(i); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | class IteratorForPermKArrays : #Constructor, Time O(n*k), Space O(n*k), n is the max length of arrays, k is number of arrays def __init__(self,x, y, z) : input = [] input.append(x) input.append(y) input.append(z) self.permResult = self.permKArrays(input); #Call recursion,Time O(n*k), Space O(n*k) def permKArrays(self, input) : out = set() self.permUtil(input.copy(), set(), out) return out # recursion helper, Time O(n*k), Space O(n*k) def permUtil(self, input, part, out) : if (len(input) == 0) : out.add(frozenset(part)) return if part in out : #memoization return nextIn = input.copy() #new copy for s in nextIn.pop(0) : nextPart = set(part) nextPart.add(s) self.permUtil(nextIn, nextPart, out) # Call set iterator, Time O(1), Space O(1) def __iter__(self): self.count = len(self.permResult) self.it = iter(self.permResult) return self #Time O(1), Space O(1) def __next__(self): if self.count >= 0 : self.count -= 1 return next(self.it) else: raise StopIteration x = ["a","b","c"] y = ["p","q"] z = ["r","s"] obj = IteratorForPermKArrays(x, y, z) for i in obj: print(i) |
Output:
[
[a, p, r]
[a, p, s]
[a, q, r]
[b, p, r]
[a, q, s]
[b, p, s]
[b, q, r]
[c, p, r]
[b, q, s]
[c, p, s]
[c, q, r]
[c, q, s]
O Notation:
Time complexity: O(n*k)
Space complexity: O(n*k)
Download IteratorForPermKArrays.java
Download IteratorForPermKArrays.js
Download IteratorForPermKArrays.py
Permutation of multiple arrays and iterator (YouTube)
