Permutation - What It Is.
In the unlikely scenario that the Teacher wanted to see just how any four pupils, in a class of six (6), could be seated on a four-person desk; what this Teacher would be doing in essence is called Permutation (nPr).
Code for Doing Permutation in C++
The algorithm for Permutation - nPr, possible ways of arrangement - will simply be based on that of combination.
All that is needed after combination is a rotation / shuffle of
the make-up / constituents of each possible combination result.
This shuffle simply involves interchanging the elements of the
combination group of size, r, to take all possible positions
starting from the extreme right to extreme left.
This is how our Permutation code in C++ will work.
Create a new C++ class file;
Call it Permutation
Type out the adjoining C++ code for Permutation
(nPr).
Advice: You might want to keep the mother-class size (n)
and the group-size (r) small to avoid the permutation code taking too long.
As a rule-of-thump, DO NOT ASK QUESTIONS YOU DON'T WANT TO KNOW THE ANSWER TO.
Permutation Header File
#include "Combination.h"
#include <array>
class Permutation : public Combination
{
public:
Permutation();
virtual ~Permutation();
vector<vector<string>> possibleWordPermutations(vector<string>, unsigned short);
void shuffleWord(vector<vector<string>>, unsigned);
private:
unsigned index;
vector<vector<string>> local_store;
protected:
vector<vector<string>> perm_store;
};
C++ Code for Permutation Class File
#include "Permutation.h"
Permutation::Permutation() : Combination()
{
}
// till the ground for shuffle to grind on
vector<vector<string>> Permutation::possibleWordPermutations(vector<string> candidates, unsigned short dimension) {
perm_store = {};
possibleWordCombinations(candidates, dimension);
// illegal 'r' value
if (comb_store.empty() || r == 1) {
perm_store = comb_store;
}
else {
vector<vector<string>> last_two = { {"", ""}, {"", ""} };
for (unsigned i = 0; i < comb_store.size(); i++) {
index = r - 1;
// copy up last two elements of 'comb_store.get(i)'
last_two[0][0] = last_two[1][1] = comb_store[i][index--];
last_two[0][1] = last_two[1][0] = comb_store[i][index--];
local_store = {};
local_store.push_back(last_two[0]);
local_store.push_back(last_two[1]);
if (r > 2) {
shuffleWord(local_store, i);
}
// add to final comb_store
for (vector<string> part : local_store) {
perm_store.push_back(part);
}
}
}
return perm_store;
}
void Permutation::shuffleWord(vector<vector<string>> arg_store, unsigned i) {
local_store = {};
vector<string> members;
for (unsigned j = 0; j < arg_store.size(); j++) {
members = arg_store[j];
// add 'index' 'comb_store[i]' element to this list of members
members.push_back(comb_store[i][index]);
int shift_index = members.size();
// shuffle this pack of words
while (shift_index > 0) {
vector<vector<string>>::iterator iter;
iter = search(local_store.begin(), local_store.end(), &members, &members + 1);
// skip if already in store
if (iter == local_store.end()) {
local_store.push_back(members);
}
// interchange these two neighbours
if (--shift_index > 0 && members[shift_index] != members[shift_index - 1]) {
swap(members[shift_index - 1], members[shift_index]);
}
}
}
// Are there any elements left? repeat if yes
if (index-- > 0) {
shuffleWord(local_store, i);
}
}
Permutation::~Permutation()
{
}
Main Class
#include "Permutation.h"
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<string> goods = { "Eno", "Chidi", "Olu", "Ahmed", "Osas", "Gbeda" };
Permutation perm;
vector<vector<string>> result = perm.possibleWordPermutations(goods, 3);
// print choices and operation
cout << "\n[ ";
for (string choice : perm.words) {
cout << choice << "; ";
}
cout << "] permutation " << perm.r << ":\n\n";
// print out permutations 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;
}