Combinatorics

Combinatorics.cs

namespace Scripts;

public class Combinatorics
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(List<T> input, int i = 0)
    {
        if (i >= input.Count - 1)
        {
            yield return input.ToList();
        }
        else
        {
            foreach (var permutation in GetPermutations(input, i + 1))
            {
                yield return permutation;
            }

            for (int j = i + 1; j < input.Count; ++j)
            {
                (input[i], input[j]) = (input[j], input[i]);
                foreach (var permutation in GetPermutations(input, i + 1))
                {
                    yield return permutation;
                }
                (input[i], input[j]) = (input[j], input[i]);
            }
        }
    }

    public static IEnumerable<IEnumerable<T>> GetCombinations<T>(List<T> input, int count = 0)
    {
        List<T> buffer = new(count);
        foreach (var combination in GetCombinations(input, buffer, 0, count))
        {
            yield return combination;
        } 
    }

    private static IEnumerable<IEnumerable<T>> GetCombinations<T>(List<T> input, List<T> buffer, int offset, int count)
    {
        if (count == 0)
        {
            yield return buffer.ToList();
        }
        else
        {
            for (int i = offset; i <= input.Count - count; ++i)
            {
                buffer.Add(input[i]);
                foreach (var combination in GetCombinations(input, buffer, i + 1, count - 1))
                {
                    yield return combination;
                }
                buffer.RemoveAt(buffer.Count - 1);
            }
        }
    }
}