0

suppose we have a list like [x,y,z] and a number like 2. i need an algorithm to find all monomials with this 3 variable and degree=2

my algorithm:

def mul(x:list, y:list) -> list:
        return ["".join(elm) for elm in product(x, y)]

def f(x:list, n:int) -> list:
    r = x;
    for i in range(n-1):
        r = mul(r, x)
    return r

>>> f(['x','y','z'],2)
['xx', 'xy', 'xz', 'yx', 'yy', 'yz', 'zx', 'zy', 'zz']

is there any better algorithm to do this?

EDIT:

1) suppose 'xz' != 'zx' 2) suppose 'xx' = 'x^2'

Alireza Afzal Aghaei
  • 1,184
  • 10
  • 27
  • The question is too broad. One can imagine lots of algorithms to do this and it is not clear what are the desired properties of an algorithm you are looking for. (Do you really need ALL the algorithms that solve this problem?) Please, clarify. – Ilya V. Schurov Nov 12 '16 at 15:35
  • sorry, i need to do this with a better algorithm, i cant find any other solution for my problem. – Alireza Afzal Aghaei Nov 12 '16 at 16:06
  • What do you mean by 'better'? What are your exact requirements? Do you need faster algorithm? How fast should it be? – Ilya V. Schurov Nov 12 '16 at 16:27
  • @IlyaV.Schurov lowest time complexity! – Alireza Afzal Aghaei Nov 13 '16 at 06:49
  • I doubt there is any way to do it faster then `itertools.product` (which is designed exactly for solving this problem), like in the answer by vishes_shell. – Ilya V. Schurov Nov 13 '16 at 10:29
  • @IlyaV.Schurov i'm looking for another algorithm without product... – Alireza Afzal Aghaei Nov 13 '16 at 12:14
  • After all, your problem is equivalent to the problem of calculating the Cartesian power of some finite set. `itertools.product` is created for exactly this kind of problems and solve it rather efficiently. Maybe, you can try some approaches discussed here: http://stackoverflow.com/questions/11144513/numpy-cartesian-product-of-x-and-y-array-points-into-single-array-of-2d-points — but it seems they are slower than `itertools.product` for small arrays. – Ilya V. Schurov Nov 13 '16 at 13:05

1 Answers1

3

I believe what you're looking for is called product from itertools module

from itertools import product

a=product(['x','y','z'], repeat=2)
list(map(lambda x: ''.join(x), a))

Output:

['xx', 'xy', 'xz', 'yx', 'yy', 'yz', 'zx', 'zy', 'zz']
vishes_shell
  • 22,409
  • 6
  • 71
  • 81