Algorithm: একটা loop-এর জায়গায় একটা call, আর একটা set-এর প্রতিটা ক্রম

Bob বন্ধুদের একটা ছবির জন্য এক সারি চেয়ারে বসাচ্ছে, আর সে প্রতিটা বসার ক্রম একবার করে দেখতে চায়। তিনজন বন্ধুর জন্য সে লেখে তিনটা nested loop, ছয়জনের জন্য ছয়টা। তারপর Maria বলে, কয়জন আসবে কেউ জানে না, আর loop-এর কোনো বাঁধা সংখ্যা দিয়ে সেটা হয় না। দিনশেষে Amara জানতে চায় café-র মোট বিক্রি, সবচেয়ে ভালো ঘণ্টাটা, আর কয় ঘণ্টায় ঠিক 30 কাপ বিক্রি হয়েছে। Bob আরও তিনটা loop লেখে, আর তার একটা শুরু হয় index 0-র বদলে 1 থেকে।

এই প্রতিটা কাজ standard library-তে মাত্র একটা call। এই lesson দেখাবে call-গুলো কী, ওরা একটা container-কে কীভাবে দেখে, আর প্রতিটার খরচ কত।

Algorithm হলো এমন একটা function, যেটা একটা range নেয়

STL-এ একটা algorithm হলো এমন একটা function, যেটা কাজ করে element-এর একটা range-এর উপর, পুরো container-এর উপর না। তুমি ওর হাতে Module 11-এর দুইটা iterator দাও, first আর last। ও first থেকে শুরু করে পরের প্রতিটা element নেয়, last পর্যন্ত, কিন্তু ওটাকে নিজে নেয় না। এটাকেই বলে half-open range [first, last)।

যে algorithm-গুলো হিসাব-নিকাশ করে, যেমন accumulate, ওরা থাকে <numeric> header-এ। বাকিরা, যেমন count, max_element, reverse আর next_permutation, থাকে <algorithm>-এ। নিচে দুইটা call আছে, প্রতিটা একবার পুরো vector-এর উপর, আরেকবার ওর একটা অংশের উপর।

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> sold{4, 7, 2, 9, 5, 7};
    cout << accumulate(sold.begin(), sold.end(), 0) << '\n';
    cout << accumulate(sold.begin() + 1, sold.begin() + 4, 0) << '\n';
    cout << count(sold.begin(), sold.end(), 7) << '\n';
    cout << count(sold.begin(), sold.begin() + 3, 7) << '\n';
    return 0;
}

34
18
2
1

পুরো vector যোগ করলে হয় 34। sold.begin() + 1 থেকে sold.begin() + 4 ধরে position 1, 2 আর 3, তাই দ্বিতীয় লাইনটা 7 + 2 + 9 = 18। count পুরো vector-এ দুইটা 7 পেয়েছে, আর প্রথম তিনটা position-এ পেয়েছে একটা।

তাই একই call পুরো vector-এর উপরও চলে, আবার ওর যেকোনো একটা অংশের উপরও চলে; বদলায় শুধু iterator দুইটা।

যে চারটা loop আর লিখতে হবে না

এই হলো Amara-র দিনশেষের হিসাব: পাঁচ ঘণ্টার প্রতিটায় কয় কাপ বিক্রি হয়েছে। Program-টা প্রতিটা প্রশ্নের উত্তর দুইবার দেয়, আগে Bob-এর হাতে লেখা loop দিয়ে, তারপর একটা করে call দিয়ে। শেষে reverse দিয়ে vector-টাকে উল্টে দেয়।

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> cups{12, 30, 18, 30, 9};

    int total = 0;
    for (int x : cups) {
        total += x;
    }
    int biggest = cups[0];
    for (int x : cups) {
        if (x > biggest) {
            biggest = x;
        }
    }
    int thirties = 0;
    for (int x : cups) {
        if (x == 30) {
            thirties++;
        }
    }
    cout << "loops: " << total << ' ' << biggest << ' ' << thirties << '\n';

    cout << "calls: " << accumulate(cups.begin(), cups.end(), 0) << ' '
         << *max_element(cups.begin(), cups.end()) << ' '
         << count(cups.begin(), cups.end(), 30) << '\n';

    reverse(cups.begin(), cups.end());
    cout << "reversed:";
    for (int x : cups) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

loops: 99 30 2
calls: 99 30 2
reversed: 9 30 18 30 12

দুই পথেই একই সংখ্যা print হলো। Call-গুলোতে এমন কোনো index নেই যেটা ভুল করে 1 থেকে শুরু হবে, এমন কোনো সেরা-এখন-পর্যন্ত নেই যেটা ভুল মান দিয়ে শুরু হবে। <-এর জায়গায় ভুল করে <= লেখার সুযোগও নেই। max_element একটা মান না, একটা iterator ফেরত দেয়, তাই program মানটা পড়ে * দিয়ে। তাই প্রতিটা call এক লাইনে নিজের কাজের নাম বলে দেয়, আর loop-টা উধাও।

একটা set-এর প্রতিটা ক্রম: next_permutation

Bob-এর বসার ক্রমগুলো হলো permutation: একই জিনিসগুলোর প্রতিটা সম্ভাব্য ক্রম। তিনজন বন্ধু বসতে পারে 3 × 2 × 1 = 6 রকমে, লেখা হয় 3!, পড়া হয় "3 factorial"। Nested loop ছাড়া এদের তালিকা বানাতে হলে ক্রমগুলোকে সাজাও dictionary order-এ। দুইটা ক্রমের আগে প্রথম জিনিসটা মেলাও, সেটা সমান হলে দ্বিতীয়টা, ঠিক যেভাবে অভিধান শব্দ সাজায়।

next_permutation(first, last) range-টাকে dictionary order-এর পরের ক্রমে সাজিয়ে দেয়, আর true ফেরত দেয়। Range-এ যদি আগে থেকেই শেষ ক্রমটা থাকে, মানে সবচেয়ে বড়টা, তাহলে ও ফেরত দেয় false। সাথে range-টাকে আবার প্রথম ক্রমে, মানে সবচেয়ে ছোটটায়, ফিরিয়ে আনে। তাই যে loop ওকে false না পাওয়া পর্যন্ত call করে, সেটা প্রতিটা ক্রম ঠিক একবার করে দেখে।

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> seat{1, 2, 3};
    int orders = 0;
    do {
        cout << seat[0] << ' ' << seat[1] << ' ' << seat[2] << '\n';
        orders++;
    } while (next_permutation(seat.begin(), seat.end()));
    cout << orders << " orders, and seat is back to " << seat[0] << ' ' << seat[1] << ' ' << seat[2] << '\n';
    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
6 orders, and seat is back to 1 2 3

Loop-টা do-while, কারণ প্রথম ক্রম 1 2 3-কে প্রথম call সরানোর আগেই কাজে লাগাতে হবে। 3 2 1-এর পরে call false ফেরত দিয়েছে আর পেছনে রেখে গেছে 1 2 3, তাই loop থামার সময় vector আবার শুরুর জায়গায়। এই পাঁচ লাইনই চলে 3 জন, 6 জন বা n জন বন্ধুর জন্য। তাই চেয়ার যতগুলোই হোক, Bob-এর nested loop-এর জঙ্গলের জায়গা নেয় next_permutation।

দেখো, next_permutation কীভাবে 1 2 3 পেরিয়ে যায়

প্রতিটা call এমন সবচেয়ে ছোট বদলটা করে, যাতে ক্রমটা বড় হয়, চারটা চালে। প্রথমে খোঁজে শেষ rise: সবচেয়ে ডানের position i, যেখানে v[i] < v[i + 1]। তারপর ওর পরের element-গুলোর মধ্যে খোঁজে সবচেয়ে ডানের সেইটা, যেটা v[i]-এর চেয়ে বড়, আর দুটোকে swap করে। শেষে position i-এর পরের সবকিছু reverse করে। কোনো rise-ই না থাকলে range-টা সবচেয়ে বড় ক্রম, তাই call পুরো range উল্টে দেয় আর false ফেরত দেয়।

Widget-টা vector<int> v{1, 2, 3}-এর উপর ছয়টা call চালিয়ে দেখায়, প্রতি call-এ এক সারি। প্রতিটা সারি Compiler Explorer-এ একটা program print করেছে, যেটা এই চালগুলো হাতে করে। আর প্রতিটা সারি std::next_permutation-এর সাথে মিলিয়ে দেখা হয়েছে। "none" মানে কোনো rise পাওয়া যায়নি।

Call 2-এ চারটা চালই দেখা যায়। Rise-টা 1-এর কাছে, 1 swap হয় 2-এর সাথে, আর লেজের 3 1 উল্টে হয় 1 3। Call 6 3 2 1-এ কোনো rise পায় না, তাই সবকিছু উল্টে 1 2 3 বানায় আর false ফেরত দেয়। এই চালগুলোর জন্য GCC 12-এর নিজের code lesson 05 পড়ে দেখাবে। তাই প্রতিটা call যতটা পারে কম বদলায়, আর ক্রমগুলো বেরোয় ছোট থেকে বড়তে।

প্রথম দিনেই যে syntax লাগবে

#include <numeric>      accumulate, and the other arithmetic algorithms
#include <algorithm>    count, max_element, min_element, reverse, sort, next_permutation

accumulate(first, last, init)     init plus every element; the result has init's type
count(first, last, x)             how many elements equal x
max_element(first, last)          an iterator to the first largest element
min_element(first, last)          an iterator to the first smallest element
*it                               the element an iterator points at
it - v.begin()                    that element's index in a vector
reverse(first, last)              turn the range around, in place

sort(v.begin(), v.end());                          start from the smallest order
do {
    ... use v ...
} while (next_permutation(v.begin(), v.end()));   every order once, smallest first

তাই এই lesson-এর জন্য লাগে দুইটা header আর সাতটা call, আর প্রতিটা call range নেয় একই ভাবে।

আগে sort করো, নইলে ক্রম বাদ পড়বে

next_permutation dictionary order-এ শুধু সামনের দিকে যায়। মাঝখান থেকে শুরু করলে শুরুর আগের ক্রমগুলোতে ও কখনো যায় না। এই program 2 1 3 থেকে ক্রম গোনে, তারপর sort করে আবার গোনে।

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int countOrders(vector<int> v) {
    int orders = 0;
    do {
        orders++;
    } while (next_permutation(v.begin(), v.end()));
    return orders;
}

int main() {
    vector<int> friends{2, 1, 3};
    cout << "from 2 1 3: " << countOrders(friends) << " orders\n";
    sort(friends.begin(), friends.end());
    cout << "from 1 2 3: " << countOrders(friends) << " orders\n";
    return 0;
}

from 2 1 3: 4 orders
from 1 2 3: 6 orders

2 1 3 থেকে loop দেখেছে 2 1 3, 2 3 1, 3 1 2 আর 3 2 1: ছয়টার মধ্যে চারটা। শুরুর আগের দুইটা ক্রম, 1 2 3 আর 1 3 2, কখনো আসেনি। sort-এর পরে ছয়টাই বেরিয়েছে। কোনো মান দুইবার থাকলে প্রতিটা আলাদা ক্রম আসে একবার করে: 1 1 2 থেকে আসে তিনটা ক্রম, ছয়টা না, আর lesson 02 সেটা ধাপে ধাপে দেখাবে। তাই প্রতিবার আগে sort করো।

শুরুর মানই type ঠিক করে

accumulate চলতি যোগফলটা রাখে শুরুর মানের type-এ, element-এর type-এ না। এটা দুই দিকেই ঝামেলা করে: বড় যোগফলে, আর ভগ্নাংশে।

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> steps(100000, 100000);
    cout << accumulate(steps.begin(), steps.end(), 0) << '\n';
    cout << accumulate(steps.begin(), steps.end(), 0LL) << '\n';

    vector<double> prices{1.5, 2.5, 3.5};
    cout << accumulate(prices.begin(), prices.end(), 0) << '\n';
    cout << accumulate(prices.begin(), prices.end(), 0.0) << '\n';
    return 0;
}

1410065408
10000000000
6
7.5

100000 দিন ধরে রোজ 100000 পা হাঁটলে হয় 10000000000, যেটা সবচেয়ে বড় int 2147483647-এর অনেক উপরে। 0 দিলে যোগফলটা int, তাই ওটা ঘুরে গেছে, আর GCC 12 print করেছে 1410065408। Signed overflow হলো undefined behaviour, তাই এই সংখ্যাটা এই compiler যা করেছে তা, কোনো কথা দেওয়া ফল না; সংখ্যাটা কোথা থেকে আসে, lesson 05 বলবে। 0LL দিলে যোগফল long long, আর উত্তর ঠিক।

দামগুলো যোগ করলে হয় 7.5, কিন্তু 0 আবার যোগফলকে int বানিয়ে দিয়েছে। প্রতিটা ধাপে ভগ্নাংশটা কেটে পূর্ণসংখ্যা হয়ে গেছে: 0 + 1.5 হলো 1, তারপর 3.5 হলো 3, তারপর 6.5 হলো 6। 0.0 দিলে যোগফল double। তাই যে type-এ উত্তর চাও, শুরুর মানটা সেই type-এ লেখো।

প্রতিটা call-এর খরচ কত

accumulate, count, max_element আর min_element প্রতিটা element একবার করে দেখে: n-টা element-এ n ধাপ, O(n)। reverse করে n / 2-টা swap, সেটাও O(n)। একই কাজের হাতে লেখা loop-এর খরচও এক, তাই call কখনো ধীর পথ না।

next_permutation-এর একটা call worst case-এ O(n), যখন পুরো range উল্টাতে হয়, যেমন call 6-এ হলো। তবে সব ক্রম মিলিয়ে গড়ে একটা call-এ লাগে মোটামুটি 3টা তুলনা: n = 3-এ 2.5, n = 10-এ 3.08, Compiler Explorer-এ গুনে দেখা। আসল খরচ হলো ক্রমের সংখ্যা। n-টা জিনিসের ক্রম n!-টা, আর প্রতিটা বাড়তি জিনিস সংখ্যাটাকে গুণ করে বাড়ায়। এই program 8 থেকে 11টা জিনিসের পুরো do-while-এর সময় মাপে।

#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    for (int n = 8; n <= 11; n++) {
        vector<int> v(n);
        iota(v.begin(), v.end(), 1);
        auto t0 = chrono::steady_clock::now();
        long long count = 0, check = 0;
        do {
            count++;
            check += v[0];
        } while (next_permutation(v.begin(), v.end()));
        auto t1 = chrono::steady_clock::now();
        cout << n << ": " << count << " orders, " << chrono::duration<double, milli>(t1 - t0).count() << " ms (" << check << ")\n";
    }
    return 0;
}

Compiler Explorer-এর GCC 12.2-এ -O2 -std=c++17 দিয়ে এগারোবার চালানো, প্রতিবার আলাদা একটা comment দিয়ে, যাতে কিছুই cache থেকে না আসে। একই input কোনো run-এ অন্য run-এর চেয়ে 2 থেকে 3 গুণ ধীর চলেছে, তাই প্রতিটা সারিকে একটা range হিসেবে পড়ো। প্রতি ধাপে সময় মোটামুটি n গুণ বাড়ে, n! যেমন বলে। 12টা জিনিস মানে 479001600টা ক্রম, 11টার সময়ের মোটামুটি 12 গুণ। তাই 10 বা 11টা জিনিস পর্যন্ত প্রতিটা ক্রম ঘুরে দেখা চলে, আর loop-এর ভিতরের আসল কাজ এর সাথে যোগ হয়।

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> sales{120, 45, 300, 45, 80};
    cout << "total: " << accumulate(sales.begin(), sales.end(), 0) << '\n';
    cout << "largest: " << *max_element(sales.begin(), sales.end()) << '\n';
    cout << "sales of 45: " << count(sales.begin(), sales.end(), 45) << '\n';
    return 0;
}

total: 590
largest: 300
sales of 45: 2

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string secret = "853";   // the lock knows it; Kenji does not
    string code = "583";     // the three digits, in the order Kenji remembers
    sort(code.begin(), code.end());
    int tries = 0;
    do {
        tries++;
        cout << "try " << tries << ": " << code << '\n';
        if (code == secret) {
            break;
        }
    } while (next_permutation(code.begin(), code.end()));
    cout << "open after " << tries << " tries\n";
    return 0;
}

try 1: 358
try 2: 385
try 3: 538
try 4: 583
try 5: 835
try 6: 853
open after 6 tries

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> names{"alice", "bob", "david", "zara"};
    vector<int> score{72, 91, 85, 91};
    auto best = max_element(score.begin(), score.end());
    int at = best - score.begin();
    cout << "top score " << *best << " at index " << at << ": " << names[at] << '\n';
    return 0;
}

top score 91 at index 1: bob

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{1, 2, 3};
    cout << accumulate(v.begin(), v.end(), 0) << '\n';
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{3, 1, 2};
    cout << *max_element(v.begin(), v.end()) << '\n';
    reverse(v.begin(), v.end());
    return 0;
}

vector<int> friends{2, 1, 3};
int orders = 0;
do {
    orders++;
} while (next_permutation(friends.begin(), friends.end()));
cout << orders << '\n';

vector<double> prices{1.5, 2.5, 3.5};
cout << accumulate(prices.begin(), prices.end(), 0) << '\n';

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{3, 1, 2};
    int count = 0;
    do {
        count++;
    } while (next_permutation(v.begin(), v.end()));
    cout << count << '\n';
    for (int x : v) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    vector<string> words;   // every different word, in dictionary order

    // Visit every arrangement of the letters of s with next_permutation,
    // and add each one to words.

    cout << words.size() << '\n';
    for (const string& w : words) {
        cout << w << '\n';
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    int mirrors = 0;       // how many words read the same backwards
    string longest = "";   // the longest of them so far

    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        // Make a reversed copy of word with reverse. If the two are equal,
        // count the word, and keep it if it is longer than longest.
    }

    // Line 1: mirrors. Line 2: longest, or none if no word was a mirror.

    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> cards(n);   // each card's number, kept as text
    for (string& c : cards) {
        cin >> c;
    }
    string best = "";   // the biggest number found so far

    // Try every order of the cards. For each order, join the cards into one
    // string; keep it if it is a bigger number than best. Every joined string
    // has the same length, so comparing two of them as strings works.
    // Print best.

    return 0;
}

এরপর lesson 02 এই সাপ্তাহিক set-এর প্রতিটা algorithm একটা একটা করে দেখাবে, প্রতিটার খরচসহ।