พิมพ์ทุกชุดการจัดหมู่ r องค์ประกอบจากอาร์เรย์ขนาด n ใน C++

ปัญหา

ได้รับอาร์เรย์ขนาด n และจำนวนเต็มบวก r พิมพ์ทุกชุดการจัดหมู่ (Combinations) ขององค์ประกอบขนาด r

ตัวอย่าง

Input: {5,6,7,8}, r = 3
Output: {5,6,7}, {5,6,8}, {5,7,8}, {6,7,8}

วิธีแก้

Fixed elements แล้ว Recursive/Loop หาชุดอื่นๆ ต้อง Fix แค่ n-r+1 ตัวแรก

ตัวอย่างโค้ด (วิธีที่ 1: Fix และ Recur)

#include <iostream>
using namespace std;

void printRElementCombination(int arr[], int combination[], int start, int end, int index, int r) {
    if (index == r) {
        cout << "{ ";
        for (int j = 0; j < r; j++) cout << combination[j] << " ";
        cout << "}\t";
        return;
    }
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        combination[index] = arr[i];
        printRElementCombination(arr, combination, i+1, end, index+1, r);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3, n = 5;
    int combination[r];
    cout << "The combination is : \n";
    printRElementCombination(arr, combination, 0, n-1, 0, r);
}

ผลลัพธ์

{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 } { 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }

วิธีที่ 2: Include/Exclude (Backtracking)

#include <iostream>
using namespace std;

void combinationUtil(int arr[], int n, int r, int index, int combo[], int i) {
    if (index == r) {
        cout << "{";
        for (int j = 0; j < r; j++) cout << combo[j] << " ";
        cout << "}\t";
        return;
    }
    if (i >= n) return;
    combo[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, combo, i + 1); // Include
    combinationUtil(arr, n, r, index, combo, i + 1);     // Exclude
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3, n = 5;
    int combo[r];
    cout << "The combination is : \n";
    combinationUtil(arr, n, r, 0, combo, 0);
    return 0;
}

ผลลัพธ์

{1 2 3 } {1 2 4 } {1 2 5 } {1 3 4 } {1 3 5 } {1 4 5 } {2 3 4 } {2 3 5 } {2 4 5 } {3 4 5 }

คำอธิบาย

ทั้งสองวิธีให้ผลลัพธ์เดียวกัน วิธีที่ 1 Fix แล้ว Recur วิธีที่ 2 Backtracking Include/Exclude ทั้งคู่ O(nCr)