Number of ways to partition a set into k subsets

In this problem, we are tasked with finding the number of ways to partition a set of n elements into k non-empty subsets. The objective is to determine how many different ways we can distribute the elements into these subsets.

Problem Statement

Given a set of n elements and a positive integer k, we need to find the number of distinct ways to partition the set into k non-empty subsets.

Example Scenario

Let's say we have a set of 6 elements: {1, 2, 3, 4, 5, 6}. If we want to partition this set into 3 subsets, the total number of ways to do so is 90.

Idea to Solve the Problem

To solve this problem, we can use dynamic programming with memoization. We'll define a recursive function that calculates the number of ways to partition the set into k subsets. We'll consider two cases for each element: either it's included in a subset or it's not.

Pseudocode

int partition(int n, int k)
{
    // Base cases
    if (n == 0 || k == 0 || k > n)
        return 0;
    if (k == 1 || k == n)
        return 1;

    // Recursive cases
    return partition(n - 1, k - 1) + k * partition(n - 1, k);
}

Algorithm Explanation

1. Create a function partition that takes two arguments: n (number of elements in the set) and k (number of subsets).
2. Implement base cases:
   • If n is 0, k is 0, or k is greater than n, return 0 (invalid cases).
   • If k is 1 or k is equal to n, return 1 (only one way to partition in these cases).
3. Implement recursive cases:
   • For each element in the set, calculate the number of ways to partition the remaining elements into k - 1 subsets, considering that the current element is included in one of the subsets.
   • Calculate the number of ways to partition the remaining elements into k subsets, considering that the current element is not included in any subset.
   • Add the results of these two recursive calls.

Program Solution

• C
• C++
• Go
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin
• Rust

// C program
// Number of ways to partition a set into k subsets
#include <stdio.h>

int partition(int n, int k)
{
    if (n == 0 || k == 0 || k > n)
    {
        // Outside the range
        return 0;
    }
    if (k == 1 || k == n)
    {
        // When single result possible
        return 1;
    }
    // Count partition recursively
    return partition(n - 1, k - 1) + k * partition(n - 1, k);
}
// Handles the request to count number of partition in subsets
void countPartition(int n, int k)
{
    // Display given data
    printf("\n Given n : %d", n);
    printf("\n Given k : %d", k);
    // Display calculated result
    printf("\n Total partition  : %d", partition(n, k));
}
int main(int argc, char
    const *argv[])
{
    // Test cases
    countPartition(6, 3);
    countPartition(5, 2);
    return 0;
}

 Given n : 6
 Given k : 3
 Total partition  : 90
 Given n : 5
 Given k : 2
 Total partition  : 15

// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program for
    Treap implementation
*/
class SubsetsPartition
{
	public: int partition(int n, int k)
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return this->partition(n - 1, k - 1) + k *this->partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	void countPartition(int n, int k)
	{
		// Display given data
		cout << "\n Given n : " << n;
		cout << "\n Given k : " << k;
		// Display calculated result
		cout << "\n Total partition : " << this->partition(n, k);
	}
};
int main()
{
	SubsetsPartition *task = new SubsetsPartition();
	// Test cases
	task->countPartition(6, 3);
	task->countPartition(5, 2);
	return 0;
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

package main
import "fmt"
func partition(n, k int) int {
	if n == 0 || k == 0 || (n < k) {
		//  Outside the range
		return 0
	}
	if k == 1 || k == n {
		//  When single result possible
		return 1
	}
	//  Count partition recursively
	return (partition((n - 1), (k - 1)) + (k * partition((n - 1), k)))
}
//  Handles the request to count number of partition in subsets
func countPartition(n, k int) {
	//  Display given data
	fmt.Printf("\n Given n : %d", n)
	fmt.Printf("\n Given k : %d", k)
	//  Display calculated result
	fmt.Printf("\n Total partition  : %d", partition(n, k))
}
func main() {
	//  Test cases
	countPartition(6, 3)
	countPartition(5, 2)
}

 Given n : 6
 Given k : 3
 Total partition  : 90
 Given n : 5
 Given k : 2
 Total partition  : 15

/*
    Java Program for
    Treap implementation
*/
public class SubsetsPartition
{
	public int partition(int n, int k)
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return partition(n - 1, k - 1) + k * partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	public void countPartition(int n, int k)
	{
		// Display given data
		System.out.print("\n Given n : " + n);
		System.out.print("\n Given k : " + k);
		// Display calculated result
		System.out.print("\n Total partition : " + partition(n, k));
	}
	public static void main(String[] args)
	{
		SubsetsPartition task = new SubsetsPartition();
		// Test cases
		task.countPartition(6, 3);
		task.countPartition(5, 2);
	}
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

// Include namespace system
using System;
/*
    Csharp Program for
    Treap implementation
*/
public class SubsetsPartition
{
	public int partition(int n, int k)
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	public void countPartition(int n, int k)
	{
		// Display given data
		Console.Write("\n Given n : " + n);
		Console.Write("\n Given k : " + k);
		// Display calculated result
		Console.Write("\n Total partition : " + this.partition(n, k));
	}
	public static void Main(String[] args)
	{
		SubsetsPartition task = new SubsetsPartition();
		// Test cases
		task.countPartition(6, 3);
		task.countPartition(5, 2);
	}
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

<?php
/*
    Php Program for
    Treap implementation
*/
class SubsetsPartition
{
	public	function partition($n, $k)
	{
		if ($n == 0 || $k == 0 || $k > $n)
		{
			// Outside the range
			return 0;
		}
		if ($k == 1 || $k == $n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return $this->partition($n - 1, $k - 1) + $k * $this->partition($n - 1, $k);
	}
	// Handles the request to count number of partition in subsets
	public	function countPartition($n, $k)
	{
		// Display given data
		echo("\n Given n : ".$n);
		echo("\n Given k : ".$k);
		// Display calculated result
		echo("\n Total partition : ".$this->partition($n, $k));
	}
}

function main()
{
	$task = new SubsetsPartition();
	// Test cases
	$task->countPartition(6, 3);
	$task->countPartition(5, 2);
}
main();

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

/*
    Node JS Program for
    Treap implementation
*/
class SubsetsPartition
{
	partition(n, k)
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	countPartition(n, k)
	{
		// Display given data
		process.stdout.write("\n Given n : " + n);
		process.stdout.write("\n Given k : " + k);
		// Display calculated result
		process.stdout.write("\n Total partition : " + this.partition(n, k));
	}
}

function main()
{
	var task = new SubsetsPartition();
	// Test cases
	task.countPartition(6, 3);
	task.countPartition(5, 2);
}
main();

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

#    Python 3 Program for
#    Treap implementation
class SubsetsPartition :
	def partition(self, n, k) :
		if (n == 0 or k == 0 or k > n) :
			#  Outside the range
			return 0
		
		if (k == 1 or k == n) :
			#  When single result possible
			return 1
		
		#  Count partition recursively
		return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k)
	
	#  Handles the request to count number of partition in subsets
	def countPartition(self, n, k) :
		#  Display given data
		print("\n Given n : ", n, end = "")
		print("\n Given k : ", k, end = "")
		#  Display calculated result
		print("\n Total partition : ", self.partition(n, k), end = "")
	

def main() :
	task = SubsetsPartition()
	#  Test cases
	task.countPartition(6, 3)
	task.countPartition(5, 2)

if __name__ == "__main__": main()

 Given n :  6
 Given k :  3
 Total partition :  90
 Given n :  5
 Given k :  2
 Total partition :  15

#    Ruby Program for
#    Treap implementation
class SubsetsPartition 
	def partition(n, k) 
		if (n == 0 || k == 0 || k > n) 
			#  Outside the range
			return 0
		end

		if (k == 1 || k == n) 
			#  When single result possible
			return 1
		end

		#  Count partition recursively
		return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k)
	end

	#  Handles the request to count number of partition in subsets
	def countPartition(n, k) 
		#  Display given data
		print("\n Given n : ", n)
		print("\n Given k : ", k)
		#  Display calculated result
		print("\n Total partition : ", self.partition(n, k))
	end

end

def main() 
	task = SubsetsPartition.new()
	#  Test cases
	task.countPartition(6, 3)
	task.countPartition(5, 2)
end

main()

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

/*
    Scala Program for
    Treap implementation
*/
class SubsetsPartition()
{
	def partition(n: Int, k: Int): Int = {
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return partition(n - 1, k - 1) + k * partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	def countPartition(n: Int, k: Int): Unit = {
		// Display given data
		print("\n Given n : " + n);
		print("\n Given k : " + k);
		// Display calculated result
		print("\n Total partition : " + partition(n, k));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SubsetsPartition = new SubsetsPartition();
		// Test cases
		task.countPartition(6, 3);
		task.countPartition(5, 2);
	}
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

/*
    Swift 4 Program for
    Treap implementation
*/
class SubsetsPartition
{
	func partition(_ n: Int, _ k: Int) -> Int
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return self.partition(n - 1, k - 1) + k * self.partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	func countPartition(_ n: Int, _ k: Int)
	{
		// Display given data
		print("\n Given n : ", n, terminator: "");
		print("\n Given k : ", k, terminator: "");
		// Display calculated result
		print("\n Total partition : ", self.partition(n, k), terminator: "");
	}
}
func main()
{
	let task = SubsetsPartition();
	// Test cases
	task.countPartition(6, 3);
	task.countPartition(5, 2);
}
main();

 Given n :  6
 Given k :  3
 Total partition :  90
 Given n :  5
 Given k :  2
 Total partition :  15

/*
    Kotlin Program for
    Treap implementation
*/
class SubsetsPartition
{
	fun partition(n: Int, k: Int): Int
	{
		if (n == 0 || k == 0 || k > n)
		{
			// Outside the range
			return 0;
		}
		if (k == 1 || k == n)
		{
			// When single result possible
			return 1;
		}
		// Count partition recursively
		return this.partition(n - 1, k - 1) + k * this.partition(n - 1, k);
	}
	// Handles the request to count number of partition in subsets
	fun countPartition(n: Int, k: Int): Unit
	{
		// Display given data
		print("\n Given n : " + n);
		print("\n Given k : " + k);
		// Display calculated result
		print("\n Total partition : " + this.partition(n, k));
	}
}
fun main(args: Array < String > ): Unit
{
	val task: SubsetsPartition = SubsetsPartition();
	// Test cases
	task.countPartition(6, 3);
	task.countPartition(5, 2);
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

// Rust program
// Number of ways to partition a set into k subsets
fn main()  {
	// Test cases
	count_partition(6, 3);
	count_partition(5, 2);
}
fn count_partition(n: i32, k: i32) {
	// Display given data
	print!("\n Given n : {}", n);
	print!("\n Given k : {}", k);
	// Display calculated result
	print!("\n Total partition : {}", partition(n, k));
}
fn partition(n: i32, k: i32) -> i32 {
	if n == 0 || k == 0 || k > n {
		// Outside the range
		return 0;
	}
	if k == 1 || k == n {
		// When single result possible
		return 1;
	}
	// Count partition recursively
	return partition(n - 1, k - 1) + k * partition(n - 1, k);
}

 Given n : 6
 Given k : 3
 Total partition : 90
 Given n : 5
 Given k : 2
 Total partition : 15

Output Explanation

The code implements the algorithm and finds the number of ways to partition a set into k subsets based on the provided input. It demonstrates two test cases and displays the resulting number of ways.

Time Complexity

The time complexity of this algorithm is O(n * k), where n is the number of elements in the set and k is the number of subsets. The dynamic programming approach with memoization ensures that overlapping subproblems are computed only once, resulting in an efficient solution.