Subset Generation and Permutasion Analysis

Given a psoitive integer N, generate all possible subsets and permutations. For N=3, subsets are represented as binary tuples: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). Permutations for N=3 are: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Measure execution times for both operations and plot time complexity curves.

Criminal Investigation Logic Puzzle

Six suspects (A-F) are involved in a case with these constraints:

1. Either A or B is involved
2. At least two from A, E, F are involved
3. A and D cannot both be involved
4. B and C are either both invovled or both innocent
5. Exactly one of C or D is involved
6. If D is innocent, then E must also be innocent

Implementation Results

Subset and Permutation Performance

• Subset generation follows O(2^n) complexity
• Permutation generation follows O(n!) complexity

Investigation Solution

The solution requires checking all possible combinations while minimizing loop nesting. Key observations:

• Constraints 4 links B and C's status
• Only 5 variables need iteration due to relationships

Code Implementation

Subset and Permutation Generator

#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;

void swapElements(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

void generatePermutations(int arr[], int start, int end) {
    if(start == end) {
        cout << "(";
        for(int i=0; i<=end; i++) {
            cout << arr[i];
            if(i != end) cout << ",";
        }
        cout << ")" << endl;
    } else {
        for(int i=start; i<=end; i++) {
            swapElements(arr[start], arr[i]);
            generatePermutations(arr, start+1, end);
            swapElements(arr[start], arr[i]);
        }
    }
}

void printSubset(int num, int length) {
    string binary;
    while(num > 0) {
        binary = (char)((num % 2) + '0') + binary;
        num /= 2;
    }
    while(binary.length() < length) {
        binary = "0" + binary;
    }
    cout << "(";
    for(int i=0; i<length; i++) {
        cout << binary[i];
        if(i != length-1) cout << ",";
    }
    cout << ")" << endl;
}

Investigation Solver

#include<iostream>
using namespace std;

int main() {
    for(int a=0; a<=1; a++)
        for(int b=0; b<=1; b++)
            for(int d=0; d<=1; d++)
                for(int e=0; e<=1; e++)
                    for(int f=0; f<=1; f++) {
                        int c = b; // Constraint 4
                        int valid = (a || b); // Constraint 1
                        valid += (a + e + f >= 2); // Constraint 2
                        valid += !(a && d); // Constraint 3
                        valid += (c != d); // Constraint 5
                        valid += (!d || !e); // Constraint 6
                        
                        if(valid == 5) {
                            cout << "Solution found:" << endl;
                            if(a) cout << "A" << endl;
                            if(b) cout << "B\nC" << endl;
                            if(d) cout << "D" << endl;
                            if(e) cout << "E" << endl;
                            if(f) cout << "F" << endl;
                        }
                    }
    return 0;
}