Class Combinatorics

Namespace

PAC.Maths

A collection of common combinatorial functions, such as computing factorials or generating all permutations of a set.

public static class Combinatorics

Inheritance

object

Combinatorics

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

BinomialCoefficient(int, int)

The coefficient of x^k in (x + 1)^n. An alias for Choose(int, int).

public static int BinomialCoefficient(int n, int k)

Parameters

n int

k int

Returns

int

See Also

Choose(int, int)

Choose(int, int)

The choose function. An alias for BinomialCoefficient(int, int).

public static int Choose(int n, int k)

Parameters

n int

k int

Returns

int

See Also

BinomialCoefficient(int, int)

Factorial(int)

Computes n * (n - 1) * ... * 2 * 1. Returns 1 if n is 0.

public static int Factorial(int n)

Parameters

n int

Returns

int

FallingFactorial(int, int)

Computes n * (n - 1) * ... * (n - (k - 1)). Returns 1 if k is 0.

public static int FallingFactorial(int n, int k)

Parameters

n int

k int

Returns

int

MultiChoose(int, int)

public static int MultiChoose(int n, int k)

Parameters

n int

k int

Returns

int

NumberOfCombinations(int)

public static int NumberOfCombinations(int sizeOfSet)

Parameters

sizeOfSet int

Returns

int

NumberOfCombinations(int, int)

public static int NumberOfCombinations(int numElementsToChooseFrom, int lengthOfCombination)

Parameters

numElementsToChooseFrom int

lengthOfCombination int

Returns

int

NumberOfMultisets(int)

public static int NumberOfMultisets(int sizeOfSet)

Parameters

sizeOfSet int

Returns

int

NumberOfMultisets(int, int)

public static int NumberOfMultisets(int numElementsToChooseFrom, int sizeOfMultiset)

Parameters

numElementsToChooseFrom int

sizeOfMultiset int

Returns

int

NumberOfPermutations(int)

The number of possible permutations of a set of the given size. (Permutations do not allow repeated elements.)

public static int NumberOfPermutations(int sizeOfSet)

Parameters

sizeOfSet int

Returns

int

NumberOfPermutations(int, int)

The number of possible permutations of the given length with elements in a set of the given size. (Permutations do not allow repeated elements.)

public static int NumberOfPermutations(int numElementsToChooseFrom, int lengthOfPermutation)

Parameters

numElementsToChooseFrom int

lengthOfPermutation int

Returns

int

NumberOfTuples(int, int)

The number of possible tuples of the given length with elements in a set of the given size. (Tuples allow repeated elements.)

public static int NumberOfTuples(int numElementsToChooseFrom, int lengthOfTuple)

Parameters

numElementsToChooseFrom int

lengthOfTuple int

Returns

int

Pairs<T>(IEnumerable<T>)

Lazily generates all possible pairs (x, y) with x and y in the given IEnumerable<T>. x and y don't have to be distinct.

public static IEnumerable<(T first, T second)> Pairs<T>(this IEnumerable<T> set)

Parameters

set IEnumerable<T>

Returns

IEnumerable<(T first, T second)>

Type Parameters

T

Remarks

If the given IEnumerable<T> has duplicate elements, those elements will be treated as though they were distinct.

For a description of the order in which the pairs are yielded, see Tuples<T>(IEnumerable<T>, int).

Pairs<TFirst, TSecond>(IEnumerable<TFirst>, IEnumerable<TSecond>)

Lazily generates all possible pairs (x, y) with x in first and y in second.

public static IEnumerable<(TFirst first, TSecond second)> Pairs<TFirst, TSecond>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second)

Parameters

first IEnumerable<TFirst>

second IEnumerable<TSecond>

Returns

IEnumerable<(TFirst first, TSecond second)>

Type Parameters

TFirst

TSecond

Remarks

If a given IEnumerable<T> has duplicate elements, those elements will be treated as though they were distinct.

For a description of the order in which the pairs are yielded, see Tuples<T>(IEnumerable<T>, int).

Permutations<T>(IEnumerable<T>)

Lazily generates all possible permutations of the elements in the given IEnumerable<T>. (Permutations do not allow repeated elements.)

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> elements)

Parameters

elements IEnumerable<T>

Returns

IEnumerable<IEnumerable<T>>

Type Parameters

T

Remarks

If the given IEnumerable<T> has duplicate elements, they will be treated as though they were distinct.

Permutations<T>(IEnumerable<T>, int)

Lazily generates all possible permutations of the given length with elements in the given IEnumerable<T>. (Permutations do not allow repeated elements.)

public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> elements, int length)

Parameters

elements IEnumerable<T>

length int

Returns

IEnumerable<IEnumerable<T>>

Type Parameters

T

Remarks

If the given IEnumerable<T> has duplicate elements, they will be treated as though they were distinct.

RisingFactorial(int, int)

Computes n * (n + 1) * ... * (n + (k - 1)). Returns 1 if k is 0.

public static int RisingFactorial(int n, int k)

Parameters

n int

k int

Returns

int

Triples<T>(IEnumerable<T>)

Lazily generates all possible triples (x, y, z) with x, y and z in the given IEnumerable<T>. x, y and z don't have to all be distinct.

public static IEnumerable<(T first, T second, T third)> Triples<T>(this IEnumerable<T> set)

Parameters

set IEnumerable<T>

Returns

IEnumerable<(T first, T second, T third)>

Type Parameters

T

Remarks

If the given IEnumerable<T> has duplicate elements, those elements will be treated as though they were distinct.

For a description of the order in which the triples are yielded, see Tuples<T>(IEnumerable<T>, int).

Triples<TFirst, TSecond, TThird>(IEnumerable<TFirst>, IEnumerable<TSecond>, IEnumerable<TThird>)

Lazily generates all possible triples (x, y, z) with x in first, y in second and z in third.

public static IEnumerable<(TFirst first, TSecond second, TThird third)> Triples<TFirst, TSecond, TThird>(this IEnumerable<TFirst> first, IEnumerable<TSecond> second, IEnumerable<TThird> third)

Parameters

first IEnumerable<TFirst>

second IEnumerable<TSecond>

third IEnumerable<TThird>

Returns

IEnumerable<(TFirst first, TSecond second, TThird third)>

Type Parameters

TFirst

TSecond

TThird

Remarks

If a given IEnumerable<T> has duplicate elements, those elements will be treated as though they were distinct.

For a description of the order in which the triples are yielded, see Tuples<T>(IEnumerable<T>, int).

Tuples<T>(IEnumerable<T>, int)

Lazily generates all possible tuples of the given length with elements in the given IEnumerable<T>. (Tuples allow repeated elements.)

public static IEnumerable<IEnumerable<T>> Tuples<T>(this IEnumerable<T> elements, int length)

Parameters

elements IEnumerable<T>

length int

Returns

IEnumerable<IEnumerable<T>>

Type Parameters

T

Remarks

If the given IEnumerable<T> has duplicate elements, they will be treated as though they were distinct.

The order of the tuples will be lexicographic based on the order in which the elements appear in the input, with the left-most coordinate being the most significant. This is equivalent to using nested foreach loops, with a loop being less nested corresponding to a further-left coordinate.

For example, the tuples of length 2 with elements in { 0, 1 } will be in the order { { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } }. This is equivalent to

foreach (int element1 in set)
{
    foreach (int element2 in set)
    {
        yield return new int[] { element1, element2 };
    }
}