Combination in C++

Code for Doing Combination in C++

Writing up an algorithm to carry out the different Combination - Selection without Repetition, ⁿC_r - of a set of things in C++ requires some level of imaginative thinking.

Get a writing pad and pencil:

Write out all n members in the set - for Combination - at the top of the pad.
Beginning with the first member, match it separately with the other members until the required selected-group size (r) is reached.
When every possible Combination for this first member is exhausted, remove the current first member from the mother set.
The immediate next member becomes the new first member in the culminating set.
Take the first member in what is left of the mother set and repeat the same process from step II.

This is exactly what we will do with code to list up all possible selections without repetition in C++.

Create a new C++ project; call it Miscellaneous.
Create a new C++ class file; call it Combination.

Type out the adjoining C++ code for the combination of different options (ⁿC_r).

Why Bother About Combination

Well, isn't it obvious?
Say you are to pick only four (4) pupils from a class of six - such a small class; our little Combination algorithm solves this little problem for you by showing all your possible options / selection outcomes.

Combination Header File

#pragma once

#include <string>
#include <vector>

using namespace std;

class Combination
{
public:
    Combination();
    virtual ~Combination();
    // variables
    vector<string> words;
    unsigned short r; // min length of word
    // functions
    vector<vector<string>> possibleWordCombinations(vector<string>, unsigned short);
    void progressiveCombination(void);
protected:
    vector<vector<string>> comb_store;
private:
    void repetitivePairing(vector<string>, unsigned);
    unsigned int i;
};

C++ code for Combination Class File

#include "stdafx.h"
#include "Combination.h"

Combination::Combination()
{
}

// point of entry
vector<vector<string>> Combination::possibleWordCombinations(vector<string> candidates, unsigned short dimension) {
    words = candidates;
    r = dimension;
    comb_store = {};
    i = 0;
    // check for conformity
    if (r <= 0 || r > words.size()) {
        comb_store = {};
    }
    else if (r == 1) {
        for (; i < words.size(); i++) {
            comb_store.push_back({words[i]});
        }
    }
    else {
        progressiveCombination();
    }
    return comb_store;
}

// do combinations for all 'words' element
void Combination::progressiveCombination() {
    //        single member list
    repetitivePairing({words[i]}, i + 1);
    if (i + r <= words.size()) {
        // move on to next degree
        i++;
        progressiveCombination();
    }
}

// do all possible combinations for 1st element of this array
void Combination::repetitivePairing(vector<string> prefix, unsigned position) {
    vector<string> * auxiliary_store;
    auxiliary_store = new vector<string>[words.size() - position];
    for (unsigned j = 0; position < words.size(); position++, j++) {
        // check if desired -- r -- size will be realised
        if (r - prefix.size() <= words.size() - position) {
            auxiliary_store[j] = prefix;
            auxiliary_store[j].push_back(words[position]);
            if (auxiliary_store[j].size() < r) {
                // see to adding next word on
                repetitivePairing(auxiliary_store[j], position + 1);
            }
            else {
                comb_store.push_back(auxiliary_store[j]);
            }
        }
    }
    delete[] auxiliary_store; // memory friendly
    comb_store.shrink_to_fit();
}

Combination::~Combination()
{
}

Main Class

#include "stdafx.h"
#include "Combination.h"
#include <vector>

#include <iostream>

using namespace std;

int main()
{
    vector<string> goods = { "Eno", "Chidi", "Olu", "Ahmed", "Osas", "Gbeda" };
    Combination combo;
    vector<vector<string>> result = combo.possibleWordCombinations(goods, 3);
    // print choices and operation
    cout << "\n[";
    for (string choice : combo.words) {
        cout << choice << "; ";
    }
    cout << "] combination " << combo.r << ":\n\n";

    // print out combinations nicely
    int i = 0;
    for (vector<string> set : result) {
        i++;
        cout << i << ":    ";
        for (string member : set) {
            cout << member << "; ";
        }
        cout << "\n";
    }
    cout << "\nNumber of ways is " << result.size() << ".";

    return 0;
}

I have a better version / See other versions.