Рубрики

Числа звонка (Количество способов Разбить Набор)

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

Input:  n = 2
Output: Number of ways = 2
Explanation: Let the set be {1, 2}
            { {1}, {2} } 
            { {1, 2} }

Input:  n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
             { {1}, {2}, {3} }
             { {1}, {2, 3} }
             { {2}, {1, 3} }
             { {3}, {1, 2} }
             { {1, 2, 3} }. 

Решением вышеупомянутых вопросов является номер Белла .

Что такое колокольчик?
Пусть S (n, k) — общее количество разбиений n элементов на k множеств. Значение n-го числа Белла является суммой S (n, k) для k = 1 до n.

Значение S (n, k) может быть определено рекурсивно как S (n + 1, k) = k * S (n, k) + S (n, k-1)

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

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

Первые несколько номеров Белла: 1, 1, 2, 5, 15, 52, 203,….

Простой метод для вычисления n-го числа Белла состоит в том, чтобы последовательно вычислять S (n, k) при k = 1 до n и возвращать сумму всех вычисленных значений. Обратитесь к этому для вычисления S (n, k).

Лучший метод — использовать Bell Triangle . Ниже приведен образец Белл Треугольник для первых нескольких номеров Белл.

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52

Треугольник построен по формуле ниже.

// If this is first column of current row 'i'
If j == 0
   // Then copy last entry of previous row
   // Note that i'th row has i entries
   Bell(i, j) = Bell(i-1, i-1) 

// If this is not first column of current row
Else 
   // Then this element is sum of previous element 
   // in current row and the element just above the
   // previous element
   Bell(i, j) = Bell(i-1, j-1) + Bell(i, j-1)

интерпретация
Затем Белл (n, k) считает количество разбиений множества {1, 2,…, n + 1}, в котором элемент k + 1 является наибольшим элементом, который может быть один в своем наборе.

Например, Bell (3, 2) равен 3, это количество подсчетов {1, 2, 3, 4}, в котором 3 является наибольшим единичным элементом. Есть три таких раздела:

    {1}, {2, 4}, {3}
    {1, 4}, {2}, {3}
    {1, 2, 4}, {3}. 

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

C ++

// Программа на C ++ для поиска n-го числа Белла
#include<iostream>

using namespace std;

  

int bellNumber(int n)

{

   int bell[n+1][n+1];

   bell[0][0] = 1;

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

   {

      // Явное заполнение для j = 0

      bell[i][0] = bell[i-1][i-1];

  

      // Заполняем оставшиеся значения j

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

         bell[i][j] = bell[i-1][j-1] + bell[i][j-1];

   }

   return bell[n][0];

}

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

int main()

{

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

      cout << "Bell Number " << n << " is " 

           << bellNumber(n) << endl;

   return 0;

}

Джава

// Java-программа для поиска номера Белла

import java.io.*;

  

class GFG 

{

    // Функция для поиска n-го номера звонка

    static int bellNumber(int n)

    {

        int[][] bell = new int[n+1][n+1];

        bell[0][0] = 1;

          

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

        {

            // Явное заполнение для j = 0

            bell[i][0] = bell[i-1][i-1];

   

            // Заполняем оставшиеся значения j

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

                bell[i][j] = bell[i-1][j-1] + bell[i][j-1];

        }

          

        return bell[n][0];

    }

      

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

    public static void main (String[] args) 

    {

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

            System.out.println("Bell Number "+ n +

                            " is "+bellNumber(n));

    }

}

  
// Этот код предоставлен Pramod Kumar

python3

# Программа на Python, чтобы найти номер Белла

  

def bellNumber(n):

  

    bell = [[0 for i in range(n+1)] for j in range(n+1)]

    bell[0][0] = 1

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

  

        # Явно заполните для j = 0

        bell[i][0] = bell[i-1][i-1]

  

        # Заполнить оставшиеся значения j

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

            bell[i][j] = bell[i-1][j-1] + bell[i][j-1]

  

    return bell[n][0]

  
# Драйверная программа

for n in range(6):

    print('Bell Number', n, 'is', bellNumber(n))

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

C #

// C # программа для поиска n-го номера звонка

using System;

  

class GFG {

      

    // Функция для поиска n

    // Колокольчик

    static int bellNumber(int n)

    {

        int[,] bell = new int[n + 1, 

                              n + 1];

        bell[0, 0] = 1;

          

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

        {

              

            // Явное заполнение для j = 0

            bell[i, 0] = bell[i - 1, i - 1];

  

            // Заполняем оставшиеся значения j

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

                bell[i, j] = bell[i - 1, j - 1] + 

                             bell[i, j - 1];

        }

          

        return bell[n, 0];

    }

      

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

    public static void Main () 

    {

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

            Console.WriteLine("Bell Number "+ n +

                              " is "+bellNumber(n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для поиска
// номер колокольчика

  
// функция, которая возвращает
// номер колокольчика

function bellNumber($n)

{

  

    $bell[0][0] = 1;

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

    {

          

        // Явное заполнение для j = 0

        $bell[$i][0] = $bell[$i - 1]

                            [$i - 1];

      

        // Заполнить оставшиеся

        // значения j

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

            $bell[$i][$j] = $bell[$i - 1][$j - 1] + 

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

    }

    return $bell[$n][0];

}

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

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

echo("Bell Number " . $n . " is "

      . bellNumber($n) . "\n");

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


Выход:

Bell Number 0 is 1
Bell Number 1 is 1
Bell Number 2 is 2
Bell Number 3 is 5
Bell Number 4 is 15
Bell Number 5 is 52

Сложность времени вышеупомянутого решения составляет O (n 2 ). Вскоре мы обсудим другие более эффективные методы вычисления чисел Белла.

Еще одна проблема, которую можно решить с помощью колокольчиков .
Число не содержит квадратов, если оно не делится на идеальный квадрат, отличный от 1. Например, 6 — это число без квадратов, а 12 — не делится на 4.
Дано число без квадратов x, найти количество различных мультипликативных разбиений x. Число мультипликативных разбиений — Белл (n), где n — число простых множителей x. Например, x = 30, есть 3 простых множителя 2, 3 и 5. Таким образом, ответ — Bell (3), который равен 5. 5 разделов — 1 x 30, 2 x15, 3 x 10, 5 x 6 и 2. х 3 х 5.

Упражнение:
Вышеуказанная реализация вызывает арифметическое переполнение для немного больших значений n. Расширьте вышеуказанную программу, чтобы результаты вычислялись по модулю 1000000007, чтобы избежать переполнения.

Ссылка:
https://en.wikipedia.org/wiki/Bell_number
https://en.wikipedia.org/wiki/Bell_triangle

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

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

Числа звонка (Количество способов Разбить Набор)

0.00 (0%) 0 votes