FInd Possible Permutations of Given Numbers whose Multiplication Gives the Required Number

Question

Questions :
A set of digits S separated by space is passed as input. A number N is also passed as the input. The program must find the two numbers N1, N2 from S so that N1*N2 = N and print them.

Input Format: The set of digits in S separated by space.

Boundary Conditions: The count of digits in S is less than 50.

Output Format: N1 followed by N2 separated by a space(Here N1 >= N2)

Example Input/Output 1:

Input:

6 8 5 3 9 4
552337

Output:

859 643

Explanation:

Using the digits given 859*643 = 552337. As 859 > 643 it is printed first.

Example Input/Output 2:

Input:

2 1 2
42

Output:

21 2

Any possible ideas about how to go about doing this will be appreciated.

Answer 1

Have a look at the itertools.permutations function. Then it's simply merging the strings, parsing as int and multiplying them until you find the right one.

---

Alternatively you can factorize N and then test if the pair of factors contains all the digits in S

from itertools import permutations
from numpy import sqrt

def permuts(S,N):
    def factorize(N):
        return [ (i, N//i) for i in xrange(1,int(sqrt(N))) if N%i == 0 ]

    factors = factorize(N)
    for i,j in factors:
        for p in permutations(str(i)+str(j)):
            if ' '.join(map(str, p)) == S:
                return j,i

Usage :

permuts("2 1 2", 42) -> (21, 2)