Print all combinations of factors

In this article, we will discuss about the algorithms to print every combination of factors of a given number (all factorization). We have explored recursive and partially iterative approach.

What we'll see,

• Problem Statement
• Iterative Approach
• Recursive Approach
• Conclusion
• References

Problem Statement

We have to design and implement an algorithm which prints all the unique combinations of factors of the given number. For example, let the number given be 16, therefore, the output should be as follows:-

2 2 2 2
2 2 4
2 8
4 4

There are many methods to solve this problem of printing the combinations of factors of a number. Some of the approaches are discussed below;

Iterative Approach using the backtracking concept

The underneath idea to solve this problem is to multiply the iterating number to a product variable which is initially 1 and check whether the product is less, is equal, or exceeds the number at every step.

The case if the product is less than the number input, we multiply the next number to the product and check again.

If the product is equal to the number, we will output the combination of the factors multiplied to form the product (the numbers which are being iterated and multiplied to the product to make it equal to the number input), then remove or divide the last multiplied number from the product (i.e. we are using the concept of backtracking) and test out by multipying the next numbre to the product.

And if the product exceed the number, we repeat the same backtrack process until the product equals or less than the number input.

We are required to know which combinations of factors have formed the product, for that, we have to store each multiplied number into the list or stack. At the time we remove any number from the product, we also have to pop or remove it from the list or stack.

Implementation in Python

factors = []
num = int(input("Enter a number: "))

def factorCombinations(n, product):
    global l
    
    # The base condition for recursive call
    if product == num:
        print(factors)
        return
        
    for i in range(n, int(num/2)+1):
        # Returning to the last recursive call, if product exceeds the num.
        if product*i > num:
            return 
            
        # Multiplying the number to the product
        product *= i
        factors.append(i)
        
        # Recursively calling the function with same number
        factorCombinations(i, product)
        
        # Using the backtracking approach
        factors.pop()
        product //= i
        
factorCombinations(2, 1)

In the findCombinations(n, product), function declaration n is the next number to be multiplied to the product variable, the second argument.

With each recursive call or step, the product value is updated and compared with the num, the number input.

If the product variable equals the num variable, we print the combination of factors in the list and return or backtrack to the last recursive call to remove the last multiplied factor from the product and test out with the next iterative i value.

We repeat the recursive call for the same value of i, that is, findCombinations(i, product) because the combination could include duplicate factors, for example, 16 = [2, 2, 2, 2].

Recursive Approach

Recursive approach starts with 3 arguments of the number which acts as the product in this approach simillar to the iterative approach which stores the current product at each recursion step, the string to store a combination of factors(printFactors), and the parent value(parentVal) which is the original number input.

Inside the recursion block, we define a new variable newVal initially given the value of the parentVal(the parent value). Iterates through the range number-1 to 2 with decrementor i getting decreases by 1 at each iteration.

Then we check whether the number is divisible by i or not, if it is divisible, then checks the three conditions. Condition one is if the newVal is greater than the value of i, we change the value of newVal of newVal as i. Condition two is if the number divided by i (number/i) is less than or equal to the parentVal and i is less than or equal to the parentVal and number divided by i (number/i) is less than or equal to i, then print the parentFactors string concatenating it with the variable i, space for decoration and the integer value of the number divided by i. And checks the third condition, which is if i is less than parentVal, we execute the recursive call by calling the printFactors function with the arguments as the integer value of number/i, concatenated string of parentFactors, i, and a space character, and the newVal as the third argument.

This recursive approach takes in 3 inputs namely a string to carry over the current value of i in while loop to perform subsequent reduction and also a temporary integer to know when not to print duplicate reversals, that is, 8*3 and 3*8.

Implementation in Python

def printFactors(number, parentFactors, parentVal):
    ''' Initialising the variable newVal with value parentVal '''
    newVal = parentVal
    
    ''' Initialising the iterable variable i iterating through number-1 to 2 '''
    i = number-1
    while (i>=2):
    
        ''' Checking if the number is divisible by i '''
        if (number % i == 0):
            
            ''' Case when newVal is greater than i '''
            if (newVal > i) :
                
                ''' Replacing the current value of newVal with i '''
                newVal = i
            
            ''' Case when number/i is less than or equal to
            parentVal, i is less than or equal to parentVal 
            and number/i is less than or equal to i '''
            if (number / i <= parentVal and i <= parentVal and number / i <= i):
                
                ''' Printing the string of the desired output, 
                which is a combination of the factors 
                giving product equal to the parentVal '''
                print(str(parentFactors)+str(i)+" "+str(int(number/i)))
                
                ''' Setting the newVal variable, the integer value of number/i '''
                newVal = int(number/i)
            
            ''' Case when i is less than or equal to parentVal '''
            if (i <= parentVal):
                
                ''' Recursively calling the printFactors to 
                print the next combination of factors '''
                printFactors(int(number/i), str(parentFactors) + str(i) + " ", newVal)

        ''' Decrementing the i variable '''
        i-=1

printFactors(16,"",16)

Conclusion

In this article at OpenGenus, we have discussed the solution to the problem of printing all the unique combinations of the factors of the given number. We have discussed the recursive and iterative using the backtracking concept approach.