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);
}
}
}
Tag: c#
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 Combinations with repetition recursively in C#
// 1: [0, 0]
// 2: [0, 1]
// 3: [0, 2]
// 4: [0, 3]
// 5: [1, 1]
// 6: [1, 2]
// 7: [1, 3]
// 8: [2, 2]
// 9: [2, 3]
// 10: [3, 3]
using System;
public static class CombinationsWithRep
{
private static int numberofCombos;
private static int n;
private static int k;
private static int[] storageArr;
public static void Main()
{
n = 4;
k = 2;
storageArr = new int[k];
GenCombinationsWithRep();
}
private static void GenCombinationsWithRep(int index = 0, int element = 0)
{
if (index >= storageArr.Length)
{
PrintCombo();
return;
}
for (int i = element; i < n; i++)
{
storageArr[index] = i;
GenCombinationsWithRep(index + 1, i);
}
}
private static void PrintCombo()
{
Console.WriteLine(
"{0,3}: [{1}]",
++numberofCombos,
string.Join(", ", storageArr));
}
}
How to generate Combinations without repetition recursively in C#
// 1: [0, 1]
// 2: [0, 2]
// 3: [0, 3]
// 4: [1, 2]
// 5: [1, 3]
// 6: [2, 3]
using System;
public static class CombinationsNoRep
{
private static int numberofCombos;
private static int n;
private static int k;
private static int[] storageArr;
public static void Main()
{
n = 4;
k = 2;
storageArr = new int[k];
GenCombinationsNoRep();
}
private static void GenCombinationsNoRep(int index = 0, int element = 0)
{
if (index >= storageArr.Length)
{
PrintCombo();
return;
}
for (int i = element; i < n; i++)
{
storageArr[index] = i;
GenCombinationsNoRep(index + 1, i + 1);
}
}
private static void PrintCombo()
{
Console.WriteLine(
"{0,3}: [{1}]",
++numberofCombos,
string.Join(", ", storageArr));
}
}
Generic BinaryHeap implementation with C#
namespace BinaryHeap
{
using System;
using System.Collections.Generic;
public class BinaryHeap<T> where T : IComparable<T>
{
private IList<T> heap;
public BinaryHeap(T[] elements = null)
{
if (elements != null)
{
this.heap = new List<T>(elements);
for (int i = elements.Length / 2; i >= 0; i--)
{
this.HeapifyDown(i);
}
}
else
{
this.heap = new List<T>();
}
}
public int Count
{
get
{
return this.heap.Count;
}
}
public T ExtractMax()
{
var max = this.heap[0];
this.heap[0] = this.heap[this.Count - 1];
this.heap.RemoveAt(this.Count - 1);
if (this.Count > 0)
{
this.HeapifyDown(0);
}
return max;
}
public T PeekMax()
{
var max = this.heap[0];
return max;
}
public void Insert(T node)
{
this.heap.Add(node);
this.HeapifyUp(this.Count - 1);
}
private void HeapifyDown(int i)
{
var leftChild = (i * 2) + 1;
var rightChild = (i * 2) + 2;
var biggest = i;
if (leftChild < this.Count && this.heap[leftChild].CompareTo(this.heap[biggest]) > 0)
{
biggest = leftChild;
}
if (rightChild < this.Count && this.heap[rightChild].CompareTo(this.heap[biggest]) > 0)
{
biggest = rightChild;
}
if (biggest != i)
{
T old = this.heap[i];
this.heap[i] = this.heap[biggest];
this.heap[biggest] = old;
this.HeapifyDown(biggest);
}
}
private void HeapifyUp(int i)
{
var parent = (i - 1) / 2;
while (i > 0 && this.heap[i].CompareTo(this.heap[parent]) > 0)
{
var temp = this.heap[parent];
this.heap[parent] = this.heap[i];
this.heap[i] = temp;
i = parent;
parent = (i - 1) / 2;
}
}
}
}