Package de.rwth.swc.coffee4j.algorithmic.util

Class Combinator

  • public final class Combinator
extends Object
    Utility methods used for combinatorial tasks in the context of combinatorial test generation.

    Uses the indexing schema introduced in CombinationUtil.

    • Method Detail

      • computeCartesianProduct

        public static List<int[]> computeCartesianProduct​(it.unimi.dsi.fastutil.ints.Int2IntMap parameters,
                                                  int combinationSize)
        Computes the full cartesian product of the given parameters. Each entry form the cartesian product is stored in an array of size combinationSize so that the combinations can be used for larger test inputs in later iterations of the IPOG algorithm.
        Parameters:
        parameters - the parameters for whose values the cartesian product shall be computed. Must no be null or empty
        combinationSize - the size of the combinations returned. Empty places are filled with CombinationUtil.NO_VALUE. Must not be smaller than the number of parameters
        Returns:
        all tuples of the cartesian product
        Throws:
        NullPointerException - if parameters are null
        IllegalArgumentException - if there are no parameters or if the combinationsSize is too small

      • computeParameterCombinations

        public static List<it.unimi.dsi.fastutil.ints.IntSet> computeParameterCombinations​(int[] parameters,
                                                                                   int size)
        Computes all subsets of parameter indices with the given size. For example if the parameters 1, 2, 3, and 4 are given and the specified size is 2, the parameters subsets (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) are returned.
        Parameters:
        parameters - the set of parameters for which all subsets shall be generated. Must not be null
        size - the size of the returned subsets. Must not be negative or greater than the number of parameters
        Returns:
        all subsets of parameters of the given size. If the size is zero, an empty list is returned
        Throws:
        NullPointerException - if parameters are null
        IllegalArgumentException - if the size is negative or too large

      • computeNegativeParameterCombinations

        public static List<it.unimi.dsi.fastutil.ints.IntSet> computeNegativeParameterCombinations​(int[] parameters,
                                                                                           int[] negativeParameters,
                                                                                           int strengthA,
                                                                                           int strengthB)
        Computes (a,b)-wise subsets of parameter indices

        For example with a unary error-constraint, f( [0, 1, 2, 3], [ 0 ], 1, 0) == { (0) } f( [0, 1, 2, 3], [ 0 ], 1, 1) == { (0, 1), (0, 2), (0, 3) } f( [0, 1, 2, 3], [ 0 ], 1, 2) == { (0, 1, 2), (0, 1, 3), (0, 2, 3) } f( [0, 1, 2, 3], [ 0 ], 1, 3) == { (0, 1, 2, 3) } f( [0, 1, 2, 3], [ 0 ], 1, 4) == { (0, 1, 2, 3) } f( [0, 1, 2, 3], [ 0 ], 1, 5) == { (0, 1, 2, 3) }

        Another example with a binary error-constraint, f( [0, 1, 2, 3], [ 2, 3 ], 1, 0) == { (2), (3) } f( [0, 1, 2, 3], [ 2, 3 ], 2, 0) == { (2, 3) } f( [0, 1, 2, 3], [ 2, 3 ], 1, 1) == { (2, 0), (2, 1), (3, 0), (3, 1) } f( [0, 1, 2, 3], [ 2, 3 ], 2, 1) == { (2, 3, 0), (2, 3, 1) } f( [0, 1, 2, 3], [ 2, 3 ], 1, 2) == { (2, 0, 1), (3, 0, 1) } f( [0, 1, 2, 3], [ 2, 3 ], 2, 2) == { (2, 3, 0, 1) }

        Parameters:
        parameters - the set of parameters for which all subsets shall be generated. Must not be null
        negativeParameters - the set of parameters that is involved in the error-constraint. Must not be null
        strengthA - the interaction strength for negativeParameters
        strengthB - the interaction stregth for the subset of not-negativeParameters
        Returns:
        all subsets of parameters of size strengthA + strengthB
        Throws:
        NullPointerException - if parameters are null
        IllegalArgumentException - if parameter sizes are illegal

      • computeCombinations

        public static Set<int[]> computeCombinations​(int[] parameterSizes,
                                             it.unimi.dsi.fastutil.ints.IntSet parameters)
        Computes all possible combinations as partial test cases which only contain the given parameters.

        For example, given an input of [2, 3, 4, 5] and {0, 2}, all combinations between the first and third parameters are computed: [0, -1, 0, -1], [0, -1, 1, -1], [0, -1, 2, -1], [0, -1, 3, -1], [1, -1, 0, -1], [1, -1, 1, -1], [1, -1, 2, -1], [1, -1, 3, -1]

        Parameters:
        parameterSizes - the sizes of all parameters. This actually only needs to contain the sizes of the parameters which are referenced in the set of given parameters. Must not be null or empty
        parameters - the parameters of which to build the cartesian product of combinations. Must not be null or empty and must only contain valid indices of parameterSizes
        Returns:
        the cartesian product of the referenced parameter values with the other values left empty

      • computeCombinations

        public static Set<int[]> computeCombinations​(int[] parameters,
                                             int size)
        Computes all size-value-combinations there are with the given parameters. For example, for the given parameters [2, 2, 2] (three parameters with 2 values each) and size 2, the following combinations are returned: [0, 0, -1] [0, 1, -1] [1, 0, -1] [1, 1, -1] [0, -1, 0] [0, -1, 1] [1, -1, 0] [1, -1, 1] [-1, 0, 0] [-1, 0, 1] [-1, 1, 0] [-1, 1, 1]
        Parameters:
        parameters - all parameters. They are defined as their number of values. So [2, 3] means the first parameter has two values, and the second one has three. Must not be null
        size - the size of sub-combinations of values in the parameters that are calculated
        Returns:
        all sub-combinations of the values with the given size as demonstrated above. The order of combinations is not defined and may change in subsequent implementations. In any combinations the values for parameters are ordered the same way as the parameters supplied to the method

      • computeSubCombinations

        public static List<int[]> computeSubCombinations​(int[] combination,
                                                 int size)
        Computes all sub-combinations with the given size that the combination has. The combinations is allowed to have values not set. For example, [-1, 2, 3, 1, -1, 3] called with 2 would return [-1, 2, 3, -1, -1, -1] [-1, 2, -1, 1, -1, -1] [-1, 2, -1, -1, -1, 3] [-1, -1, 3, 1, -1, -1] [-1, -1, 3, -1, -1, 3] [-1, -1, -1, 1, -1, 3]
        Parameters:
        combination - a combination. Must not be null
        size - the size of sub-combinations. Must be positive
        Returns:
        all sub-combinations with the given size of the combinations. No order is guaranteed. The parameters are in the same order as with the given combination

      • computeSubCombinations

        public static List<int[]> computeSubCombinations​(int[] combination)
        Computes all sub-combinations of this combination. This returns the same result as calling computeCombinations(int[], int) with sizes from 1 to combinations.length.
        Parameters:
        combination - a combination. Must not be null but can have unset values
        Returns:
        all sub-combinations (including the combination itself)