Combinations of sequence elements

Combinatorics • Arrangements • Permutations

22.09.2021

Consider a problem where you need to get all possible combinations of sequence elements, in which the number of elements in the combination does not exceed a given maximum, and let’s write a method for solving in Java with the appropriate filter for the minimum and maximum number of elements.

Table setting problem • Method for solving in Java

An arrangement is an ordered set of {k} distinct elements from a set of {n} distinct elements, where {k ≤ n}. If {k = n}, then this ordered set is a permutation. For the universality of the solution, we’ll also consider permutations as a special case of arrangement.

Number of possible combinations #

For clarity, we’ll take a sequence of three elements {XYZ}, draw all possible subsets of this set, add permutations to them and calculate the number of combinations.

We get the number of all possible arrangements of the sequence elements

Formula for the number of arrangements:

Sequence of three elements:

Implementation in Java:

public static void main(String[] args) {
    // number of sequence elements
    int n = 3;
    // number of possible combinations
    int sum = 0;
    // bypass the possible numbers of elements
    for (int k = 0; k <= n; k++)
        // add up the numbers of arrangements
        sum += factorial(n) / factorial(n - k);
    // output
    System.out.println(sum); // 16
}
// factorial of a number
static int factorial(int n) {
    int fact = 1;
    for (int i = 2; i <= n; i++)
        fact *= i;
    return fact;
}

Combinations of three elements #

Let’s compare two sequences of three elements: digits {123} and letters {XYZ}. The type of elements is different — combinations are the same, because the sequence numbers of the elements are the same.

number of variants: 16
[][1][2][3][12][13][21][23][31][32][123][132][213][231][312][321]
[][X][Y][Z][XY][XZ][YX][YZ][ZX][ZY][XYZ][XZY][YXZ][YZX][ZXY][ZYX]

Let’s compare sequences of [1..12] elements: the number of variants grows rapidly and soon goes beyond the Integer, then for {n > 12} you will need to use Long, and when {n > 20} — already BigInteger.

n number of variants
1 2
2 5
3 16
4 65
5 326
6 1957
7 13700
8 109601
9 986410
10 9864101
11 108505112
12 1302061345

Consider a problem where you need to limit the possible variants by the maximum number of elements contained in them.

Table setting problem #

Four guests are invited to dinner {n = 4}, of whom it is known that no more than two people will arrive {k = 2}, and the order of their appearance is important, since the table setting depends on it. It is also known that when the first one arrives, this person will say who will be the second and whether this person will arrive. Calculate the possible variants for table setting.

Solution approach #

Let’s write a method in Java for solving such problems, which will take three parameters as input: sequence size, minimum and maximum number of elements in a combination. The method will return a list of combinations of specified length.

static List<Set<Integer>> combinationsOfElements(int size, int min, int max)

We call the method with the selection {min=0; max=2} and get a list of combinations of specified length.

// table setting problem
public static void main(String[] args) {
    // four guests are invited
    int[] arr = {1, 2, 3, 4};
    // n - number of elements in a sequence
    // k - maximum number of elements in a combination
    int n = 4, k = 2;
    // combinations of elements of specified length [0..2]
    List<Set<Integer>> list = combinationsOfElements(n, 0, k);
    // output
    System.out.println("number of variants: " + list.size());
    for (Set<Integer> set : list) {
        System.out.print("[");
        for (int i : set)
            System.out.print(arr[i]);
        System.out.print("]");
    }
}

Output:

number of variants: 17
[][1][2][3][4][12][13][14][21][23][24][31][32][34][41][42][43]

Combinations of elements of specified length #

We write a method in Java using three nested for loops. Next, to check, we call this method without selection {min=0; max=size} and get all possible combinations. For example, let’s take two sequences of three elements: digits {123} and letters {XYZ}.

Method description #

We prepare two lists of combinations: the resulting list and the current list. In the current list, the number of elements in all combinations will be the same. The maximum number of elements in a combination is the size of the sequence. We start with one empty combination and gradually increase the number of elements.

We bypass the possible number of elements and supplement the current combinations with those indices that are not yet included. At each step, we increase the current number of elements in the combinations by one and, if it gets into selection, then we add these combinations to the result.

/**
 * @param size the sequence size (0 ≤ min ≤ max ≤ size)
 * @param min  minimum number of elements in a combination
 * @param max  maximum number of elements in a combination
 * @return combinations of elements of specified length
 */
static List<Set<Integer>> combinationsOfElements(int size, int min, int max) {
    // invalid incoming data, return an empty list of combinations
    if (0 > min || min > max || max > size) return Collections.emptyList();
    // resulting list of combinations
    List<Set<Integer>> result = new ArrayList<>();
    // current list of combinations, number of elements in all
    // combinations is the same, start with one empty combination
    List<Set<Integer>> sublist = Arrays.asList(Collections.<Integer>emptySet());
    // bypass the possible number of elements in a combination
    for (int l = 0; l < Math.min(size, max); l++) {
        // if current number of elements gets into selection,
        // then add these combinations to the result
        if (l >= min) result.addAll(sublist);
        // next list of combinations
        List<Set<Integer>> nSublist = new ArrayList<>();
        // bypass the current list of combinations
        for (Set<Integer> comb : sublist) {
            // bypass the indexes of the sequence elements
            for (int i = 0; i < size; i++) {
                // skip those indexes that already present
                if (comb.contains(i)) continue;
                // new combination, copy the current one
                Set<Integer> nComb = new LinkedHashSet<>(comb);
                // adding the current index
                nComb.add(i);
                // add in a new list of combinations
                nSublist.add(nComb);
            }
        }
        // update the current list of combinations
        sublist = nSublist;
    }
    // add the current list of combinations to the result
    result.addAll(sublist);
    // return the final result
    return result;
}

// start the program and output the result
public static void main(String[] args) {
    // two sequences of three elements
    Integer[] arr1 = {1, 2, 3};
    String[] arr2 = {"X", "Y", "Z"};
    // number of sequence elements
    int n = 3;
    // all possible combinations of elements [0..n]
    List<Set<Integer>> list = combinationsOfElements(n, 0, n);
    // output
    System.out.println("number of variants: " + list.size());
    for (Object[] arr : Arrays.asList(arr1, arr2)) {
        StringBuilder sb = new StringBuilder();
        for (Set<Integer> set : list) {
            sb.append("[");
            for (int i : set) sb.append(arr[i]);
            sb.append("]");
        }
        System.out.println(sb);
    }
}

The output for this code see above: combinations of three elements.