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);
}
}
Tag: algorithm
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 fill matrix in spiral order Java
public class SpiralMatrix {
public static void main(String[] args) {
int[][] matrix = new int[7][7];
int top = 0;
int bottom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
int index = 1;
while (left <= right && top <= bottom) {
for (int col = left; col <= right; col++) {
matrix[top][col] = index++;
}
top++;
for (int row = top; row <= bottom; row++) {
matrix[row][right] = index++;
}
right--;
for (int col = right; col >= left ; col--) {
matrix[bottom][col] = index++;
}
bottom--;
for (int row = bottom; row >= top ; row--) {
matrix[row][left] = index++;
}
left++;
}
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
System.out.printf("%02d ", matrix[row][col]);
}
System.out.println();
}
// result:
// 01 02 03 04 05 06 07
// 24 25 26 27 28 29 08
// 23 40 41 42 43 30 09
// 22 39 48 49 44 31 10
// 21 38 47 46 45 32 11
// 20 37 36 35 34 33 12
// 19 18 17 16 15 14 13
}
}
How to generate Eratosthenes sieve in Java
public class EratosthenesSieve {
public static final int MAX = 121;
public static void main(String[] args) {
boolean[] primes = new boolean[MAX];
eratosthenesSieve(primes);
System.out.printf("Primes in range [2..%d] are: ", MAX);
for (int i = 2; i < MAX; i++) {
if(primes[i]) {
System.out.printf(i + " ");
}
}
}
private static void eratosthenesSieve(boolean[] primes) {
for (int i = 2; i < primes.length; i++) {
primes[i] = true;
}
for (int i = 2; i < Math.sqrt(MAX); i++) {
if (primes[i]) {
for (int j = i * i; j < MAX; j += i) {
primes[j] = false;
}
}
}
}
}
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])));
}
}
}
}