using System;
using System.Collections.Generic;
using System.Linq;
public static class DijkstraWithoutQueue
{
public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
{
var n = graph.GetLength(0);
var distance = new int[n];
for (int i = 0; i < n; i++)
{
distance[i] = int.MaxValue;
}
distance[sourceNode] = 0;
var used = new bool[n];
var previous = new int?[n];
while (true)
{
var minDistance = int.MaxValue;
var minNode = 0;
for (int i = 0; i < n; i++)
{
if (!used[i] && minDistance > distance[i])
{
minDistance = distance[i];
minNode = i;
}
}
if (minDistance == int.MaxValue)
{
break;
}
used[minNode] = true;
for (int i = 0; i < n; i++)
{
if (graph[minNode, i] > 0)
{
var shortestToMinNode = distance[minNode];
var distanceToNextNode = graph[minNode, i];
var totalDistance = shortestToMinNode + distanceToNextNode;
if (totalDistance < distance[i])
{
distance[i] = totalDistance;
previous[i] = minNode;
}
}
}
}
if (distance[destinationNode] == int.MaxValue)
{
return null;
}
var path = new LinkedList<int>();
int? currentNode = destinationNode;
while (currentNode != null)
{
path.AddFirst(currentNode.Value);
currentNode = previous[currentNode.Value];
}
return path.ToList();
}
public static void Main()
{
var graph = new[,]
{
// 0 1 2 3 4 5 6 7 8 9 10 11
{ 0, 0, 0, 0, 0, 0, 10, 0, 12, 0, 0, 0 }, // 0
{ 0, 0, 0, 0, 20, 0, 0, 26, 0, 5, 0, 6 }, // 1
{ 0, 0, 0, 0, 0, 0, 0, 15, 14, 0, 0, 9 }, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0 }, // 3
{ 0, 20, 0, 0, 0, 5, 17, 0, 0, 0, 0, 11 }, // 4
{ 0, 0, 0, 0, 5, 0, 6, 0, 3, 0, 0, 33 }, // 5
{10, 0, 0, 0, 17, 6, 0, 0, 0, 0, 0, 0 }, // 6
{ 0, 26, 15, 0, 0, 0, 0, 0, 0, 3, 0, 20 }, // 7
{12, 0, 14, 0, 0, 3, 0, 0, 0, 0, 0, 0 }, // 8
{ 0, 5, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 }, // 9
{ 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0 }, // 10
{ 0, 6, 9, 0, 11, 33, 0, 20, 0, 0, 0, 0 }, // 11
};
PrintPath(graph, 0, 9);
PrintPath(graph, 0, 2);
PrintPath(graph, 0, 10);
PrintPath(graph, 0, 11);
PrintPath(graph, 0, 1);
}
public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
{
Console.Write(
"Shortest path [{0} -> {1}]: ",
sourceNode,
destinationNode);
var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);
if (path == null)
{
Console.WriteLine("no path");
}
else
{
int pathLength = 0;
for (int i = 0; i < path.Count - 1; i++)
{
pathLength += graph[path[i], path[i + 1]];
}
var formattedPath = string.Join("->", path);
Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
}
}
}
Category: C# Algorithms
Minimum Spanning Tree – Kruskal Algorithm – C# Implementation
using System.Collections.Generic;
using System.Linq;
public static class KruskalAlgorithm
{
public static List<Edge> Kruskal(int numberOfVertices, List<Edge> edges)
{
// Inital sort
edges.Sort();
// Set parents table
var parent = Enumerable.Range(0, numberOfVertices).ToArray();
// Spanning tree list
var spanningTree = new List<Edge>();
foreach (var edge in edges)
{
var startNodeRoot = FindRoot(edge.StartNode, parent);
var endNodeRoot = FindRoot(edge.EndNode, parent);
if (startNodeRoot != endNodeRoot)
{
// Add edge to the spanning tree
spanningTree.Add(edge);
// Mark one root as parent of the other
parent[endNodeRoot] = startNodeRoot;
}
}
// Return the spanning tree
return spanningTree;
}
private static int FindRoot(int node, int[] parent)
{
var root = node;
while (root != parent[root])
{
root = parent[root];
}
while (node != root)
{
var oldParent = parent[node];
parent[node] = root;
node = oldParent;
}
return root;
}
}
How to generate Variations with repetition interatively in C#
// (red, red)
// (red, green)
// (red, blue)
// (green, red)
// (green, green)
// (green, blue)
// (blue, red)
// (blue, green)
// (blue, blue)
using System;
using System.Linq;
public static class Program
{
private static readonly string[] Fruits = { "red", "green", "blue"};
public static void Main()
{
var k = 2;
var n = 3;
var arr = new int[k];
while (true)
{
Console.WriteLine($"({string.Join(", ", arr.Select(e => Fruits[e]))})");
var index = k - 1;
while (index >= 0 && arr[index] == n - 1)
{
index--;
}
if (index < 0)
{
break;
}
arr[index]++;
for (int i = index + 1; i < k; i++)
{
arr[i] = 0;
}
}
}
}
How to generate Combinations without repetition interatively in C#
// n = 5
// k = 3
// 1, 2, 3
// 1, 2, 4
// 1, 2, 5
// 1, 3, 4
// 1, 3, 5
// 1, 4, 5
// 2, 3, 4
// 2, 3, 5
// 2, 4, 5
// 3, 4, 5
using System;
using System.Collections.Generic;
public static class GenerateCombinationsIteratively
{
static void Main()
{
Console.Write("n = ");
var n = int.Parse(Console.ReadLine());
Console.Write("k = ");
var k = int.Parse(Console.ReadLine());
foreach (var combo in Combinations(k, n))
{
Console.WriteLine(string.Join(", ", combo));
}
}
private static IEnumerable<int[]> Combinations(int k, int n)
{
var result = new int[k];
var stack = new Stack<int>();
stack.Push(1);
while (stack.Count > 0)
{
var index = stack.Count - 1;
var value = stack.Pop();
while (value <= n)
{
result[index++] = value++;
stack.Push(value);
if (index == k)
{
yield return result;
break;
}
}
}
}
}
How to generate Permutations without repetition iteratively in C#
// 1, 2, 3
// 2, 1, 3
// 3, 1, 2
// 1, 3, 2
// 2, 3, 1
// 3, 2, 1
// Total permutations: 6
using System;
using System.Linq;
public static class GeneratePermutationsIteratively
{
public static void Main()
{
var num = int.Parse(Console.ReadLine());
var numberOfPerm = 1;
var elements = Enumerable.Range(1, num).ToArray();
var workArr = Enumerable.Range(0, elements.Length + 1).ToArray();
PrintPerm(elements);
var index = 1;
while (index < elements.Length)
{
workArr[index]--;
var j = 0;
if (index % 2 == 1)
{
j = workArr[index];
}
SwapInts(ref elements[j], ref elements[index]);
index = 1;
while (workArr[index] == 0)
{
workArr[index] = index;
index++;
}
numberOfPerm++;
PrintPerm(elements);
}
Console.WriteLine($"Total permutations: {numberOfPerm}");
}
private static void PrintPerm(int[] elements)
{
Console.WriteLine(string.Join(", ", elements));
}
private static void SwapInts(ref int a, ref int b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
How to generate Permutations with repetition recursively in C#
// 1: [6, 1, 1, 1, 1, 1, 1, 1, 1]
// 2: [1, 6, 1, 1, 1, 1, 1, 1, 1]
// 3: [1, 1, 6, 1, 1, 1, 1, 1, 1]
// 4: [1, 1, 1, 6, 1, 1, 1, 1, 1]
// 5: [1, 1, 1, 1, 6, 1, 1, 1, 1]
// 6: [1, 1, 1, 1, 1, 6, 1, 1, 1]
// 7: [1, 1, 1, 1, 1, 1, 6, 1, 1]
// 8: [1, 1, 1, 1, 1, 1, 1, 6, 1]
// 9: [1, 1, 1, 1, 1, 1, 1, 1, 6]
using System;
public static class PermutationsWithRep
{
private static int numberOfCombos;
public static void Main()
{
var collection = new[] { 6, 1, 1, 1, 1, 1, 1, 1, 1 };
PermuteRep(collection);
}
private static void PermuteRep<T>(T[] workArray, int? end = null, int start = 0)
where T : IComparable<T>
{
if (end == null)
{
end = workArray.Length - 1;
}
PrintPerm(workArray);
for (int left = end.Value - 1; left >= start; left--)
{
for (int right = left + 1; right <= end; right++)
if (workArray[left].CompareTo(workArray[right]) != 0)
{
Swap(ref workArray[left], ref workArray[right]);
PermuteRep(workArray, end, left + 1);
}
var firstElement = workArray[left];
for (int i = left; i <= end.Value - 1; i++)
{
workArray[i] = workArray[i + 1];
}
workArray[end.Value] = firstElement;
}
}
private static void Swap<T>(ref T a, ref T b)
{
var temp = a;
a = b;
b = temp;
}
private static void PrintPerm<T>(T[] arr)
{
Console.WriteLine($"{++numberOfCombos}: [{string.Join(", ", arr)}]");
}
}
How to generate Variations with repetition recursively in C#
// 1: [0, 0]
// 2: [0, 1]
// 3: [0, 2]
// 4: [1, 0]
// 5: [1, 1]
// 6: [1, 2]
// 7: [2, 0]
// 8: [2, 1]
// 9: [2, 2]
using System;
public static class VariationsWithRep
{
private static int numberOfCombos;
private static int n;
private static int k;
private static int[] workArr;
public static void Main()
{
n = 3;
k = 2;
workArr = new int[k];
GenerateVariationsWithRep();
}
private static void GenerateVariationsWithRep(int index = 0)
{
if (index >= k)
{
PrintCombo();
return;
}
for (int i = 0; i < n; i++)
{
workArr[index] = i;
GenerateVariationsWithRep(index + 1);
}
}
private static void PrintCombo()
{
Console.WriteLine($"{++numberOfCombos}: [{string.Join(", ", workArr)}]");
}
}
How to generate Variations without repetition recursively in C#
using System;
using System.Linq;
class VariationsWithoutRepetition
{
const int k = 2;
const int n = 4;
static int[] arr = new int[k];
static int[] free = Enumerable.Range(1, 4).ToArray();
static void Main()
{
GenerateVariationsNoRepetitions(0);
}
static void GenerateVariationsNoRepetitions(int index)
{
if (index >= k)
{
PrintVariations();
}
else
{
for (int i = index; i < n; i++)
{
arr[index] = free[i];
Swap(ref free[i], ref free[index]);
GenerateVariationsNoRepetitions(index + 1);
Swap(ref free[i], ref free[index]);
}
}
}
private static void Swap<T>(ref T v1, ref T v2)
{
T old = v1;
v1 = v2;
v2 = old;
}
static void PrintVariations()
{
Console.WriteLine("(" + string.Join(", ", arr) + ")");
}
}
// result:
// (1, 2)
// (1, 3)
// (1, 4)
// (2, 1)
// (2, 3)
// (2, 4)
// (3, 2)
// (3, 1)
// (3, 4)
// (4, 2)
// (4, 3)
// (4, 1)
How to generate Permutations without repetition recursively in C#
using System;
class GroupPermutations
{
static void Main(string[] args)
{
string[] array = { "apple", "peach", "orange" };
Perm(array, 0);
}
static void Perm<T>(T[] arr, int k)
{
if (k >= arr.Length)
Print(arr);
else
{
Perm(arr, k + 1);
for (int i = k + 1; i < arr.Length; i++)
{
Swap(ref arr[k], ref arr[i]);
Perm(arr, k + 1);
Swap(ref arr[k], ref arr[i]);
}
}
}
private static void Swap<T>(ref T item1, ref T item2)
{
T temp = item1;
item1 = item2;
item2 = temp;
}
private static void Print<T>(T[] arr)
{
Console.WriteLine("{" + string.Join(", ", arr) + "}");
}
}
//Result:
//{apple, peach, orange}
//{apple, orange, peach}
//{peach, apple, orange}
//{peach, orange, apple}
//{orange, peach, apple}
//{orange, apple, peach}
How to generate all subsets of power set using bitwise mask in C#
namespace SubsetsOfSet
{
using System;
using System.Collections.Generic;
using System.Linq;
class SubsetsOfSet
{
static void Main()
{
int[] nums = { 0, 1, 2 };
string[] fruits = {"apple", "peach", "starwberry"};
int b = nums.Length;
int n = (int)Math.Pow(2, b);
for (int num = 0; num < n; num++)
{
var subSet = new List<int>();
for (int bit = 0; bit <= b; bit++)
{
if ((num >> bit & 1) == 1)
{
subSet.Add(nums[bit]);
}
}
Console.WriteLine("{{{0}}}", string.Join(", ", subSet.Select(i => fruits[i])));
}
}
}
}