Possible Selections With Repetition.
Imagine being given the opportunity to pick six (6) exercise books
from a book-shop having 10 different brands of exercise books -
Ben 10, Chelsea F.C., Superman, Tottenham F.C.,
Indomitables, Manchester City F.C., Spider Man,
Power Rangers, Liverpool F.C. and Bat Man exercise books.
If you happen to be a big Power Rangers fan, nothing stops you from
selecting all 6 exercise books to be Power Rangers exercise books.
But you can as well decide to pick only 3 Power Rangers exercise books
and make up for the other 3 with any other brands of exercise book.
Code for Repetitive Selection in C++
The algorithm for Selection with Repetition will be a lot similar to that of combination.
- Beginning with the first member in the mother set, match it separately with every member - including itself - until the required Selection group-size (r) is reached.
- When every possible Selection with this member is exhausted, move to the next member in the mother set and repeat Step I.
This is how our Repetitive Selection code in C++ will work.
Create a new C++ class file;
Call it Selection
.
Type out the adjoining C++ code for Selection with Repetition.
Selection Header File
#include <string>
#include <vector>
using namespace std;
class Selection
{
public:
Selection();
virtual ~Selection();
// variables
vector<string> words;
unsigned short r; // min length of word
// functions
vector<vector<string>> groupSelection(vector<string>, unsigned short);
void recursiveFillUp(vector<string>);
protected:
vector<vector<string>> complete_group;
private:
unsigned i;
};
C++ Code for Selection Class File
#include "Selection.h"
Selection::Selection()
{
}
vector<vector<string>> Selection::groupSelection(vector<string> candidates, unsigned short dimension) {
words = candidates;
r = dimension;
complete_group = {};
i = 0;
recursiveFillUp({});
return complete_group;
}
// pick elements recursively
void Selection::recursiveFillUp(vector<string> temp) {
vector<string> * picked_elements;
picked_elements = new vector<string>[words.size()];
unsigned j = i;
while (j < words.size()) {
picked_elements[j] = temp;
picked_elements[j].push_back(words[j]);
// recoil factor
if (i >= words.size()) {
i = j;
}
// satisfied yet?
if (picked_elements[j].size() == r) {
complete_group.push_back(picked_elements[j]);
}
else if (picked_elements[j].size() < r) {
recursiveFillUp(picked_elements[j]);
}
j++;
}
if (!picked_elements[--j].empty() && picked_elements[j].size() == r) {
i++; // keep recoil factor straightened out
}
delete[] picked_elements;
}
Selection::~Selection()
{
}
Main Class
#include "Selection.h"
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<string> goods = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
Selection pick;
vector<vector<string>> result = pick.groupSelection(goods, 2);
// print choices and operation
cout << "\n[ ";
for (string choice : pick.words) {
cout << choice << "; ";
}
cout << "] selection " << pick.r << ":\n\n";
// print out selections 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;
}