Skip to content

Combinatorics

Jump to bottom
Evgeny Vashchenko edited this page Dec 26, 2023 · 12 revisions

General

Here is an implementation of several basic combinatorial analysis methods for the .NET framework:

  • permutations generation
  • combinations generation
  • powerset (all subsets) generation

All combinatorial sequence generators implement the ICombinatorial<T> interface, which declares the following properties:

  • Elements (IReadOnlyList<T>) - returns an all-elements list of the main set.
  • Cardinality (Int32) - the cardinality of the main set of objects
  • Count (Int64) - the number of possible subsets generated by this combinatorial generator.
  • BigCount (BigInteger) - the big number of possible subsets generated by this combinatorial generator.
  • ApproxCount (Double) - the approximate number of possible subsets generated by this combinatorial generator and used for fast calculations on a large number of elements.

Also, this interface declares via inheritance the IEnumerable<IEnumerable<T>> interface to get generated sequences.

ICombinatorial<T> interface declaration 
public interface ICombinatorial<T> : IEnumerable<IEnumerable<T>>
{
  IReadOnlyList<T> Elements { get; }

  int Cardinality { get; }

  long Count { get; }

  BigInteger BigCount { get; }

  double ApproxCount { get; }
}

Combinatorial object generators with a fixed subset selection length implement the ICombinatorialWithSelection<T> interface which inherits the ICombinatorial<T> interface described above and declares a Selection (Int32) property pointing to a fixed selection length.

ICombinatorialWithSelection<T> interface declaration 
public interface ICombinatorialWithSelection<T> : ICombinatorial<T>
{
  int Selection { get; }
}

Combinatorial object generators with variable subset selection length specified by range implement the ICombinatorialWithMultiselection<T> interface which inherits the ICombinatorial<T> interface described above and declares MinSelection and MaxSelection (Int32) properties pointing to a selection length range.

ICombinatorialWithMultiselection<T> interface declaration 
public interface ICombinatorialWithMultiselection<T> : ICombinatorial<T>
{
  int MinSelection { get; }

  int MaxSelection { get; }
}

Below are base classes for various combinatorial objects:

  • Combinatorial<T> - class represents the base class for all described subset generators of a given set of elements of type T, and implements the ICombinatorial<T> interface.
  • CombinatorialWithSelection<T> - base class which inherits the Combinatorial<T> class and implements the ICombinatorialWithSelection<T> interface.
  • CombinatorialWithMultiselection<T> - base class which inherits the Combinatorial<T> class and implements the ICombinatorialWithMultiselection<T> interface.

Non-abstract classes of combinatorial object generators implement static methods for calculating the number of subsets generated by an instance of this class on a set with a specified cardinality and optional parameters specifying the selection. There are three methods, differing in accuracy and acceptable range of values:

  • Int64 CountOf(Int32 cardinality[,...]) – calculates the number of generated combinatorial subsets on a set with the cardinality specified by the cardinality parameter (an arithmetic operation overflow exception is generated if the resulting value exceeds the permissible range of values represented by the Int64 type);
  • BigInteger BigCountOf(Int32 cardinality[,...]) – calculates the number of generated combinatorial subsets on a set with cardinality specified by the cardinality parameter (used for exact calculation on any sets, including very large dimensions).
  • Double ApproxCountOf(Int32 cardinality[,...]) – calculates the approximate number of generated combinatorial subsets on a set with cardinality specified by the cardinality parameter (suitable for fast calculations with approximate accuracy on high-dimensional sets).

For the .NET framework, starting from version 7.0, such methods for calculating the number of subsets are declared as static in the following interfaces: ICombinatorialCountable, ICombinatorialWithSelectionCountable, ICombinatorialWithMultiselectionCountable, which are implemented by the classes described above.

ICombinatorialCountable interface declaration 
public interface ICombinatorialCountable
{
  static abstract long CountOf(int cardinality);

  static abstract BigInteger BigCountOf(int cardinality);

  static abstract double ApproxCountOf(int cardinality);
}
ICombinatorialWithSelectionCountable interface declaration 
public interface ICombinatorialWithSelectionCountable
{
  static abstract long CountOf(int cardinality, int selection);

  static abstract BigInteger BigCountOf(int cardinality, int selection);

  static abstract double ApproxCountOf(int cardinality, int selection);
}
ICombinatorialWithMultiselectionCountable interface declaration 
public interface ICombinatorialWithMultiselectionCountable
{
  static abstract long CountOf(int cardinality, int minSelection, int maxSelection);

  static abstract BigInteger BigCountOf(int cardinality, int minSelection, int maxSelection);

  static abstract double ApproxCountOf(int cardinality, int minSelection, int maxSelection);
}

Classes of combinatorial object generators without a generic parameter enumerate the corresponding subsets of elements of the main set with cardinality N from integers in the range 0…N-1. The cardinality of the main set is specified by the cardinality parameter (Int32) in the generator constructor.

Classes with a generic parameter of type T enumerate the corresponding subsets of elements of the main set with cardinality N using a specified list (IReadOnlyList<T>). Each element of a set is treated as unique using its position in the list rather than its value.

For some generator classes, the length of the sample of elements of the enumerated subsets can be specified. It can be specified either as a fixed value or as a range. Generators of combinatorial objects with a selection of elements with a fixed length are inherited from the base class CombinatorialWithSelection<T>. Generators of combinatorial objects with a selection of elements specified by a range are inherited from the base class CombinatorialWithMultiselection<T>.

Permutations

  • Permutations - enumerates all permutations of sample elements of fixed length K from the main set of dimension N integers from the range 0...N-1.

  • Permutations<T> - enumerates all permutations of a sample of fixed length K of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • PermutationsWithRepetition - enumerates all permutations with repetition of sample elements of a fixed length K from the main set of dimension N integers from the range 0...N-1.

  • PermutationsWithRepetition<T> - enumerates all permutations with repetition of the sample elements of a fixed length K of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • PermutationsWithMultiselection - enumerates all permutations of variable-length sample elements specified by the range Kmin...Kmax from the main set of dimension N integers from the range 0...N-1.

  • PermutationsWithMultiselection<T> - enumerates all permutations of selection elements of variable length specified by the range Kmin...Kmax of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • PermutationsWithRepetitionAndMultiselection - enumerates all permutations with repetition of sample elements of variable length specified by the range Kmin...Kmax from the main set of dimension N integers from the range 0...N-1.

  • PermutationsWithRepetitionAndMultiselection<T> - enumerates all permutations with repetition of selection elements of variable length specified by the range Kmin...Kmax of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

Combinations

  • Combinations - enumerates all combinations of elements of a fixed length K from the main set of dimension N integers from the range 0...N-1.

  • Combinations<T> - enumerates all combinations of sample elements of a fixed length K of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • CombinationsWithRepetition - enumerates all combinations with repetition of sample elements of a fixed length K from the main set of dimension N integers from the range 0...N-1.

  • CombinationsWithRepetition<T> - enumerates all combinations with repetition of sample elements of a fixed length K of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • CombinationsWithMultiselection - enumerates all combinations of sample elements of variable length specified by the range Kmin...Kmax from the main set of dimension N integers from the range 0...N-1.

  • CombinationsWithMultiselection<T> - enumerates all combinations of variable length selection elements specified by the range Kmin...Kmax of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

  • CombinationsWithRepetitionAndMultiselection - enumerates all combinations with repetition of sample elements of variable length specified by the range Kmin...Kmax from the main set of dimension N integers from the range 0...N-1.

  • CombinationsWithRepetitionAndMultiselection<T> - enumerates all combinations with repetition of selection elements of variable length specified by the range Kmin...Kmax of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.

Powerset

  • Powerset - enumerates all subsets of a given set of size N integers from the range 0…N-1.
  • Powerset<T> - enumerates all subsets of a given set of elements of type T defined by the list of the Elements (IReadOnlyList<T>) property.
Clone this wiki locally