Outer product as string?

Question

I am trying to do the following. The outer product of an array [a,b; c,d] with itself can be described as a 4x4 array of 'strings' of length 2. So in the upper left corner of the 4x4 matrix, the values are aa, ab, ac, ad. What's the best way to generate these strings in numpy/python or matlab?

This is an example for just one outer product. The goal is to handle k successive outer products, that is the 4x4 matrix can be multiplied again by [a,b; c,d] and so on.

Answer 1

Could it be that you want the Kronecker product of two char.arrays?

A quick adaptation of np.kron (numpy/lib/shape_base.py):

def outer(a,b):
    # custom 'outer' for this issue
    # a,b must be np.char.array for '+' to be defined
    return a.ravel()[:, np.newaxis]+b.ravel()[np.newaxis,:]

def kron(a,b):
    # assume a,b are 2d char array
    # functionally same as np.kron, but using custom outer()
    result = outer(a, b).reshape(a.shape+b.shape)
    result = np.hstack(np.hstack(result))
    result = np.char.array(result)
    return result

A  = np.char.array(list('abcd')).reshape(2,2)

produces:

A =>

[['a' 'b']
 ['c' 'd']]

outer(A,A) =>

[['aa' 'ab' 'ac' 'ad']
 ['ba' 'bb' 'bc' 'bd']
 ['ca' 'cb' 'cc' 'cd']
 ['da' 'db' 'dc' 'dd']]

kron(A,A) =>

[['aa' 'ab' 'ba' 'bb']
 ['ac' 'ad' 'bc' 'bd']
 ['ca' 'cb' 'da' 'db']
 ['cc' 'cd' 'dc' 'dd']]

kron rearranges the outer elements by reshaping it to (2,2,2,2), and then concatenating twice on axis=1.

kron(kron(A,A),A) =>

[['aaa' 'aab' 'aba' 'abb' 'baa' 'bab' 'bba' 'bbb']
 ['aac' 'aad' 'abc' 'abd' 'bac' 'bad' 'bbc' 'bbd']
 ['aca' 'acb' 'ada' 'adb' 'bca' 'bcb' 'bda' 'bdb']
 ['acc' 'acd' 'adc' 'add' 'bcc' 'bcd' 'bdc' 'bdd']
 ['caa' 'cab' 'cba' 'cbb' 'daa' 'dab' 'dba' 'dbb']
 ['cac' 'cad' 'cbc' 'cbd' 'dac' 'dad' 'dbc' 'dbd']
 ['cca' 'ccb' 'cda' 'cdb' 'dca' 'dcb' 'dda' 'ddb']
 ['ccc' 'ccd' 'cdc' 'cdd' 'dcc' 'dcd' 'ddc' 'ddd']]

kron(kron(kron(A,A),A),A) =>

# (16,16)
[['aaaa' 'aaab' 'aaba' 'aabb'...]
 ['aaac' 'aaad' 'aabc' 'aabd'...]
 ['aaca' 'aacb' 'aada' 'aadb'...]
 ['aacc' 'aacd' 'aadc' 'aadd'...]
 ...]

Answer 2

To continue the discussion after Jose Varz's answer:

def foo(A,B):
    flatA [x for row in A for x in row],
    flatB = [x for row in B for x in row]
    outer = [[y+x for x in flatA] for y in flatB]
    return outer

In [265]: foo(A,A)
Out[265]: 
[['aa', 'ab', 'ac', 'ad'],
 ['ba', 'bb', 'bc', 'bd'],
 ['ca', 'cb', 'cc', 'cd'],
 ['da', 'db', 'dc', 'dd']]

In [268]: A3=np.array(foo(foo(A,A),A))
In [269]: A3
Out[269]: 
array([['aaa', 'aab', 'aac', 'aad', 'aba', 'abb', 'abc', 'abd', 'aca',
        'acb', 'acc', 'acd', 'ada', 'adb', 'adc', 'add'],
       ['baa', 'bab', 'bac', 'bad', 'bba', 'bbb', 'bbc', 'bbd', 'bca',
        'bcb', 'bcc', 'bcd', 'bda', 'bdb', 'bdc', 'bdd'],
       ['caa', 'cab', 'cac', 'cad', 'cba', 'cbb', 'cbc', 'cbd', 'cca',
        'ccb', 'ccc', 'ccd', 'cda', 'cdb', 'cdc', 'cdd'],
       ['daa', 'dab', 'dac', 'dad', 'dba', 'dbb', 'dbc', 'dbd', 'dca',
        'dcb', 'dcc', 'dcd', 'dda', 'ddb', 'ddc', 'ddd']], 
      dtype='|S3')

In [270]: A3.reshape(4,4,4)
Out[270]: 
array([[['aaa', 'aab', 'aac', 'aad'],
        ['aba', 'abb', 'abc', 'abd'],
        ['aca', 'acb', 'acc', 'acd'],
        ['ada', 'adb', 'adc', 'add']],

       [['baa', 'bab', 'bac', 'bad'],
        ['bba', 'bbb', 'bbc', 'bbd'],
        ['bca', 'bcb', 'bcc', 'bcd'],
        ['bda', 'bdb', 'bdc', 'bdd']],

       [['caa', 'cab', 'cac', 'cad'],
        ['cba', 'cbb', 'cbc', 'cbd'],
        ['cca', 'ccb', 'ccc', 'ccd'],
        ['cda', 'cdb', 'cdc', 'cdd']],

       [['daa', 'dab', 'dac', 'dad'],
        ['dba', 'dbb', 'dbc', 'dbd'],
        ['dca', 'dcb', 'dcc', 'dcd'],
        ['dda', 'ddb', 'ddc', 'ddd']]], 
      dtype='|S3')

With this definition, np.array(foo(A,foo(A,A))).reshape(4,4,4) produces the same array.

In [285]: A3.reshape(8,8)
Out[285]: 
array([['aaa', 'aab', 'aac', 'aad', 'aba', 'abb', 'abc', 'abd'],
       ['aca', 'acb', 'acc', 'acd', 'ada', 'adb', 'adc', 'add'],
       ['baa', 'bab', 'bac', 'bad', 'bba', 'bbb', 'bbc', 'bbd'],
       ['bca', 'bcb', 'bcc', 'bcd', 'bda', 'bdb', 'bdc', 'bdd'],
       ['caa', 'cab', 'cac', 'cad', 'cba', 'cbb', 'cbc', 'cbd'],
       ['cca', 'ccb', 'ccc', 'ccd', 'cda', 'cdb', 'cdc', 'cdd'],
       ['daa', 'dab', 'dac', 'dad', 'dba', 'dbb', 'dbc', 'dbd'],
       ['dca', 'dcb', 'dcc', 'dcd', 'dda', 'ddb', 'ddc', 'ddd']], 
      dtype='|S3')

Answer 3

You can obtain @Jaime's result in a much simpler way using np.char.array():

a  = np.char.array(list('abcd'))
print(a[:,None]+a)

which gives:

chararray([['aa', 'ab', 'ac', 'ad'],
       ['ba', 'bb', 'bc', 'bd'],
       ['ca', 'cb', 'cc', 'cd'],
       ['da', 'db', 'dc', 'dd']],
      dtype='|S2')

Answer 4

Using a funky mix of itertools and numpy you could do:

>>> from itertools import product
>>> s = 'abcd' # s = ['a', 'b', 'c', 'd'] works the same
>>> np.fromiter((a+b for a, b in product(s, s)), dtype='S2',
                count=len(s)*len(s)).reshape(len(s), len(s))
array([['aa', 'ab', 'ac', 'ad'],
       ['ba', 'bb', 'bc', 'bd'],
       ['ca', 'cb', 'cc', 'cd'],
       ['da', 'db', 'dc', 'dd']],
      dtype='|S2')

You can also avoid using numpy getting a little creative with itertools:

>>> from itertools import product, islice
>>> it = (a+b for a, b in product(s, s))
>>> [list(islice(it, len(s))) for j in xrange(len(s))]
[['aa', 'ab', 'ac', 'ad'],
 ['ba', 'bb', 'bc', 'bd'],
 ['ca', 'cb', 'cc', 'cd'],
 ['da', 'db', 'dc', 'dd']]

Answer 5

You could use list comprehensions in Python:

array = [['a', 'b'], ['c', 'd']]
flatarray = [ x for row in array for x in row]
outerproduct = [[y+x for x in flatarray] for y in flatarray]
Output: [['aa', 'ab', 'ac', 'ad'], ['ba', 'bb', 'bc', 'bd'], ['ca', 'cb', 'cc', 'cd'], ['da', 'db', 'dc', 'dd']]