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.
C# code for Permutation Class
using System.Collections.Generic;
namespace Miscellaneous
{
class Permutation : Combination
{
private List<string[]> local_store;
protected List<string[]> perm_store;
private int index;
public Permutation() : base()
{
}
// till the ground for shuffle to grind on
public List<string[]> possibleWordPermutations(List<string> candidates, int size) {
perm_store = new List<string[]>();
possibleWordCombinations(candidates, size);
// illegal 'r' value
if (comb_store.Count == 0 || r == 1) {
perm_store = comb_store;
}
else {
List<string[]> last_two;
last_two = new List<string[]>(){ new string[]{ "", "" }, new string[]{ "", "" } };
for (int i = 0; i < comb_store.Count; i++) {
index = r - 1;
// copy up last two elements of 'comb_store[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 = new List<string[]>();
local_store.Add(last_two[0]);
local_store.Add(last_two[1]);
if (r > 2) {
shuffleWord(local_store, i);
}
perm_store.AddRange(local_store);
}
}
return perm_store;
}
private void shuffleWord(List<string[]> arg_store, int i) {
local_store = new List<string[]>();
List<string> members;
for (int j = 0; j < arg_store.Count; j++) {
members = new List<string>();
members.AddRange(arg_store[j]);
// add 'index' 'comb_store[i]' element to this list of members
members.Add(comb_store[i][index]);
string temp_char;
int shift_index = members.Count;
// shuffle this pack of words
while (shift_index > 0) {
// skip if already in store
if (!local_store.Contains(members.ToArray())) {
local_store.Add(members.ToArray());
}
// interchange these two neighbours
if (--shift_index > 0 && !members[shift_index].Equals(members[shift_index - 1])) {
temp_char = members[shift_index];
members[shift_index] = members[shift_index - 1];
members[shift_index - 1] = temp_char;
}
}
}
// Are there any elements left? repeat if yes
if (index-- > 0) {
shuffleWord(local_store, i);
}
}
}
}
namespace Miscellaneous
{
class Permutation : Combination
{
private List<string[]> local_store;
protected List<string[]> perm_store;
private int index;
public Permutation() : base()
{
}
// till the ground for shuffle to grind on
public List<string[]> possibleWordPermutations(List<string> candidates, int size) {
perm_store = new List<string[]>();
possibleWordCombinations(candidates, size);
// illegal 'r' value
if (comb_store.Count == 0 || r == 1) {
perm_store = comb_store;
}
else {
List<string[]> last_two;
last_two = new List<string[]>(){ new string[]{ "", "" }, new string[]{ "", "" } };
for (int i = 0; i < comb_store.Count; i++) {
index = r - 1;
// copy up last two elements of 'comb_store[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 = new List<string[]>();
local_store.Add(last_two[0]);
local_store.Add(last_two[1]);
if (r > 2) {
shuffleWord(local_store, i);
}
perm_store.AddRange(local_store);
}
}
return perm_store;
}
private void shuffleWord(List<string[]> arg_store, int i) {
local_store = new List<string[]>();
List<string> members;
for (int j = 0; j < arg_store.Count; j++) {
members = new List<string>();
members.AddRange(arg_store[j]);
// add 'index' 'comb_store[i]' element to this list of members
members.Add(comb_store[i][index]);
string temp_char;
int shift_index = members.Count;
// shuffle this pack of words
while (shift_index > 0) {
// skip if already in store
if (!local_store.Contains(members.ToArray())) {
local_store.Add(members.ToArray());
}
// interchange these two neighbours
if (--shift_index > 0 && !members[shift_index].Equals(members[shift_index - 1])) {
temp_char = members[shift_index];
members[shift_index] = members[shift_index - 1];
members[shift_index - 1] = temp_char;
}
}
}
// Are there any elements left? repeat if yes
if (index-- > 0) {
shuffleWord(local_store, i);
}
}
}
}
Main Class
using System;
using System.Collections.Generic;
namespace Miscellaneous
{
class Program
{
static void Main(string[] args)
{
List<String> goods;
goods = new List<String>() { "Eno", "Chidi", "Olu", "Ahmed", "Osas", "Gbeda" };
Permutation perm = new Permutation();
List<String[]> result = perm.possibleWordPermutations(goods, 5);
// print choices and operation
Console.Write("[ ");
foreach (string choice in perm.words)
{
Console.Write(choice + "; ");
}
Console.WriteLine("] permutation " + perm.r + ":" + Environment.NewLine);
// print out permutations nicely
int i = 0;
foreach (string[] set in result)
{
Console.Write(++i + ": ");
foreach (string member in set)
{
Console.Write(member + "; ");
}
Console.WriteLine();
}
Console.WriteLine(Environment.NewLine + "Number of ways is " + result.Count + ".");
}
}
}
using System.Collections.Generic;
namespace Miscellaneous
{
class Program
{
static void Main(string[] args)
{
List<String> goods;
goods = new List<String>() { "Eno", "Chidi", "Olu", "Ahmed", "Osas", "Gbeda" };
Permutation perm = new Permutation();
List<String[]> result = perm.possibleWordPermutations(goods, 5);
// print choices and operation
Console.Write("[ ");
foreach (string choice in perm.words)
{
Console.Write(choice + "; ");
}
Console.WriteLine("] permutation " + perm.r + ":" + Environment.NewLine);
// print out permutations nicely
int i = 0;
foreach (string[] set in result)
{
Console.Write(++i + ": ");
foreach (string member in set)
{
Console.Write(member + "; ");
}
Console.WriteLine();
}
Console.WriteLine(Environment.NewLine + "Number of ways is " + result.Count + ".");
}
}
}