Posted on by Kalkicode
Code Backtracking

Generate combinations of integer product whose adjacent numbers are not similar

Here given code implementation process.

// C Program
// Generate combinations of integer product whose adjacent numbers are not similar
#include <stdio.h>

// Display result
void printSequence(int result[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", result[i]);
	}
	printf("\n");
}
void findCombination(int num, int result[], int index, int product)
{
	if (product == num)
	{
		// Display calculated result
		printSequence(result, index);
		return;
	}
	if (index >= num || product > num)
	{
		// Base case when stop process
		return;
	}
	for (int i = 2; i <= num / 2; ++i)
	{
		if (index == 0 || result[index - 1] != i)
		{
			// Collects resultant value
			result[index] = i;
			// Find other combination using recursion
			findCombination(num, result, index + 1, product *i);
		}
	}
}
void combination(int num)
{
	if (num <= 0)
	{
		return;
	}
	if (num == 1)
	{
		printf("\n 1 \n");
		return;
	}
	printf("\n Given Number : %d\n", num);
	// Collect result
	int result[num];
	// Test
	findCombination(num, result, 0, 1);
}
int main()
{
	int num = 20;
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	combination(num);
	num = 32;
	/*
	    num = 32
	    --------
	    2  8  2
	    2  16
	    4  2  4
	    4  8
	    8  4
	    16  2
	    ------
	    Here not consider following pairs
	    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
         - -     - -     - - - - -   - - - 
	    Because few adjacent elements same in this pairs
	*/
	combination(num);
	return 0;
}

Output

 Given Number : 20
  2  5  2
  2  10
  4  5
  5  4
  10  2

 Given Number : 32
  2  8  2
  2  16
  4  2  4
  4  8
  8  4
  16  2
// Java Program 
// Generate combinations of integer product whose adjacent numbers are not similar
public class Product
{
	// Display result
	public void printSequence(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + result[i]);
		}
		System.out.print("\n");
	}
	public void findCombination(int num, int[] result, 
      int index, int product)
	{
		if (product == num)
		{
			// Display calculated result
			printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		for (int i = 2; i <= num / 2; ++i)
		{
			if (index == 0 || result[index - 1] != i)
			{
				// Collects resultant value
				result[index] = i;
				// Find other combination using recursion
				findCombination(num, result, index + 1, product * i);
			}
		}
	}
	public void combination(int num)
	{
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			System.out.print("\n 1 \n");
			return;
		}
		System.out.println("\n Given Number : " + num );
		// Collect result
		int[] result = new int[num];
		// Test
		findCombination(num, result, 0, 1);
	}
	public static void main(String args[])
	{
		Product task = new Product();

		int num = 20;
		/*
		    num = 20
		    --------
		    2  5  2
		    2  10
		    4   5
		    5   4
		    10  2
		    ------
		    Note 2 x 2 x 5 = 20
		    But 2 and 2 are adjacent
		*/
		task.combination(num);
		num = 32;
		/*
		    num = 32
		    --------
		    2  8  2
		    2  16
		    4  2  4
		    4  8
		    8  4
		    16  2
		    ------
		    Here not consider following pairs
		    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	         - -     - -     - - - - -   - - - 
		    Because few adjacent elements same in this pairs
		*/
		task.combination(num);
	}
}

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2
// Include namespace system
using System;
// Csharp Program
// Generate combinations of integer product whose adjacent numbers are not similar
public class Product
{
	// Display result
	public void printSequence(int[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + result[i]);
		}
		Console.Write("\n");
	}
	public void findCombination(int num, int[] result, int index, int product)
	{
		if (product == num)
		{
			// Display calculated result
			this.printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		for (int i = 2; i <= num / 2; ++i)
		{
			if (index == 0 || result[index - 1] != i)
			{
				// Collects resultant value
				result[index] = i;
				// Find other combination using recursion
				this.findCombination(num, result, index + 1, product * i);
			}
		}
	}
	public void combination(int num)
	{
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			Console.Write("\n 1 \n");
			return;
		}
		Console.WriteLine("\n Given Number : " + num);
		// Collect result
		int[] result = new int[num];
		// Test
		this.findCombination(num, result, 0, 1);
	}
	public static void Main(String[] args)
	{
		Product task = new Product();
		int num = 20;
		/*
		    num = 20
		    --------
		    2  5  2
		    2  10
		    4   5
		    5   4
		    10  2
		    ------
		    Note 2 x 2 x 5 = 20
		    But 2 and 2 are adjacent
		*/
		task.combination(num);
		num = 32;
		/*
			    num = 32
			    --------
			    2  8  2
			    2  16
			    4  2  4
			    4  8
			    8  4
			    16  2
			    ------
			    Here not consider following pairs
			    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
		         - -     - -     - - - - -   - - - 
			    Because few adjacent elements same in this pairs
		*/
		task.combination(num);
	}
}

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2
package main
import "fmt"
// Go Program
// Generate combinations of integer product whose adjacent numbers are not similar
type Product struct {}
func getProduct() * Product {
	var me *Product = &Product {}
	return me
}
// Display result
func(this Product) printSequence(result[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", result[i])
	}
	fmt.Print("\n")
}
func(this Product) findCombination(num int, 
	result[] int, index int, product int) {
	if product == num {
		// Display calculated result
		this.printSequence(result, index)
		return
	}
	if index >= num || product > num {
		// Base case when stop process
		return
	}
	for i := 2 ; i <= num / 2 ; i++ {
		if index == 0 || result[index - 1] != i {
			// Collects resultant value
			result[index] = i
			// Find other combination using recursion
			this.findCombination(num, 
				result, index + 1, product * i)
		}
	}
}
func(this Product) combination(num int) {
	if num <= 0 {
		return
	}
	if num == 1 {
		fmt.Print("\n 1 \n")
		return
	}
	fmt.Println("\n Given Number : ", num)
	// Collect result
	var result = make([] int, num)
	// Test
	this.findCombination(num, result, 0, 1)
}
func main() {
	var task * Product = getProduct()
	var num int = 20
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	task.combination(num)
	num = 32
	/*
	    num = 32
	    --------
	    2  8  2
	    2  16
	    4  2  4
	    4  8
	    8  4
	    16  2
	    ------
	    Here not consider following pairs
	    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
         - -     - -     - - - - -   - - - 
	    Because few adjacent elements same in this pairs
	*/
	task.combination(num)
}

Output

 Given Number :  20
  2  5  2
  2  10
  4  5
  5  4
  10  2

 Given Number :  32
  2  8  2
  2  16
  4  2  4
  4  8
  8  4
  16  2
<?php
// Php Program
// Generate combinations of integer product whose adjacent numbers are not similar
class Product
{
	// Display result
	public	function printSequence($result, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$result[$i]);
		}
		echo("\n");
	}
	public	function findCombination($num, $result, $index, $product)
	{
		if ($product == $num)
		{
			// Display calculated result
			$this->printSequence($result, $index);
			return;
		}
		if ($index >= $num || $product > $num)
		{
			// Base case when stop process
			return;
		}
		for ($i = 2; $i <= (int)($num / 2); ++$i)
		{
			if ($index == 0 || $result[$index - 1] != $i)
			{
				// Collects resultant value
				$result[$index] = $i;
				// Find other combination using recursion
				$this->findCombination($num, $result, $index + 1, $product * $i);
			}
		}
	}
	public	function combination($num)
	{
		if ($num <= 0)
		{
			return;
		}
		if ($num == 1)
		{
			echo("\n 1 \n");
			return;
		}
		echo("\n Given Number : ".$num.
			"\n");
		// Collect result
		$result = array_fill(0, $num, 0);
		// Test
		$this->findCombination($num, $result, 0, 1);
	}
}

function main()
{
	$task = new Product();
	$num = 20;
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	$task->combination($num);
	$num = 32;
	/*
		    num = 32
		    --------
		    2  8  2
		    2  16
		    4  2  4
		    4  8
		    8  4
		    16  2
		    ------
		    Here not consider following pairs
		    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	         - -     - -     - - - - -   - - - 
		    Because few adjacent elements same in this pairs
	*/
	$task->combination($num);
}
main();

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2
// Node JS Program
// Generate combinations of integer product whose adjacent numbers are not similar
class Product
{
	// Display result
	printSequence(result, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + result[i]);
		}
		process.stdout.write("\n");
	}
	findCombination(num, result, index, product)
	{
		if (product == num)
		{
			// Display calculated result
			this.printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		for (var i = 2; i <= parseInt(num / 2); ++i)
		{
			if (index == 0 || result[index - 1] != i)
			{
				// Collects resultant value
				result[index] = i;
				// Find other combination using recursion
				this.findCombination(num, result, index + 1, product * i);
			}
		}
	}
	combination(num)
	{
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			process.stdout.write("\n 1 \n");
			return;
		}
		console.log("\n Given Number : " + num);
		// Collect result
		var result = Array(num).fill(0);
		// Test
		this.findCombination(num, result, 0, 1);
	}
}

function main()
{
	var task = new Product();
	var num = 20;
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	task.combination(num);
	num = 32;
	/*
		    num = 32
		    --------
		    2  8  2
		    2  16
		    4  2  4
		    4  8
		    8  4
		    16  2
		    ------
		    Here not consider following pairs
		    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	         - -     - -     - - - - -   - - - 
		    Because few adjacent elements same in this pairs
	*/
	task.combination(num);
}
main();

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2
#  Python 3 Program
#  Generate combinations of integer product whose adjacent numbers are not similar
class Product :
	#  Display result
	def printSequence(self, result, n) :
		i = 0
		while (i < n) :
			print(" ", result[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def findCombination(self, num, result, index, product) :
		if (product == num) :
			#  Display calculated result
			self.printSequence(result, index)
			return
		
		if (index >= num or product > num) :
			#  Base case when stop process
			return
		
		i = 2
		while (i <= int(num / 2)) :
			if (index == 0 or result[index - 1] != i) :
				#  Collects resultant value
				result[index] = i
				#  Find other combination using recursion
				self.findCombination(num, result, index + 1, product * i)
			
			i += 1
		
	
	def combination(self, num) :
		if (num <= 0) :
			return
		
		if (num == 1) :
			print("\n 1 ")
			return
		
		print("\n Given Number : ", num)
		#  Collect result
		result = [0] * (num)
		#  Test
		self.findCombination(num, result, 0, 1)
	

def main() :
	task = Product()
	num = 20
	#    num = 20
	#    --------
	#    2  5  2
	#    2  10
	#    4   5
	#    5   4
	#    10  2
	#    ------
	#    Note 2 x 2 x 5 = 20
	#    But 2 and 2 are adjacent
	task.combination(num)
	num = 32
	# 	    num = 32
	# 	    --------
	# 	    2  8  2
	# 	    2  16
	# 	    4  2  4
	# 	    4  8
	# 	    8  4
	# 	    16  2
	# 	    ------
	# 	    Here not consider following pairs
	# 	    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	#         - -     - -     - - - - -   - - - 
	# 	    Because few adjacent elements same in this pairs
	task.combination(num)

if __name__ == "__main__": main()

Output

 Given Number :  20
  2  5  2
  2  10
  4  5
  5  4
  10  2

 Given Number :  32
  2  8  2
  2  16
  4  2  4
  4  8
  8  4
  16  2
#  Ruby Program
#  Generate combinations of integer product whose adjacent numbers are not similar
class Product 
	#  Display result
	def printSequence(result, n) 
		i = 0
		while (i < n) 
			print(" ", result[i])
			i += 1
		end

		print("\n")
	end

	def findCombination(num, result, index, product) 
		if (product == num) 
			#  Display calculated result
			self.printSequence(result, index)
			return
		end

		if (index >= num || product > num) 
			#  Base case when stop process
			return
		end

		i = 2
		while (i <= num / 2) 
			if (index == 0 || result[index - 1] != i) 
				#  Collects resultant value
				result[index] = i
				#  Find other combination using recursion
				self.findCombination(num, result, index + 1, product * i)
			end

			i += 1
		end

	end

	def combination(num) 
		if (num <= 0) 
			return
		end

		if (num == 1) 
			print("\n 1 \n")
			return
		end

		print("\n Given Number : ", num, "\n")
		#  Collect result
		result = Array.new(num) {0}
		#  Test
		self.findCombination(num, result, 0, 1)
	end

end

def main() 
	task = Product.new()
	num = 20
	#    num = 20
	#    --------
	#    2  5  2
	#    2  10
	#    4   5
	#    5   4
	#    10  2
	#    ------
	#    Note 2 x 2 x 5 = 20
	#    But 2 and 2 are adjacent
	task.combination(num)
	num = 32
	# 	    num = 32
	# 	    --------
	# 	    2  8  2
	# 	    2  16
	# 	    4  2  4
	# 	    4  8
	# 	    8  4
	# 	    16  2
	# 	    ------
	# 	    Here not consider following pairs
	# 	    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	#         - -     - -     - - - - -   - - - 
	# 	    Because few adjacent elements same in this pairs
	task.combination(num)
end

main()

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2

// Scala Program
// Generate combinations of integer product whose adjacent numbers are not similar
class Product()
{
	// Display result
	def printSequence(result: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + result(i));
			i += 1;
		}
		print("\n");
	}
	def findCombination(num: Int, result: Array[Int], 
      index: Int, product: Int): Unit = {
		if (product == num)
		{
			// Display calculated result
			printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		var i: Int = 2;
		while (i <= num / 2)
		{
			if (index == 0 || result(index - 1) != i)
			{
				// Collects resultant value
				result(index) = i;
				// Find other combination using recursion
				findCombination(num, result, index + 1, product * i);
			}
			i += 1;
		}
	}
	def combination(num: Int): Unit = {
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			print("\n 1 \n");
			return;
		}
		println("\n Given Number : " + num);
		// Collect result
		var result: Array[Int] = Array.fill[Int](num)(0);
		// Test
		findCombination(num, result, 0, 1);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Product = new Product();
		var num: Int = 20;
		/*
		    num = 20
		    --------
		    2  5  2
		    2  10
		    4   5
		    5   4
		    10  2
		    ------
		    Note 2 x 2 x 5 = 20
		    But 2 and 2 are adjacent
		*/
		task.combination(num);
		num = 32;
		/*
			    num = 32
			    --------
			    2  8  2
			    2  16
			    4  2  4
			    4  8
			    8  4
			    16  2
			    ------
			    Here not consider following pairs
			    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
		         - -     - -     - - - - -   - - - 
			    Because few adjacent elements same in this pairs
		*/
		task.combination(num);
	}
}

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2
// Swift 4 Program
// Generate combinations of integer product whose adjacent numbers are not similar
class Product
{
	// Display result
	func printSequence(_ result: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", result[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func findCombination(_ num: Int, 
                         _ result: inout[Int],
      _ index: Int, 
      _ product: Int)
	{
		if (product == num)
		{
			// Display calculated result
			self.printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		var i: Int = 2;
		while (i <= num / 2)
		{
			if (index == 0 || result[index - 1]  != i)
			{
				// Collects resultant value
				result[index] = i;
				// Find other combination using recursion
				self.findCombination(num, &result, index + 1, product * i);
			}
			i += 1;
		}
	}
	func combination(_ num: Int)
	{
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			print("\n 1 ");
			return;
		}
		print("\n Given Number : ", num);
		// Collect result
		var result: [Int] = Array(repeating: 0, count: num);
		// Test
		self.findCombination(num, &result, 0, 1);
	}
}
func main()
{
	let task: Product = Product();
	var num: Int = 20;
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	task.combination(num);
	num = 32;
	/*
		    num = 32
		    --------
		    2  8  2
		    2  16
		    4  2  4
		    4  8
		    8  4
		    16  2
		    ------
		    Here not consider following pairs
		    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	         - -     - -     - - - - -   - - - 
		    Because few adjacent elements same in this pairs
	*/
	task.combination(num);
}
main();

Output

 Given Number :  20
  2  5  2
  2  10
  4  5
  5  4
  10  2

 Given Number :  32
  2  8  2
  2  16
  4  2  4
  4  8
  8  4
  16  2
// Kotlin Program
// Generate combinations of integer product whose adjacent numbers are not similar
class Product
{
	// Display result
	fun printSequence(result: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + result[i]);
			i += 1;
		}
		print("\n");
	}
	fun findCombination(num: Int, result: Array < Int > , 
                        index: Int, product: Int): Unit
	{
		if (product == num)
		{
			// Display calculated result
			this.printSequence(result, index);
			return;
		}
		if (index >= num || product > num)
		{
			// Base case when stop process
			return;
		}
		var i: Int = 2;
		while (i <= num / 2)
		{
			if (index == 0 || result[index - 1] != i)
			{
				// Collects resultant value
				result[index] = i;
				// Find other combination using recursion
				this.findCombination(num, result, 
                                     index + 1, product * i);
			}
			i += 1;
		}
	}
	fun combination(num: Int): Unit
	{
		if (num <= 0)
		{
			return;
		}
		if (num == 1)
		{
			print("\n 1 \n");
			return;
		}
		println("\n Given Number : " + num);
		// Collect result
		val result: Array < Int > = Array(num)
		{
			0
		};
		// Test
		this.findCombination(num, result, 0, 1);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Product = Product();
	var num: Int = 20;
	/*
	    num = 20
	    --------
	    2  5  2
	    2  10
	    4   5
	    5   4
	    10  2
	    ------
	    Note 2 x 2 x 5 = 20
	    But 2 and 2 are adjacent
	*/
	task.combination(num);
	num = 32;
	/*
		    num = 32
		    --------
		    2  8  2
		    2  16
		    4  2  4
		    4  8
		    8  4
		    16  2
		    ------
		    Here not consider following pairs
		    [2,2,8] [4,4,8] [2,2,2,2,2],[2,2,2,4]...
	         - -     - -     - - - - -   - - - 
		    Because few adjacent elements same in this pairs
	*/
	task.combination(num);
}

Output

 Given Number : 20
 2 5 2
 2 10
 4 5
 5 4
 10 2

 Given Number : 32
 2 8 2
 2 16
 4 2 4
 4 8
 8 4
 16 2

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post