-
Notifications
You must be signed in to change notification settings - Fork 23
v3.4.1
___ _ _ _ _ __ _ _ _____
/ __\___ _ __ ___ | |__ (_)_ __ __ _| |_ ___ _ __(_) ___ ___ / /(_) |__ |___ /
/ / / _ \| '_ ` _ \| '_ \| | '_ \ / _` | __/ _ \| '__| |/ __/ __| / / | | '_ \ |_ \
/ /__| (_) | | | | | | |_) | | | | | (_| | || (_) | | | | (__\__ \/ /__| | |_) | ___) |
\____/\___/|_| |_| |_|_.__/|_|_| |_|\__,_|\__\___/|_| |_|\___|___/\____/_|_.__/ |____/
New implementation of the combinatorics library for Java.
- Simple combinations
- Combinations with repetitions
- Simple permutations
- Permutations with repetitions
- Subsets
- Integer partitions
- Cartesian product
| Description | Is Order Important? | Is Repetition Allowed? | Stream |
|---|---|---|---|
| Simple combinations | No | No | Generator.combination(...).simple(n).stream() |
| Combinations with repetitions | No | Yes | Generator.combination(...).multi(n).stream() |
| Simple permutations | Yes | No | Generator.permutation(...).simple().stream() |
| Permutations with repetitions | Yes | Yes | Generator.permutation(...).withRepetitions(n).stream() |
The latest release of the library v3.4.0 is available through The Maven Central Repository here
Include the following section into your pom.xml file.
<dependency>
<groupId>com.github.dpaukov</groupId>
<artifactId>combinatoricslib3</artifactId>
<version>3.4.0</version>
</dependency>A simple k-combination of a finite set S is a subset of k distinct elements of S. Specifying a subset does not arrange them in a particular order. As an example, a poker hand can be described as a 5-combination of cards from a 52-card deck: the 5 cards of the hand are all distinct, and the order of the cards in the hand does not matter.
Let's generate all 3-combination of the set of 5 colors (red, black, white, green, blue).
List<List<String>> combinations = Generator.combination("red", "black", "white", "green", "blue")
.simple(3)
.stream()
.collect(Collectors.<List<String>>toList());
combinations.stream().forEach(System.out::println);And the result of 10 combinations
[red, black, white]
[red, black, green]
[red, black, blue]
[red, white, green]
[red, white, blue]
[red, green, blue]
[black, white, green]
[black, white, blue]
[black, green, blue]
[white, green, blue]
A k-multicombination or k-combination with repetition of a finite set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account.
As an example. Suppose there are 2 types of fruits (apple and orange) at a grocery store, and you want to buy 3 pieces of fruit. You could select
- (apple, apple, apple)
- (apple, apple, orange)
- (apple, orange, orange)
- (orange, orange, orange)
Example. Generate 3-combinations with repetitions of the set (apple, orange). You can pass an array as a parameter of the combination generator.
Generator.combination(new String[] { "apple", "orange" })
.multi(3)
.stream()
.forEach(System.out::println);And the result of 4 multi-combinations
[apple, apple, apple]
[apple, apple, orange]
[apple, orange, orange]
[orange, orange, orange]
A permutation is an ordering of a set in the context of all possible orderings. For example, the set containing the first three digits, 123, has six permutations: 123, 132, 213, 231, 312, and 321.
This is an example of the permutations of the 3 string items (apple, orange, cherry):
Generator.permutation("apple", "orange", "cherry")
.simple()
.stream()
.forEach(System.out::println);The result of 6 permutations
[apple, orange, cherry]
[apple, cherry, orange]
[cherry, apple, orange]
[cherry, orange, apple]
[orange, cherry, apple]
[orange, apple, cherry]
This generator can produce the permutations even if an initial vector has duplicates. For example, all permutations of (1, 1, 2, 2):
Generator.permutation(1, 1, 2, 2)
.simple()
.stream()
.forEach(System.out::println);The result of all possible permutations (with duplicates)
[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]
Permutation may have more elements than slots. For example, all possible permutation of '12' in three slots are: 111, 211, 121, 221, 112, 212, 122, and 222.
Let's generate all possible permutations with repetitions of 3 elements from the set of apple and orange.
List<List<String>> permutations = Generator
.permutation("apple", "orange")
.withRepetitions(3)
.stream()
.collect(Collectors.<List<String>>toList());
permutations.stream().forEach(System.out::println);And the result of 8 permutations
[apple, apple, apple]
[orange, apple, apple]
[apple, orange, apple]
[orange, orange, apple]
[apple, apple, orange]
[orange, apple, orange]
[apple, orange, orange]
[orange, orange, orange]
A set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment.
Examples:
The set (1, 2) is a proper subset of (1, 2, 3). Any set is a subset of itself, but not a proper subset. The empty set, denoted by ∅, is also a subset of any given set X. All subsets of (1, 2, 3) are:
- ()
- (1)
- (2)
- (1, 2)
- (3)
- (1, 3)
- (2, 3)
- (1, 2, 3)
Here is a piece of code that generates all possible subsets of (one, two, three)
List<List<String>> subsets = Generator
.subset("one", "two", "three")
.simple()
.stream()
.collect(Collectors.<List<String>>toList());
subsets.stream().forEach(System.out::println);And the result of all possible 8 subsets
[]
[one]
[two]
[one, two]
[three]
[one, three]
[two, three]
[one, two, three]
In number theory, a partition of a positive integer n is a way of writing n as a sum of positive integers.
Two sums that differ only in the order of their summands are considered to be the same partition;
if order matters then the sum becomes a composition. A summand in a partition is also called a part.
The partitions of 5 are listed below:
- 1 + 1 + 1 + 1 + 1
- 2 + 1 + 1 + 1
- 2 + 2 + 1
- 3 + 1 + 1
- 3 + 2
- 4 + 1
- 5
Let's generate all possible partitions of 5:
Generator.partition(5)
.stream()
.forEach(System.out::println);And the result of all 7 integer possible partitions
[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[2, 2, 1]
[3, 1, 1]
[3, 2]
[4, 1]
[5]
In set theory, a Cartesian Product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
As an example, suppose there are 2 sets of number, (1, 2, 3) and (4, 5, 6), and you want to get the Cartesian product of the two sets.
Source: Cartesian Product
Generator.cartesianProduct(Arrays.asList(1, 2, 3), Arrays.asList(4, 5, 6))
.stream()
.forEach(System.out::println);And the result will be:
[1, 4]
[1, 5]
[1, 6]
[2, 4]
[2, 5]
[2, 6]
[3, 4]
[3, 5]
[3, 6]