Рубрики

Подсчитать количество способов разбить набор на k подмножеств

Учитывая два числа n и k, где n представляет количество элементов в наборе, найдите количество способов разбить набор на k подмножеств.

Пример:

Input: n = 3, k = 2
Output: 3
Explanation: Let the set be {1, 2, 3}, we can partition
             it into 2 subsets in following ways
             {{1,2}, {3}},  {{1}, {2,3}},  {{1,3}, {2}}  

Input: n = 3, k = 1
Output: 1
Explanation: There is only one way {{1, 2, 3}}

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Пусть S (n, k) — общее количество разбиений n элементов на k множеств. Значение S (n, k) может быть определено рекурсивно как

S(n, k) = k*S(n-1, k) + S(n-1, k-1) 

S (n, k) называется числами Стирлинга второго рода


Как работает приведенная выше рекурсивная формула?

Когда мы добавляем (n + 1) -й элемент к k разделам, есть две возможности.
1) Он добавляется как единый набор элементов к существующим разделам, т. Е. S (n, k-1)
2) Добавляется ко всем наборам каждого разбиения, т. Е. K * S (n, k)

Следовательно, S (n + 1, k) = k * S (n, k) + S (n, k-1), что означает S (n, k) = k * S (n-1, k) + S (n -1, к-1)

Ниже приведено рекурсивное решение на основе приведенной выше формулы.

C ++

// Программа на C ++ для подсчета количества разделов
// множества из n элементов в k подмножеств
#include<iostream>

using namespace std;

  
// Возвращает количество разных разделов n
// элементы в k подмножествах

int countP(int n, int k)

{

  // Базовые случаи

  if (n == 0 || k == 0 || k > n)

     return 0;

  if (k == 1 || k == n)

      return 1;

  

  // S (n + 1, k) = k * S (n, k) + S (n, k-1)

  return  k*countP(n-1, k) + countP(n-1, k-1);

}

  
// Драйвер программы

int main()

{

   cout <<  countP(3, 2);

   return 0;

}

Джава

// Java-программа для подсчета числа
// разделов множества с
// n элементов в k подмножеств

import java.io.*;

  

class GFG

{

    // Возвращает количество разных

    // разбиение n элементов в

    // k подмножеств

    public static int countP(int n, int k)

    {

       // Базовые случаи

       if (n == 0 || k == 0 || k > n)

          return 0;

       if (k == 1 || k == n)

          return 1;

  

       // S (n + 1, k) = k * S (n, k) + S (n, k-1)

       return (k * countP(n - 1, k) 

              + countP(n - 1, k - 1));

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

       System.out.println(countP(3, 2));

  

    }

}

  
// Этот код предоставлен Аншикой Гоял.

Python 3

# Программа Python3 для подсчета числа
# разделов набора с n
# элементов в k подмножеств

  
# Возвращает количество разных разделов
количество n элементов в k подмножествах

def countP(n, k):

      

    # Базовые случаи

    if (n == 0 or k == 0 or k > n):

        return 0

    if (k == 1 or k == n):

        return 1

      

    # S (n + 1, k) = k * S (n, k) + S (n, k-1)

    return (k * countP(n - 1, k) + 

                countP(n - 1, k - 1))

  
Код водителя

if __name__ == "__main__":

    print(countP(3, 2))

  
# Этот код добавлен
# от Akanksha Rai (Abby_akku)

C #

// C # программа для подсчета числа
// разделов множества с
// n элементов в k подмножеств

using System;

  

class GFG {

      

    // Возвращает количество разных

    // разбиение n элементов в

    // k подмножеств

    public static int countP(int n, int k)

    {

          

        // Базовые случаи

        if (n == 0 || k == 0 || k > n)

            return 0;

        if (k == 1 || k == n)

            return 1;

      

        // S (n + 1, k) = k * S (n, k) + S (n, k-1)

        return (k * countP(n - 1, k) 

                + countP(n - 1, k - 1));

    }

  

    // Драйвер программы

    public static void Main()

    {

        Console.WriteLine(countP(3, 2));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP-программа для подсчета
// количество разделов
// набор из n элементов
// в k подмножеств

  
// Возвращает количество разных
// разделы n элементов
// в k подмножествах

function countP($n, $k)

{

    // Базовые случаи

    if ($n == 0 || $k == 0 || $k > $n)

        return 0;

    if ($k == 1 || $k == $n)

        return 1;

      

    // S (n + 1, k) = k * S (n, k)

    // + S (n, k-1)

    return $k * countP($n - 1, $k) + 

            countP($n - 1, $k - 1);

}

  

    // Код драйвера

    echo countP(3, 2);

  
// Этот код предоставлен aj_36
?>


Выход:

3

Временная сложность вышеуказанного рекурсивного решения является экспоненциальной. Решение может быть оптимизировано, так как существуют перекрывающиеся подзадачи. Например, ниже приведено дерево рекурсии countP (10,7). Число подзадач P (8,6) или CP (8,6) вызывается несколько раз.

 CP() represents countP()

             CP(10,7)
           /        \
       CP(9,7)       CP(9,6) 
       /    \       /    \
  CP(8,7) CP(8,6) CP(8,6)  CP(8,5)
    / \    / \     / \       / \

  Partial Recursion Tree for countP(10, 7) 
  to highlight overlapping subproblems.

Таким образом, эта проблема имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив dp [] [] снизу вверх, используя приведенную выше рекурсивную формулу.

Ниже приведена реализация решения для динамического программирования.

C ++

// Программа на С ++, основанная на динамическом программировании
// количество разделов набора с n элементами
// в k подмножеств
#include<iostream>

using namespace std;

  
// Возвращает количество разных разделов n
// элементы в k подмножествах

int countP(int n, int k)

{

  // Таблица для хранения результатов подзадач

  int dp[n+1][k+1];

  

  // Базовые случаи

  for (int i = 0; i <= n; i++)

     dp[i][0] = 0;

  for (int i = 0; i <= k; i++)

     dp[0][k] = 0;

  

  // Заполняем остальные записи в dp [] []

  // снизу вверх

  for (int i = 1; i <= n; i++)

     for (int j = 1; j <= i; j++)

       if (j == 1 || i == j)

          dp[i][j] = 1;

       else

          dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];

  

  return dp[n][k];

}

  
// Драйвер программы

int main()

{

   cout <<  countP(5, 2);

   return 0;

}

Джава

// Программа Java на основе динамического программирования для подсчета
// количество разделов набора с n элементами
// в k подмножеств

class GFG{

  
// Возвращает количество разных разделов n
// элементы в k подмножествах

static int countP(int n, int k) 

    // Таблица для хранения результатов подзадач

    int[][] dp = new int[n+1][k+1]; 

      

    // Базовые случаи

    for (int i = 0; i <= n; i++) 

    dp[i][0] = 0

    for (int i = 0; i <= k; i++) 

    dp[0][k] = 0

      

    // Заполняем остальные записи в dp [] []

    // снизу вверх

    for (int i = 1; i <= n; i++) 

    for (int j = 1; j <= k; j++) 

    if (j == 1 || i == j) 

        dp[i][j] = 1

    else

        dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]; 

          

        return dp[n][k]; 

      

  
// Драйвер программы

public static void main(String[] args ) 

    System.out.println(countP(5, 2)); 


}

  
// Этот код предоставлен Rajput-Ji

python3

# Программа Python3 на основе динамического программирования
# считать количество разделов набора с
# n элементов в k подмножеств

  
# Возвращает количество разных разделов
количество n элементов в k подмножествах

def countP(n, k):

      

    # Таблица для хранения результатов подзадач

    dp = [[0 for i in range(k + 1)] 

             for j in range(n + 1)]

  

    # Базовые случаи

    for i in range(n + 1):

        dp[i][0] = 0

  

    for i in range(k + 1):

        dp[0][k] = 0

  

    # Заполните остальные записи в

    # dp [] [] снизу вверх

    for i in range(1, n + 1):

        for j in range(1, k + 1):

            if (j == 1 or i == j):

                dp[i][j] = 1

            else:

                dp[i][j] = (j * dp[i - 1][j] +

                                dp[i - 1][j - 1])

                  

    return dp[n][k]

  
Код водителя

if __name__ == '__main__':

    print(countP(5, 2))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// Программа на C # для динамического программирования
// посчитать количество разделов
// набор из n элементов в k подмножеств

using System;

  

class GFG

{

  
// Возвращает количество разных разделов n
// элементы в k подмножествах

static int countP(int n, int k) 

    // Таблица для хранения результатов подзадач

    int[,] dp = new int[n + 1, k + 1]; 

      

    // Базовые случаи

    for (int i = 0; i <= n; i++) 

        dp[i, 0] = 0; 

    for (int i = 0; i <= k; i++) 

        dp[0, k] = 0; 

      

    // Заполняем остальные записи в dp [] []

    // снизу вверх

    for (int i = 1; i <= n; i++) 

        for (int j = 1; j <= k; j++) 

            if (j == 1 || i == j) 

                dp[i, j] = 1; 

            else

                dp[i, j] = j * dp[i - 1, j] + dp[i - 1, j - 1]; 

              

        return dp[n, k]; 

      

  
// Код драйвера

public static void Main( ) 

    Console.Write(countP(5, 2)); 


}

  
// Этот код предоставлен Ita_c.

PHP

<?php
// Динамическое программирование на основе PHP
// программа для подсчета количества
// разбиения множества с n
// элементы в k подмножеств

  
// Возвращает количество разных
// разбиение n элементов в
// k подмножеств

function countP($n, $k

      
// Таблица для хранения результатов
// подзадач

$dp[$n + 1][$k + 1] = array(array()); 

  
// Базовые случаи

for ($i = 0; $i <= $n; $i++) 

    $dp[$i][0] = 0; 

for ($i = 0; $i <= $k; $i++) 

    $dp[0][$k] = 0; 

  
// Заполняем остальные записи в
// dp [] [] снизу вверх

for ($i = 1; $i <= $n; $i++) 

    for ($j = 1; $j <= $i; $j++) 

    if ($j == 1 || $i == $j

        $dp[$i][$j] = 1; 

    else

        $dp[$i][$j] = $j * $dp[$i - 1][$j] + 

                           $dp[$i - 1][$j - 1]; 

  

return $dp[$n][$k]; 

  
// Код драйвера

echo countP(5, 2); 

  
// Этот код предоставлен jit_t
?>


Выход:

15

Сложность времени: O (nxk)
Вспомогательное пространство: O (nxk)

Аналогичная статья: Белл номера

Эта статья предоставлена Радживом Агравалом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитать количество способов разбить набор на k подмножеств

0.00 (0%) 0 votes