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