Package com.amalgamasimulation.core.combinatorics

Interface Combinatorics

public interface Combinatorics
The Combinatorics interface defines a collection of methods for generating various combinatorial structures, such as Cartesian products, combinations, and subsets from given lists of elements. These methods are designed to support both eager and lazy generation of results, allowing for efficient handling of combinatorial problems even with large data sets.
Author:
Andrey Malykhanov

  • Method Summary

    Static Methods
    Modifier and Type
    Method
    Description
    static <T> List<List<T>>
    cartesianProduct(List<? extends List<? extends T>> elementLists)
    Creates a list of all possible combinations (Cartesian product) of the elements from the provided lists.
    static <T> Stream<List<T>>
    cartesianProductStream(List<? extends List<? extends T>> elementLists)
    Returns a stream of all possible combinations (Cartesian product) of the elements from the provided lists.
    static <T> List<List<T>>
    combinations(List<T> elements, int combinationSize)
    Creates a list of all possible combinations of a specified size from the given list of elements.
    static <T> Stream<List<T>>
    combinationsStream(List<? extends T> elements, int combinationSize)
    Returns a stream of all possible combinations of a specified size from the given list of elements.
    static <T> List<List<T>>
    permutations(List<T> elements)
    Creates a list of all possible permutations of the provided list of elements.
    static <T> Stream<List<T>>
    permutationsStream(List<T> elements)
    Returns a stream of all possible permutations of the provided list of elements.
    static <T> List<List<T>>
    subsets(List<T> elements)
    Creates a list of all possible subsets of the provided list of elements.
    static <T> Stream<List<T>>
    subsetsStream(List<? extends T> elements)
    Returns a stream of all possible subsets of the provided list of elements.
    static <T> List<T>
    union(List<? extends T>... lists)
    Concatenates several lists into a single list.

  • Method Details

    • cartesianProductStream

      static <T> Stream<List<T>> cartesianProductStream(List<? extends List<? extends T>> elementLists)
      Returns a stream of all possible combinations (Cartesian product) of the elements from the provided lists. Each combination is a list containing one element from each of the provided lists. The stream does not compute the combinations in advance, allowing for efficient processing of large lists with potentially many combinations.

      For example, given two lists ["1", "2"] and ["A", "B"], the Cartesian product would be [["1", "A"], ["1", "B"], ["2", "A"], ["2", "B"]].

      Stream is ordered, its elements are ordered lexicographically.

      Type Parameters:
      T - the type of elements in the input lists and the combinations
      Parameters:
      elementLists - a list of lists, where each list contains elements of type T. It is the source from which the Cartesian product is computed.
      Returns:
      a Stream of List objects, where each list represents a possible combination from the Cartesian product of the input lists. The stream is lazily populated, meaning combinations are generated on-demand

    • cartesianProduct

      static <T> List<List<T>> cartesianProduct(List<? extends List<? extends T>> elementLists)
      Creates a list of all possible combinations (Cartesian product) of the elements from the provided lists. Each combination is a list containing one element from each of the provided lists. This method computes all combinations eagerly, meaning it constructs and stores the entire result in memory before returning. Therefore, it is best suited for scenarios with a manageable number of total combinations.

      For example, given two lists ["1", "2"] and ["A", "B"], the Cartesian product would be [["1", "A"], ["1", "B"], ["2", "A"], ["2", "B"]].

      Elements in the list are ordered lexicographically.

      The practical limit of input size is such that the output size is less than 10_000_000 elements. It typically takes 1 to 10 seconds to compute such result on a regular machine.

      Type Parameters:
      T - the type of elements in the input lists and the combinations
      Parameters:
      elementLists - a list of lists, where each list contains elements of type T. This is the source from which the Cartesian product is computed. The method does not modify the input lists. Cannot be null.
      Returns:
      a List of List objects, where each inner list represents a possible combination from the Cartesian product of the input lists. The method returns an empty list if elementLists is empty or if any of the input lists are empty.

    • combinationsStream

      static <T> Stream<List<T>> combinationsStream(List<? extends T> elements, int combinationSize)
      Returns a stream of all possible combinations of a specified size from the given list of elements. Each combination is a list of elements chosen from the input list, without repetition and regardless of order. The stream is generated lazily, meaning combinations are computed on-demand as the stream is consumed.

      For example, if the input list is [1, 2, 3] and combinationSize is 2, the result would include [1, 2], [1, 3], and [2, 3].

      Returned stream is ordered, its elements are ordered lexicographically.

      An empty stream is returned if combinationSize <= 0, or combinationSize > number of elements in the list

      Type Parameters:
      T - the type of elements in the input list and the generated combinations
      Parameters:
      elements - a list of elements of type T from which combinations are generated.
      combinationSize - the size of each combination, i.e. the number of elements in each list of the returned stream
      Returns:
      a Stream of List objects, each representing a combination of combinationSize elements from the input list. The stream does not include duplicate combinations

    • combinations

      static <T> List<List<T>> combinations(List<T> elements, int combinationSize)
      Creates a list of all possible combinations of a specified size from the given list of elements. Each combination is a list of elements chosen from the input list, without repetition and regardless of order. This method computes the combinations eagerly; the combinations are returned as a list of lists, where each inner list represents a unique combination of elements.

      For example, if the input list is [1, 2, 3] and combinationSize is 2, the result would include [1, 2], [1, 3], and [2, 3].

      Elements in the returned list are ordered lexicographically.

      The practical limit of input size is calculating all possible combinations of 13 elements from a list of 27 elements which produces a resulting list containing 20_058_300 elements. It typically takes 5 to 15 seconds to compute such result on a regular machine.

      An empty list is returned if combinationSize <= 0, or combinationSize > number of elements in the list

      Type Parameters:
      T - the type of elements in the input list and the generated combinations
      Parameters:
      elements - a list of elements of type T from which combinations are generated.
      combinationSize - the size of each combination, i.e. the number of elements in each list of the returned list
      Returns:
      a List of List<T> where each inner list is a combination of combinationSize elements from elements.

    • subsetsStream

      static <T> Stream<List<T>> subsetsStream(List<? extends T> elements)
      Returns a stream of all possible subsets of the provided list of elements. Each subset is represented as a list of elements, and the stream includes all subsets ranging from the empty set to the full set of the input list. The subsets are generated lazily, meaning they are computed on-demand as the stream is consumed, which allows for efficient processing of sets with a large number of subsets.

      For example, if the input list is [1, 2], the result would include [], [1], [2], and [1, 2].

      Returned stream is ordered, order of elements is always the same for the same input. Order of elements in every returned subset is the same as in the original list.

      Type Parameters:
      T - the type of elements in the input list and the generated subsets
      Parameters:
      elements - a list of elements of type T from which subsets are generated
      Returns:
      a Stream of List objects, where each list represents a subset of the input list, ranging from the empty set to the full set. The stream is generated lazily

    • subsets

      static <T> List<List<T>> subsets(List<T> elements)
      Creates a list of all possible subsets of the provided list of elements. Each subset is represented as a list of elements, and the list includes all subsets ranging from the empty set to the full set of the input list. This method computes the subsets eagerly.

      For example, if the input list is [1, 2], the result would include [], [1], [2], and [1, 2].

      Returned list is ordered, order of elements is always the same for the same input. Order of elements in every returned subset is the same as in the original list.

      The practical limit of input size for this method is a list of 25 elements, which produces the result with 33_554_432 elements. Such calculation typically takes 5 to 10 seconds on a regular machine.

      Type Parameters:
      T - the type of elements in the input list and the generated subsets
      Parameters:
      elements - a list of elements of type T from which the subsets are generated
      Returns:
      a List of List objects, where each inner list represents a subset of the input list, ranging from the empty set to the full set

    • permutationsStream

      static <T> Stream<List<T>> permutationsStream(List<T> elements)
      Returns a stream of all possible permutations of the provided list of elements. Each permutation is represented as a list of elements, with each list containing all the elements of the input list in a unique order. The permutations are generated lazily, meaning they are computed on-demand as the stream is consumed. This allows for efficient processing of lists with a large number of permutations.

      For example, if the input list is [1, 2, 3], the result would include [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

      Returned stream is ordered, with permutations following the lexicographical order based on the order of elements in the original list.

      Type Parameters:
      T - the type of elements in the input list and the generated permutations
      Parameters:
      elements - a list of elements of type T from which permutations are generated
      Returns:
      a Stream of List objects, where each list represents a permutation of the input list. The stream is generated lazily

    • permutations

      static <T> List<List<T>> permutations(List<T> elements)
      Creates a list of all possible permutations of the provided list of elements. Each permutation is represented as a list of elements, with each list containing all the elements of the input list in a unique order. This method computes the permutations eagerly, meaning all permutations are constructed and stored in memory before being returned. This approach is suitable for scenarios where the total number of permutations is manageable and an immediate complete list of permutations is required.

      For example, if the input list is [1, 2, 3], the result would include [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

      The returned list is ordered, with permutations following the lexicographical order based on the order of elements in the original list.

      The practical limit of input size for this method is a list of 13 elements, and the number of permutations for such list is 6_227_020_800.

      Type Parameters:
      T - the type of elements in the input list and the generated permutations
      Parameters:
      elements - a list of elements of type T from which permutations are generated
      Returns:
      a List of List objects, where each inner list represents a permutation of the input list. The method returns an empty list if the input list is empty.

    • union

      @SafeVarargs static <T> List<T> union(List<? extends T>... lists)
      Concatenates several lists into a single list. A new list is created, so the original lists are not affected.
      Parameters:
      lists - lists to be combined into one list
      Returns:
      A single list that contains all elements from the lists