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.
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.
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;
}
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.
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.
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]
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
}.
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.
© Golovin G.G., Code with comments, translation from Russian, 2021