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 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
#pragma once
#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 "stdafx.h"
#include "Permutation.h"
Permutation::Permutation() : Combination()
{
}
vector<vector<string>> Permutation::possibleWordPermutations(vector<string> candidates, unsigned short dimension) {
perm_store = {};
possibleWordCombinations(candidates, dimension);
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;
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);
}
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];
members.push_back(comb_store[i][index]);
int shift_index = members.size();
while (shift_index > 0) {
vector<vector<string>>::iterator iter;
iter = search(local_store.begin(), local_store.end(), &members, &members + 1);
if (iter == local_store.end()) {
local_store.push_back(members);
}
if (--shift_index > 0 && members[shift_index] != members[shift_index - 1]) {
swap(members[shift_index - 1], members[shift_index]);
}
}
}
if (index-- > 0) {
shuffleWord(local_store, i);
}
}
Permutation::~Permutation()
{
}
Main Class
#include "stdafx.h"
#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);
cout << "\n[ ";
for (string choice : perm.words) {
cout << choice << "; ";
}
cout << "] permutation " << perm.r << ":\n\n";
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;
}