// (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;
}
}
}
}
Category: Combinatorics
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));
}
}
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}