Transformations

Given a set S={M,I,U} and the following transformation rules
1) xI -> xIU
2) Mx -> Mxx
3) III -> U
4) UU -> ignore, i.e. empty

• The above rules can only be applied on complete strings and not partially.
• x represents 'any' string
  

e.g. if given MU then you can get MUU.

Find out whether MI -> MU exists or not, if yes, what are the set of rules

All Permutations

Given an array of digits (0-9) of length 'n', and a list of characters corresponding to every digit, develop an a'rithm to generate all possible strings.
Example:
Input: array A = [0, 1, 2], n = 3, charMap[0] = ['a', 'b', 'c'], charMap[1] = ['d', 'e', 'f', 'g'], charMap[2] = ['h', 'i']
Output: total 3*4*2 = 24 such strings are possible, as follows:
adh
adi
aeh
aei
afh
afi
agh
agi
bdh
bdi
beh
bei
bfh
bfi
bgh
bgi
cdh
cdi
ceh
cei
cfh
cfi
cgh
cgi