Skip navigation links
The mathIT Library
A Java™ API for mathematics
org.mathIT.numbers

## Class Combinatorics

• ```public class Combinatorics
extends Object```
This class provides methods related to combinatorics. Examples are routines to generate all permutations or all combinations of a set.
Version:
1.0
Author:
Andreas de Vries
• ### Constructor Summary

Constructors
Constructor and Description
`Combinatorics()`
• ### Method Summary

All Methods
Modifier and Type Method and Description
`static boolean` ```isSurjective(int[] f, int k)```
Returns whether the mapping f: {0, 1, ..., n-1} → {0, 1, ..., k-1} is a surjection.
`static <T> ArrayList<T>` ```permutation(int k, ArrayList<T> s)```
For every number k with 0 ≤ k < n!
`static <T> T[][]` `permutations(Set<T> set)`
Returns all permutations of a set as a 2-dimensional array.
`static <T> T[][]` `permutations(T[] s)`
Returns all permutations of a sequence as a 2-dimensional array.
`static <T extends Comparable<T>>ArrayList<TreeSet<T>>` ```subsets(SortedSet<T> s, int k)```
Returns the k-element subsets of a set s, i.e., each k-element combination of s, stored in an array list.
`static ArrayList<int[]>` ```surjections(int n, int k)```
Returns a list of all surjections f: {0, 1, ..., n-1} → {0, 1 ..., k-1}, each one of which encoded as an array such that f(x) = `n[x]` ∈ {0, 1 ..., k-1}.
`static ArrayList<StringBuilder>` ```words(int k, ArrayList<Character> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned.
`static byte[][]` ```words(int k, byte[] alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned.
`static StringBuilder[]` ```words(int k, char[] alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned.
`static HashSet<StringBuilder>` ```words(int k, HashSet<StringBuilder> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned.
`static TreeSet<String>` ```words(int k, Set<Character> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### Combinatorics

`public Combinatorics()`
• ### Method Detail

• #### words

```public static HashSet<StringBuilder> words(int k,
HashSet<StringBuilder> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned. There are nk words of this kind. The input set s itself is not modified by this method.
Parameters:
`k` - a nonnegative integer ≤ n
`alphabet` - the alphabet
Returns:
a set of all words of length k
Throws:
`IllegalArgumentException` - if k ≤ 0
• #### words

```public static TreeSet<String> words(int k,
Set<Character> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned. There are nk words of this kind. The input set s itself is not modified by this method.
Parameters:
`k` - a nonnegative integer ≤ n
`alphabet` - the alphabet
Returns:
a set of all words of length k
Throws:
`IllegalArgumentException` - if k ≤ 0
• #### words

```public static StringBuilder[] words(int k,
char[] alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned. There are nk words of this kind. The input list s itself is not modified by this method.
Parameters:
`k` - a nonnegative integer
`alphabet` - the alphabet
Returns:
a list of all words of length k
Throws:
`IllegalArgumentException` - if k < 0 or k >= 0
• #### words

```public static ArrayList<StringBuilder> words(int k,
ArrayList<Character> alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned. There are nk words of this kind. The input list s itself is not modified by this method.
Parameters:
`k` - a nonnegative integer
`alphabet` - the alphabet
Returns:
a list of all words of length k
Throws:
`IllegalArgumentException` - if k < 0 or k >= 0
• #### words

```public static byte[][] words(int k,
byte[] alphabet)```
For every number k with k ≥ 0 a list of all words of length k over the specified alphabet is returned. There are nk words of this kind. The input list s itself is not modified by this method.
Parameters:
`k` - a nonnegative integer
`alphabet` - the alphabet
Returns:
a list of all words of length k
Throws:
`IllegalArgumentException` - if k < 0 or k >= 0
• #### permutation

```public static <T> ArrayList<T> permutation(int k,
ArrayList<T> s)```
For every number k with 0 ≤ k < n! the k-th permutation of the sequence s is returned. The input list s itself is not modified by this method.
Type Parameters:
`T` - subclass of `ArrayList`
Parameters:
`k` - a nonnegative integer < n!
`s` - a sequence of objects
Returns:
the sequence resulting from the k-th permutation
Throws:
`IllegalArgumentException` - if k < 0 or k >= n!
• #### permutations

`public static <T> T[][] permutations(T[] s)`
Returns all permutations of a sequence as a 2-dimensional array. If the size of the sequence is 0, an array of length zero is returned.
Type Parameters:
`T` - a general class
Parameters:
`s` - a sequence containing elements of a specified type <T>
Returns:
a table where each row is a permutation of the eentries of s
• #### permutations

`public static <T> T[][] permutations(Set<T> set)`
Returns all permutations of a set as a 2-dimensional array. If the size of the set is 0, an array of length zero is returned. This method detects whether not all elements are of the same type and returns a 2-dimensional array of the "least" superclass of all elements. For instance, a set of different numbers may be input as follows:
```      HashSet<Number> s = new HashSet<Number>(java.util.Arrays.asList(
new Number[] {1, 3, 3.1415, java.math.BigInteger.valueOf(5)}
));
Number[][] perms = permutations(s);
for (int i=0; i < perms.length; i++) {
System.out.print((1+i) + ") ");
for (Number x : perms[i]) {
System.out.print(x + ", ");
}
System.out.println();
}
```
Type Parameters:
`T` - a general class
Parameters:
`set` - a set containing elements of a specified type <T>
Returns:
a table where each row is a permutation of the elements of set
• #### subsets

```public static <T extends Comparable<T>> ArrayList<TreeSet<T>> subsets(SortedSet<T> s,
int k)```
Returns the k-element subsets of a set s, i.e., each k-element combination of s, stored in an array list. Especially, the array contains only the empty set if k=0, and only the entire set s if k = n where n is the size of s. If k > n, the array list is empty. Also see `MathSet.subsets(int)` for unsorted sets.
Type Parameters:
`T` - a class implementing `Comparable`
Parameters:
`s` - a set
`k` - an integer
Returns:
a list of all k-element subsets of the set s
See Also:
`MathSet.subsets(int)`
• #### surjections

```public static ArrayList<int[]> surjections(int n,
int k)```
Returns a list of all surjections f: {0, 1, ..., n-1} → {0, 1 ..., k-1}, each one of which encoded as an array such that f(x) = `n[x]` ∈ {0, 1 ..., k-1}. I.e., the number x is mapped to `n[x]`. A surjection f: AB between two arbitrary sets A and B is a mapping whose image is exactly B, i.e,, f(A) = B; in other words, for every element b ∈ B there exists a value a ∈ A such that f(a) = b. For finite sets, in particular, a necessary condition for f: {0, 1, ..., n-1} → {0, 1 ..., k-1} to be a surjection is that nk. A surjection is also often called an onto mapping. This algorithm requires a time complexity of O(knk+1).
Parameters:
`n` - a positive integer specifying the domain {0, 1, ..., n-1}
`k` - a positive integer specifying the range {0, 1, ..., k-1}
Returns:
a list of all surjections f: {0, 1, ..., n-1} → {0, 1 ..., k-1}, each one encoded as an array
• #### isSurjective

```public static boolean isSurjective(int[] f,
int k)```
Returns whether the mapping f: {0, 1, ..., n-1} → {0, 1, ..., k-1} is a surjection. Here f is encoded as an array such that f(x) = `f[x]` ∈ {0, 1 ..., k-1}. In general, a mapping f: AB between two arbitrary sets A and B is called surjective, or onto, if its image is exactly B, i.e,, f(A) = B; in other words, for every element b ∈ B there exists a value a ∈ A such that f(a) = b. For finite sets, in particular, a necessary condition for f: {0, 1, ..., n-1} → {0, 1 ..., k-1} to be a surjection is that nk. This algorithm requires a time complexity of O(nk).
Parameters:
`f` - an array, encoding a mapping {0, 1, ..., n-1} → {0, 1, ..., k-1}
`k` - a positive integer specifying the range {0, 1, ..., k-1}
Returns:
true if and only if f is surjective on {0, 1, ..., k-1}
Skip navigation links
The mathIT Library
A Java™ API for mathematics