P&C.cpp

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

// Function to calculate factorial
long long factorial(int n) {
    if (n <= 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// Function to calculate nPr (Permutations)
// Formula: nPr = n! / (n-r)!
long long permutations(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0) return 1;
    
    long long result = 1;
    for (int i = n; i > (n - r); i--) {
        result *= i;
    }
    return result;
}

// Function to calculate nCr (Combinations)
// Formula: nCr = n! / (r! * (n-r)!)
long long combinations(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    
    // Use symmetry property: nCr = nC(n-r)
    if (r > n - r) r = n - r;
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

// Function to generate all permutations of a string
void generatePermutations(string str) {
    cout << "\nAll permutations of '" << str << "':" << endl;
    sort(str.begin(), str.end()); // Start with lexicographically smallest
    
    do {
        cout << str << " ";
    } while (next_permutation(str.begin(), str.end()));
    cout << endl;
}

// Function to generate all combinations of r elements from a vector
void generateCombinations(vector<int>& arr, int r) {
    int n = arr.size();
    cout << "\nAll combinations of " << r << " elements from array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    // Create a boolean vector for combinations
    vector<bool> selector(n, false);
    fill(selector.begin(), selector.begin() + r, true);
    
    do {
        cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (selector[i]) {
                cout << arr[i] << " ";
            }
        }
        cout << "}" << endl;
    } while (prev_permutation(selector.begin(), selector.end()));
}

// Function to calculate permutations with repetition
// Formula: n^r
long long permutationsWithRepetition(int n, int r) {
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= n;
    }
    return result;
}

// Function to calculate combinations with repetition
// Formula: (n+r-1)Cr
long long combinationsWithRepetition(int n, int r) {
    return combinations(n + r - 1, r);
}

// Function to calculate circular permutations
// Formula: (n-1)!
long long circularPermutations(int n) {
    if (n <= 1) return 1;
    return factorial(n - 1);
}

// Function to demonstrate derangements (permutations with no fixed points)
// Formula: !n = n! * Σ((-1)^i / i!) for i=0 to n
long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    if (n == 2) return 1;
    
    // Using recurrence: !n = (n-1) * (!(n-1) + !(n-2))
    long long dp[n + 1];
    dp[0] = 1;
    dp[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
    }
    
    return dp[n];
}

int main() {
    cout << "=== PERMUTATIONS AND COMBINATIONS - COMPLETE GUIDE ===" << endl;
    
    // Basic examples
    int n = 5, r = 3;
    
    cout << "\n1. BASIC FORMULAS:" << endl;
    cout << "n = " << n << ", r = " << r << endl;
    cout << "Factorial of " << n << " = " << factorial(n) << endl;
    cout << "Permutations P(" << n << "," << r << ") = " << permutations(n, r) << endl;
    cout << "Combinations C(" << n << "," << r << ") = " << combinations(n, r) << endl;
    
    cout << "\n2. PERMUTATIONS WITH REPETITION:" << endl;
    cout << "Choosing " << r << " items from " << n << " with repetition = " 
         << permutationsWithRepetition(n, r) << endl;
    
    cout << "\n3. COMBINATIONS WITH REPETITION:" << endl;
    cout << "Choosing " << r << " items from " << n << " with repetition = " 
         << combinationsWithRepetition(n, r) << endl;
    
    cout << "\n4. CIRCULAR PERMUTATIONS:" << endl;
    cout << "Circular permutations of " << n << " objects = " 
         << circularPermutations(n) << endl;
    
    cout << "\n5. DERANGEMENTS:" << endl;
    cout << "Derangements of " << n << " objects = " << derangements(n) << endl;
    
    // Practical examples
    cout << "\n6. GENERATING ALL PERMUTATIONS:" << endl;
    string word = "ABC";
    generatePermutations(word);
    
    cout << "\n7. GENERATING ALL COMBINATIONS:" << endl;
    vector<int> numbers = {1, 2, 3, 4};
    generateCombinations(numbers, 2);
    
    // Additional formulas and properties
    cout << "\n8. IMPORTANT PROPERTIES:" << endl;
    cout << "nC0 = " << combinations(n, 0) << " (always 1)" << endl;
    cout << "nCn = " << combinations(n, n) << " (always 1)" << endl;
    cout << "nCr = nC(n-r): C(5,2) = " << combinations(5, 2) 
         << ", C(5,3) = " << combinations(5, 3) << endl;
    cout << "Pascal's Identity: C(n-1,r-1) + C(n-1,r) = C(n,r)" << endl;
    cout << "C(4,1) + C(4,2) = " << combinations(4, 1) + combinations(4, 2) 
         << " = C(5,2) = " << combinations(5, 2) << endl;
    
    cout << "\n9. SPECIAL CASES:" << endl;
    cout << "Permutations of identical objects:" << endl;
    cout << "If we have 7 letters with 3 A's, 2 B's, 2 C's:" << endl;
    cout << "Answer = 7! / (3! × 2! × 2!) = " 
         << factorial(7) / (factorial(3) * factorial(2) * factorial(2)) << endl;
    
    cout << "\n10. BINOMIAL COEFFICIENT APPLICATIONS:" << endl;
    cout << "Sum of all combinations C(n,0) + C(n,1) + ... + C(n,n) = 2^n" << endl;
    long long sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += combinations(n, i);
    }
    cout << "For n=" << n << ": Sum = " << sum << ", 2^n = " << (1 << n) << endl;
    
    return 0;
}

/*
KEY FORMULAS SUMMARY:
===================

1. Basic Permutations: nPr = n! / (n-r)!
2. Basic Combinations: nCr = n! / (r! × (n-r)!)
3. Permutations with repetition: n^r
4. Combinations with repetition: C(n+r-1, r)
5. Circular permutations: (n-1)!
6. Permutations with identical objects: n! / (n1! × n2! × ... × nk!)
7. Derangements: !n (subfactorial)

IMPORTANT PROPERTIES:
===================
- nC0 = nCn = 1
- nCr = nC(n-r) (symmetry)
- nPr = nCr × r! (relationship between P and C)
- Pascal's Identity: C(n-1,r-1) + C(n-1,r) = C(n,r)
- Sum of all combinations: Σ C(n,r) = 2^n
- Binomial Theorem: (x+y)^n = Σ C(n,r) × x^(n-r) × y^r

WHEN TO USE WHAT:
================
- Use Permutations when ORDER MATTERS
- Use Combinations when ORDER DOESN'T MATTER
- Use "with repetition" when elements can be repeated
- Use circular permutations for arrangements in a circle
- Use derangements when no element is in its original position
*/