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 ArrayList
k
- 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 Comparable
s
- 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}