/* Note 1 : Write a Program in any Language Note 2 : If you have any doubt ask in comment Note 3 : Read problem carefuly. The Bell number is the number of ways an array of n items can be partitioned into non-empty subarrays. In general, Bn is the number of partitions of a set of size n. A partition of a set S is defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. For example, B3 = 5 because the 3-element set {a, b, c} can be partitioned in 5 distinct ways: { {a}, {b}, {c} } { {a}, {b, c} } { {b}, {a, c} } { {c}, {a, b} } { {a, b, c} } Create a function that takes a number n and returns the corresponding Bell number. Example: bell(1) ➞ 1 // sampleArr = [1] // possiblePartitions = [[[1]]] bell(2) ➞ 2 // sampleArr = [1, 2] // possiblePartitions = [[[1, 2]], [[1], [2]]] bell(3) ➞ 5 // sampleArr = [1, 2, 3] // possiblePartitions = [[[1, 2, 3]], [[1, 2], [3]], [[1], [2, 3]], [[1, 3], [2]], [[1], [2], [3]]] MAX - Bell (66) at sololearn if the conditional flag PRINT_TRINAGLE (see below) value is set to 1 else Max Bell(100), it can go higher */ #include #include #include // set the value to 1 if you wish to see all intermediate values of bell triangle and compile #define PRINT_TRINAGLE 0 using namespace std; int main() { auto long_add = [](string lhs, string rhs) { // ensure lhs is bigger if (lhs.size() < rhs.size()) swap(lhs, rhs); size_t sz = rhs.size(); string res{'0'+lhs}; int c = 0; // carry transform(lhs.rbegin(),lhs.rbegin()+sz,rhs.rbegin(),res.rbegin(),[&](char& l, char& r){ int sum = l-48 + r-48 + c; c = sum / 10; return sum%10+48; }); if(c) for(auto it{res.rbegin()+sz}; c && it != res.rend(); ++it) { int sum = *it-48 + c; *it = sum % 10 + 48; c = sum / 10; } return (res.at(0) == '0') ? res.substr(1) : res; }; auto cal_bell_row = [=](vector& brc, vector& brp){ transform(begin(brc),end(brc)-1, begin(brp), begin(brc)+1, [=](auto&& cbrs, auto&& pbrs){ return long_add(cbrs, pbrs); }); #if PRINT_TRINAGLE == 1 for(auto&& s : brc) cout << s << ' '; cout << '\n'; #endif return brc; }; vector P{"1"}; cout << "Bell(1) = 1\n\n"; #if PRINT_TRINAGLE == 1 size_t Limit = 66; #else size_t Limit = 100; #endif for(size_t i=2; i<=Limit; ++i){ vector C(P.size()+1); C.at(0) = P.back(); C = cal_bell_row(C, P); P = C; cout << "Bell(" << i << ") = " << C.back() << "\n\n"; } }

[Challenge] Bell Numbers.cpp