public class Combinatorics extends Object
| Constructor and Description |
|---|
Combinatorics() |
| 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>> |
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.
|
public static HashSet<StringBuilder> words(int k, HashSet<StringBuilder> alphabet)
k - a nonnegative integer ≤ nalphabet - the alphabetIllegalArgumentException - if k ≤ 0public static TreeSet<String> words(int k, Set<Character> alphabet)
k - a nonnegative integer ≤ nalphabet - the alphabetIllegalArgumentException - if k ≤ 0public static StringBuilder[] words(int k, char[] alphabet)
k - a nonnegative integeralphabet - the alphabetIllegalArgumentException - if k < 0 or k >= 0public static ArrayList<StringBuilder> words(int k, ArrayList<Character> alphabet)
k - a nonnegative integeralphabet - the alphabetIllegalArgumentException - if k < 0 or k >= 0public static byte[][] words(int k,
byte[] alphabet)
k - a nonnegative integeralphabet - the alphabetIllegalArgumentException - if k < 0 or k >= 0public static <T> ArrayList<T> permutation(int k, ArrayList<T> s)
T - subclass of ArrayListk - a nonnegative integer < n!s - a sequence of objectsIllegalArgumentException - if k < 0 or k >= n!public static <T> T[][] permutations(T[] s)
T - a general classs - a sequence containing elements of a specified type <T>public static <T> T[][] permutations(Set<T> set)
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();
}
T - a general classset - a set containing elements of a specified type <T>public static <T extends Comparable<T>> ArrayList<TreeSet<T>> subsets(SortedSet<T> s, int k)
MathSet.subsets(int) for unsorted sets.T - a class implementing Comparables - a setk - an integerMathSet.subsets(int)public static ArrayList<int[]> surjections(int n, int k)
n[x] ∈ {0, 1 ..., k-1}.
I.e., the number x is mapped to n[x].
A surjection f: A → B 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 n ≥ k.
A surjection is also often called an onto mapping.
This algorithm requires a time complexity of O(knk+1).n - a positive integer specifying the domain {0, 1, ..., n-1}k - a positive integer specifying the range {0, 1, ..., k-1}public static boolean isSurjective(int[] f,
int k)
f[x] ∈ {0, 1 ..., k-1}.
In general, a mapping f: A → B 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 n ≥ k.
This algorithm requires a time complexity of O(nk).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}