Permutation of multiple arrays and iterator – code

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 (CareerCup):
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 (CareerCup):
Interleave list of lists in Java
input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
output = [1,9,5,-4,2,0,-5,3,-2,-3,-1]




[ [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)

Thanks to François Lejosne to point out the problem in my YouTube tutorial. If you have any questions or want to put comments, please post there as well. I appreciate it!

Download IteratorForPermKArrays.js
Permutation of multiple arrays and iterator (YouTube)

Comments are closed