CODEWITHSUNDEEP
algorithmnumberscombinations
WOLVERINE
WOLVERINE

Reputation: 769

All possible combinations for N numbers

Can you help me with some algorithm?

I should find all possible combinations for N numbers: 1/N, 2/N, 3/N, ... , N-2/n, N-1/N, N/N

For example take 4 numbers: A, B, C, D

1/4: A + B + C + D

2/4: A*B + A*C + A*D + B*C + B*D + C*D

3/4: A*B*C + A*B*D + A*C*D + B*C*D

4/4: A*B*C*D

How can I solve this?

Upvotes: 0

Views: 346

Answers (1)

user1196549
user1196549

Reputation:

As you can notice, these are the coefficients of the polynomial (X + A)(X + B)(X + C)(X + D) when expanded.

It suffices to implement multiplication of a polynomial by a monomial and use it iteratively.

def PolyByMono(Poly, Mono):
    Poly.append(0)
    for i in range(len(Poly) - 2, -1, -1):
        Poly[i + 1]+= Mono * Poly[i]
    Poly[0]+= Mono
    return Poly

def Expand(Numbers):
    Poly= [Numbers[0]]
    for M in Numbers[1:]:
        Poly= PolyByMono(Poly, M)

    print Poly  

Expand([1, 2, 3, 4])

gives:

[10, 35, 50, 24]

Upvotes: 1

Related Questions