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");
}
} // 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);

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)

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

for (int i = n - 2; i >= 0; --i)
{
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].

• First .NET 9 Preview Emphasizes Cloud-Native Development, AI Apps

"Our most important focus areas are cloud-native and intelligent app development," said Microsoft in outlining its vision for .NET 9, which this month shipped in its first preview ahead of reaching general availability in November.

• As New Visual Studio Extension Manager Previews, Mads K Floats New Tool Ideas

Just as a new extension manager for Visual Studio 2022 was announced in a preview, Microsoft's Mads Kristensen, a principal program manager for the IDE and extension author extraordinaire, floated some new ideas for new tools and functionality.

• Copilot Chat Highlights Visual Studio 2022 17.10 Preview 1

"Copilot Chat isn't just a chatbot; it's a coding companion that understands your code," the Visual Studio dev team said in announcing Preview 1.

• Principal Component Analysis from Scratch Using Singular Value Decomposition with C#

Dr. James McCaffrey of Microsoft Research presents a full-code, step-by-step tutorial on a classical ML technique that transforms a dataset into one with fewer columns, useful for creating a graph of data that has more than two columns, for example.

• AI Marks New Release of Visual Studio 2022 17.9

AI assistance and better extensibility mark the new release of Visual Studio 2022 v17.9, which shipped today with many core productivity and performance enhancements.