generic – VDonC#ev

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

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;
            }
        }
    }
}

Simple implementation of generic BINARY TREE in C#

using System;
public class BinaryTree
{
	public BinaryTree(
		T value,
		BinaryTree leftNode = null,
		BinaryTree rightNode = null)
	{
		this.Value = value;
		this.LeftNode = leftNode;
		this.RightNode = rightNode;
	}

	public T Value { get; private set; }

	public BinaryTree LeftNode { get; private set; }

	public BinaryTree RightNode { get; private set; }

	public void EachPreOrder(Action action)
	{
		action(this.Value);

		if (this.LeftNode != null)
		{
			this.LeftNode.EachPreOrder(action);
		}

		if (this.RightNode != null)
		{
			this.RightNode.EachPreOrder(action);
		}
	}

	public void EachInOrder(Action action)
	{
		if (this.LeftNode != null)
		{
			this.LeftNode.EachPreOrder(action);
		}

		action(this.Value);

		if (this.RightNode != null)
		{
			this.RightNode.EachPreOrder(action);
		}
	}

	public void EachPostOrder(Action action)
	{
		if (this.LeftNode != null)
		{
			this.LeftNode.EachPreOrder(action);
		}

		if (this.RightNode != null)
		{
			this.RightNode.EachPreOrder(action);
		}
		
		action(this.Value);
	}
}

Simple implementation of generic TREE in C#

using System;
using System.Collections.Generic;

public class Tree<T>
{
	public Tree(
		T value,
		params Tree<T>[] children)
	{
		this.Value = value;

		this.Children = new List<Tree<T>>();
		foreach (var child in children)
		{
			this.Children.Add(child);
		}
	}
		
	public T Value { get; private set; }

	public ICollection<Tree<T>> Children { get; private set; }

	public void EachTree(Action<T> action)
	{
		action(this.Value);

		foreach (var child in this.Children)
		{
			child.EachTree(action);
		}
	}

	public void PrintTree(int indent = 0)
	{
		Console.WriteLine(new string(' ', indent * 2) + this.Value);
		indent++;
		foreach (var child in this.Children)
		{
			child.PrintTree(indent);
		}
	}
}

Simple dynamic implementation of generic STACK in C#

using System;

public class LinkedStack<T>
{
	private LinkedStackNode<T> firstNode;

	public int Count { get; private set; }

	public void Push(T element)
	{
		var newNode = new LinkedStackNode<T>(element);

		newNode.NextNode = this.firstNode;
		this.firstNode = newNode;

		this.Count++;
	}

	public T Pop()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Stack is empty.");
		}

		var nodeToPop = this.firstNode;
		this.firstNode = this.firstNode.NextNode;
		this.Count--;

		return nodeToPop.Value;
	}

	public T Peek()
	{
		var nodeToPeek = this.firstNode;

		return nodeToPeek.Value;
	}

	public T[] ToArray()
	{
		var arr = new T[this.Count];
		var currentNode = this.firstNode;
		var arrIndex = 0;
		while (currentNode != null)
		{
			arr[arrIndex] = currentNode.Value;
			arrIndex++;
			currentNode = currentNode.NextNode;
		}

		return arr;
	}

	private class LinkedStackNode<T>
	{
		public LinkedStackNode(
			T value,
			LinkedStackNode<T> nextNode = null)
		{
			this.Value = value;
		}

		public T Value { get; private set; }

		public LinkedStackNode<T> NextNode { get; set; }
	}
}

Simple static implementation of generic STACK in C#

using System;

public class ArrayStack<T> : IArrayStack<T>
{
	private const int InitialCapacity = 16;

	private T[] internalStorage;
	private int capacity;

	public ArrayStack(int capacity = InitialCapacity)
	{
		this.Capacity = capacity;
		this.internalStorage = new T[this.Capacity];
	}

	public int Count { get; private set; }

	private int Capacity
	{
		get
		{
			return this.capacity;
		}

		set
		{
			if (value <= 0)
			{
				throw new ArgumentOutOfRangeException(
					nameof(value),
					"Capacity should be positive integer number.");
			}

			this.capacity = value;
		}
	}

	public void Push(T element)
	{
		if (this.GrowNeeded())
		{
			this.Grow();
		}

		this.internalStorage[this.Count] = element;
		this.Count++;
	}

	public T Pop()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Stack is empty.");
		}
		
		this.Count--;
		var element = this.internalStorage[this.Count];
		this.internalStorage[this.Count] = default(T);

		return element;
	}

	public T Peek()
	{
		var element = this.internalStorage[this.Count - 1];

		return element;
	}

	public T[] ToArray()
	{
		var arr = new T[this.Count];
		this.FillStorage(arr);
		Array.Reverse(arr);

		return arr;
	}

	private bool GrowNeeded()
	{
		var result = this.Count >= this.Capacity;

		return result;
	}

	private void Grow()
	{
		this.Capacity *= 2;
		var newStorage = new T[this.Capacity];
		this.FillStorage(newStorage);
		this.internalStorage = newStorage;
	}

	private void FillStorage(T[] array)
	{
		Array.Copy(this.internalStorage, array, this.Count);
	}
}

Simple dynamic implementation of generic QUEUE in C#

using System;

public class LinkedQueue<T>
{
	private LinkedQueueNode<T> start;
	private LinkedQueueNode<T> end;

	public LinkedQueue()
	{
		this.Count = 0;
	}

	public int Count { get; private set; }

	public void Enqueue(T element)
	{
		var newElement = new LinkedQueueNode<T>(element);

		if (this.Count == 0)
		{
			this.start = this.end = newElement;
		}
		else
		{
			this.end.Next = newElement;
			this.end = newElement;
		}

		this.Count++;
	}

	public T Dequeue()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var elementToReturn = this.start;
		this.start = this.start.Next;
		this.Count--;

		return elementToReturn.Value;
	}

	public T Peak()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var currentElement = this.start.Value;

		return currentElement;
	}

	public T[] ToArray()
	{
		var arrToReturn = new T[this.Count];
		var currentNode = this.start;
		var arrIndex = 0;
		while (currentNode != null)
		{
			arrToReturn[arrIndex] = currentNode.Value;
			arrIndex++;
			currentNode = currentNode.Next;
		}

		return arrToReturn;
	}
	
	private class LinkedQueueNode<T>
	{
		public LinkedQueueNode(T value)
		{
			this.Value = value;
		}

		public T Value { get; private set; }

		public LinkedQueueNode<T> Next { get; set; }
	}
}

Simple static implementation of generic QUEUE in C#

public class CircularQueue<T>
{
	private const int InitialCapacity = 16;

	private T[] storage;

	private int capacity;
	private int startIndex;
	private int endIndex;

	public CircularQueue(int capacity = InitialCapacity)
	{
		this.Capacity = capacity;
		this.storage = new T[this.Capacity];
	}

	public int Count { get; private set; }

	private int Capacity
	{
		get
		{
			return this.capacity;
		}

		set
		{
			if (value <= 0)
			{
				throw new ArgumentOutOfRangeException(
					nameof(value),
					"Queue capacity should be a positive integer");
			}

			this.capacity = value;
		}
	}

	public void Enqueue(T element)
	{
		if (this.GrowNeeded())
		{
			this.Grow();
		}

		this.storage[this.endIndex] = element;
		this.endIndex = (this.endIndex + 1) % this.Capacity;
		this.Count++;
	}

	public T Dequeue()
	{
		if (this.Count <= 0)
		{
			throw new InvalidOperationException("Queue is empty.");
		}

		var element = this.storage[this.startIndex];
		this.storage[this.startIndex] = default(T);
		this.startIndex = (this.startIndex + 1) % this.Capacity;
		this.Count--;

		return element;
	}

	public T[] ToArray()
	{
		var resultArray = new T[this.Count];
		this.ResizeArrayStorage(resultArray);

		return resultArray;
	}

	private bool GrowNeeded()
	{
		var result = this.Count >= this.Capacity;

		return result;
	}

	private void Grow()
	{
		var newStorage = new T[this.Capacity * 2];
		this.ResizeArrayStorage(newStorage);
		this.startIndex = 0;
		this.endIndex = this.Capacity;
		this.Capacity *= 2;

		this.storage = newStorage;
	}

	private void ResizeArrayStorage(T[] array)
	{
		for (int i = 0; i < this.Count; i++)
		{
			var currentIndex = (this.startIndex + i) % this.Capacity;
			array[i] = this.storage[currentIndex];
		}
	}
}

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}