### Improved Permutations with the BigInteger Data Type: Listing 4

Complete demo program code.

```using System;
using System.Numerics;

namespace ImprovedPermutations
{
class PermutationsProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin improved permutations with BigInteger demo\n");

string[] names = new string[] { "Adam", "Barb", "Carl" };
Permutation p2 = new Permutation(3); // 0th
p2 = p2.Successor(); // 1
p2 = p2.Successor(); // 2
p2 = p2.Successor(); // 3
p2 = p2.Successor(); // 4
names = p2.ApplyTo(names);
Console.WriteLine("\nThe 4th permutation element applied to 'Adam', 'Barb', 'Carl' is:");
for (int i = 0; i < names.Length; ++i)
Console.Write(names[i] + " ");
Console.WriteLine("\n");

int n = 3;
Permutation p1 = new Permutation(n);
Console.WriteLine("All permutations for order n = 3 are:\n");
int ct = 0;
while (p1 != null)
{
Console.WriteLine(ct + ": " + p1.ToString());
p1 = p1.Successor();
++ct;
}

//Permutation p2 = new Permutation(n);
//string[] names = new string[] { "Adam", "Barb", "Carl" };
//p2 = p2.Element(4);
//names = p2.ApplyTo(names);
//Console.WriteLine("\nThe 4th permutation element applied to 'Adam', 'Barb', 'Carl' is:");
//for (int i = 0; i < names.Length; ++i)
//  Console.Write(names[i] + " ");
//Console.WriteLine("\n");

n = 30;
BigInteger nFactorial = Permutation.Factorial(n);
Console.WriteLine("The .NET int.MaxValue is " + int.MaxValue.ToString("#,###"));
Console.WriteLine("\nFor a permutation with order n = 30 there are n! = \n");
Console.WriteLine(nFactorial.ToString("#,###"));
Console.WriteLine("\npossible permutation elements.\n");

Permutation p3 = new Permutation(n);
BigInteger k = BigInteger.Parse("999999999999999999999999999999");
p3 = p3.Element(k);
Console.WriteLine("\nThe " + k.ToString("#,###") + "th element for order n = 30 is:");
Console.WriteLine(p3.ToString());

Console.WriteLine("\nEnd permutations demo\n");
Console.ReadLine();
}
} // class PermutationsProgram

public class Permutation
{
private int n; // order
private int[] data;

public Permutation(int n)
{
this.n = n;
this.data = new int[n];
for (int i = 0; i < n; ++i)
this.data[i] = i;
}

public static BigInteger Factorial(int k)
{
if (k == 0) return 1;
BigInteger ans = 1;
for (int i = 1; i <= k; ++i)
ans *= i;
return ans;
}

public Permutation Successor()
{
if (data[0] == n - 1 && data[n - 1] == 0)
return null;

Permutation result = new Permutation(this.n);

for (int idx = 0; idx < result.n; ++idx)  // copy curr data into result
result.data[idx] = this.data[idx];

int left, right;

left = n - 2;  // Find left value
while ((result.data[left] > result.data[left + 1]) && (left >= 1))
--left;

right = n - 1;  // find right; first value > left
while (result.data[left] > result.data[right])
--right;

int tmp = result.data[left];  // swap [left] and [right]
result.data[left] = result.data[right];
result.data[right] = tmp;

int i = left + 1;              // order the tail
int j = n - 1;

while (i < j)
{
tmp = result.data[i];
result.data[i++] = result.data[j];
result.data[j--] = tmp;
}

return result;
}

public string[] ApplyTo(string[] arr)
{
string[] result = new string[n];
for (int i = 0; i < n; ++i)
result[i] = arr[data[i]];
return result;
}

public Permutation Element(BigInteger k)
{
if (k >= Factorial(this.n))
throw new Exception("k too large in Element");
Permutation result = new Permutation(this.n);

int[] factoradic = new int[this.n]; // factoradic of k

for (int j = 1; j <= n; ++j)  // note: skip [0]
{
factoradic[n - j] = (int)(k % j);  // remainder always an int
k /= j;
}

for (int i = 0; i < n; ++i)
++factoradic[i];

result.data[n - 1] = 1; // last value set to 1

for (int i = n - 2; i >= 0; --i)
{
result.data[i] = factoradic[i];  // copy factoradic
for (int j = i + 1; j < n; ++j)  // inc all values to right . .
{
if (result.data[j] >= result.data[i]) // that are < factoradic
++result.data[j];
}
}

for (int i = 0; i < n; ++i) // make result 0-based
--result.data[i];

return result;
}

public override string ToString()
{
string s = "( ";
for (int i = 0; i < data.Length; ++i)
s += data[i] + " ";  // consider StringBuilder
s += ")";
return s;
}

} // class Permutation

} // ns
```

Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Azure and Bing. James can be reached at [email protected]rosoft.com.

comments powered by Disqus

• ### Death of the Dev Machine?

Here's a takeaway from this week's Ignite 2020 event: An advanced Azure cloud portends the death of the traditional, high-powered dev machine packed with computing, memory and storage components.

• ### COVID-19 Is Ignite 2020's Elephant in the Room: 'Frankly, It Sucks'

As in all things of our new reality, there was no escaping the drastic changes in routine caused by the COVID-19 pandemic during Microsoft's big Ignite 2020 developer/IT pro conference, this week shifted to an online-only event after drawing tens of thousands of in-person attendees in years past.

• ### Visual Studio 2019 v16.8 Preview Update Adds Codespaces

To coincide with the Microsoft Ignite 2020 IT pro/developer event, the Visual Studio dev team shipped a new update, Visual Studio 2019 v16.8 Preview 3.1, with the main attraction being support for cloud-hosted Codespaces, now in a limited beta.

• ### New for Blazor: Azure Static Web Apps Support

With Blazor taking the .NET web development world by storm, one of the first announcements during Microsoft's Ignite 2020 developer/IT event was its new support in Azure Static Web Apps.

• ### Entity Framework Core 5 RC1 Is Feature Complete, Ready for Production

The first release candidate for Entity Framework 5 -- Microsoft's object-database mapper for .NET -- has shipped with a go live license, ready for production.

Upcoming Events