dpaukov / combinatoricslib3

Combinatorial objects stream generators for Java.

     ___                _     _             _             _             __ _ _       _____ 
    / __\___  _ __ ___ | |__ (_)_ __   __ _| |_ ___  _ __(_) ___ ___   / /(_) |__   |___ / 
   / /  / _ \| '_ ` _ \| '_ \| | '_ \ / _` | __/ _ \| '__| |/ __/ __| / / | | '_ \    |_ \ 
  / /__| (_) | | | | | | |_) | | | | | (_| | || (_) | |  | | (__\__ \/ /__| | |_) |  ___) |
  \____/\___/|_| |_| |_|_.__/|_|_| |_|\__,_|\__\___/|_|  |_|\___|___/\____/_|_.__/  |____/ 

A combinatorics library for Java.

3.4.0 - the latest stable release version

The latest release of the library is v3.4.0. It is available through The Maven Central Repository here. Add the following section into your pom.xml file.

<dependency>
    <groupId>com.github.dpaukov</groupId>
    <artifactId>combinatoricslib3</artifactId>
    <version>3.4.0</version>
</dependency>

Examples

You can check out an example project to see how to use the library combinatoricslib3-example

3.4.1 - current version under development

1. Simple combinations
2. Combinations with repetitions
3. Simple permutations
4. Permutations with repetitions
5. k-Permutations
6. Subsets
7. Integer partitions
8. 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()

1. Simple combinations

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).

   Generator.combination("red", "black", "white", "green", "blue")
       .simple(3)
       .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]

2. Combinations with repetitions

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)

   Generator.combination("apple", "orange")
       .multi(3)
       .stream()
       .forEach(System.out::println);

And the result will be:

   [apple, apple, apple]
   [apple, apple, orange]
   [apple, orange, orange]
   [orange, orange, orange]

3. Simple permutations

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);

   [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 does not have duplicates. All permutations are distinct by default.

   [1, 1, 2, 2]
   [1, 2, 1, 2]
   [1, 2, 2, 1]
   [2, 1, 1, 2]
   [2, 1, 2, 1]
   [2, 2, 1, 1]

Notice that we have 6 permutations here instead of 24. If you still need all permutations, you should call method simple(PermutationGenerator.TreatDuplicatesAs.IDENTICAL).

4. Permutations with repetitions

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.

   Generator.permutation("apple", "orange")
        .withRepetitions(3)
        .stream()
        .forEach(System.out::println);

And the list of all 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]

5. k-Permutations

You can generate k-permutations with and without repetitions using the combination and permutation generators together. For example, 2-permutations without repetitions of the list (1, 2, 3):

    Generator.combination(1, 2, 3)
       .simple(2)
       .stream()
       .forEach(combination -> Generator.permutation(combination)
          .simple()
          .forEach(System.out::println));

This will print six 2-permutations of (1, 2, 3):

   [1, 2]
   [2, 1]
   [1, 3]
   [3, 1]
   [2, 3]
   [3, 2]

Similarly, you can get 2-Permutations with repetitions of the list (1, 2, 3):

    Generator.combination(1, 2, 3)
       .multi(2)
       .stream()
       .forEach(combination -> Generator.permutation(combination)
           .simple()
           .forEach(System.out::println));

This will print all nine 2-permutations of (1, 2, 3):

   [1, 1]
   [1, 2]
   [2, 1]
   [1, 3]
   [3, 1]
   [2, 2]
   [2, 3]
   [3, 2]
   [3, 3]

6. Subsets

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)

   Generator.subset("one", "two", "three")
        .simple()
        .stream()
        .forEach(System.out::println);

And the list of all 8 subsets

   []
   [one]
   [two]
   [one, two]
   [three]
   [one, three]
   [two, three]
   [one, two, three]

7. Integer Partitions

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]

8. Cartesian Product

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]

combinatoricslib3's Issues

Apache 2.0 compatible license option?

Hi,

thanks for the great library. I was thinking about using it in a (future) open source project of mine. However, the complete list of dependencies in my code uses some kind of Apache 2.0 compatible license, so I would like to use Apache 2.0 as well. However, this seems to prevent me from using combinatoricslib3 as it is under LGPLv3 and from my understanding using combinatoricslib3 in a new project would require my project to be under LGPL as well. Is there any chance you would think about dual-licensing the library to be compatible with ASF libraries, e.g. LGPLv3 + Apache 2.0?

Regards
Martin

k-Permutations - ordering of elements

From your k-Permutations example:

This will print six 2-permutations of (1, 2, 3):

   [1, 2]
   [2, 1]
   [1, 3]
   [3, 1]
   [2, 3]
   [3, 2]

How can I make the "sort ascending by column"?

   [1, 2]
   [1, 3]
   [2, 1]
   [2, 3]
   [3, 1]
   [3, 2]

Add a cartesian product with collection input parameter.

Varargs is very convenient when we want to write each parameter at function call.
However, it is quite less convenient when the input parameters we have are in a List because converting List<List<AnyType>> into List<AnyType>[] is not easy in Java.
I think it would be useful to have a cartesian product with in collection input parameter like it is already done for subset, permutation and combination.

Subsets number

Please, implement Subsets-(and other - also useful) generator limitation number, i.e.:

BEFORE:

   Generator.subset("one", "two", "three")
        .simple()
        .before(2)//
        .stream()
        .forEach(System.out::println);

   []
   [one]
   [two]
   [three]

AFTER:

   Generator.subset("one", "two", "three")
        .simple()
        .after(1)//
        .stream()
        .forEach(System.out::println);

   [one, two]
   [one, three]
   [two, three]
   [one, two, three]

STRICT or EXACT:

   Generator.subset("one", "two", "three")
        .simple()
        .strict(2)//.exact(2)
        .stream()
        .forEach(System.out::println);

   [one, two]
   [one, three]
   [two, three]

GIVEN:

   Generator.subset("one", "two", "three")
        .simple()
        .given(1, 3)//
        .stream()
        .forEach(System.out::println);

   [one]
   [two]
   [three]
   [one, two, three]

RANGE:

   Generator.subset("one", "two", "three")
        .simple()
        .range(1, 3)//
        .stream()
        .forEach(System.out::println);

   [one]
   [two]
   [one, two]
   [three]
   [one, three]
   [two, three]
   [one, two, three]

Make k-permutation API more easy to use

Thanks dpaukov, very good library. I use this library validate my combination/permutation questions, it is easy to use and quick.

One minor issue is I use k-permutation very frequently, while current API is a little verbose

        Generator.combination(1, 2, 3)
            .simple(2)
            .stream()
            .forEach(combination -> Generator.permutation(combination)
                .simple()
                .forEach(System.out::println));

Can you help provide high level API like:

        Generator.permutation(1, 2, 3)
            .simple(2)
            .stream()
            .forEach(System.out::println));

Thanks a lot.

Return Stream[] or List<Stream> chunks for combinations

Please, implement for all Generators:
Return -array[] or -List() of chunked Streams of precalculated (but not yet generated as output) combinations
according to input parallel thread number as a divisor for total precalculated number of output combinations, i.g.:

   int n = Runtime.getRuntime().availableProcessors();
   assert n == 8;
   Generator.combination("red", "black", "white", "green", "blue")
       .simple(3)
       .asArrayOfStreamsForGivenThreads(n) //returns Stream[] or List<Stream>
       .stream()
       .parallel()
       .forEach(e->e.forEach(System.out::println));

so, therefore user can process in parallel in chunks:

   [red, black, white] // 0-stream 1st output
   [red, black, green] // 0-stream 2nd output
   [red, black, blue] // 2-stream 1st output
   [red, white, green] // 2-stream 2nd output
   [red, white, blue] // 4-stream 1st output
   [red, green, blue] // 4-stream 2nd output
   [black, white, green] // 1-stream 1st output
   [black, white, blue] // 1-stream 2nd output
   [black, green, blue] // 3-stream 1st output
   [white, green, blue] // 3-stream 2nd output 
   
   //total output ==10 //out of 5-capacity array or list

(5 streams - since it is best match for given threads divisor 10/8 == Math.ceil(5/4) == 2 (so total output 10/per 2 = 5 element-array or list) for output number of array.length or list.size() but precalculated number of total output ==10)
Please note:

1. It is important, that array Stream[] or List should not be prefilled by output generated data, just chunks of stream to be used for further parallel processing

2. In Mathmatics, there are some formulas exist for every type of combination (total output number)

Thank you

One more example on K-Permutation

Original k-permutation example print output into console. while cannot collect result into a collection for further processing.

        Generator.combination("1", "2", "3", "4")
                .simple(2)
                .stream()
                .forEach(combination -> Generator.permutation(combination)
                        .simple()
                        .stream()
                        .forEach(System.out::println))

Below example collect result into a collection for further processing

        List<List<String>> kPermutationResult = Generator.combination("1", "2", "3", "4")
                .simple(2)
                .stream()
                .flatMap(combination -> Generator.permutation(combination)
                        .simple()
                        .stream()
                        )
                .collect(Collectors.toList());

Best way to determine "the rest of the sequence" generated with the `subset()` method?

What is the best way to determine "the rest of the sequence" generated with the subset() method?
For example to get exactly 3 partitions out of 5 elements and filling the second partition again with a "subset of the rest" and filling last partition with the subset of elements not used in the first 2 partitions?

How to improve this snippet?

Generator.subset(1, 1, 2, 2, 3)
        .simple()
        .stream()
        .forEach(System.out::println);

Subsets - give all subsets containing exactly n elements.

Is there an implementation for subsets containing exactly n elements.?

This can of course be done with the stream() API, but I assume it will be faster, if its already implemented in the subset iterator itself.

In case you provide an implementation, the ordering of subsets should also be adjusted.

Instead of this ordering in your example:

   []
   [one]
   [two]
   [one, two]
   [three]
   [one, three]
   [two, three]
   [one, two, three]

It should be ordered like this IMO:

   []
   [one]
   [two]
   [three]
   [one, two]
   [one, three]
   [two, three]
   [one, two, three]

Is version 3.1.0 ready ?

Thx

k-permutations

Hi,

Thanks for your excellent work, this is truly handful AND elegant, which is remarkable.
I was wondering if you are going to add k-permutations in your library, would definitely make it 100% awesome.

Regards

Combinations of lists?

I have n lists all of the same type. I want to loop through all the possible combinations of pulling one item from each of those lists.

Ex.

List 1 = { Red, Blue, Orange }
List 2 = { Brown }
List 3 = { White, Black }

Red Brown White
Red Brown Black
Blue Brown White
Blue Brown Black
Orange Brown White
Orange Brown Black

How can I do that with this library? Thanks

IndexOutOfBoundsException when generating permutation for empty list

@Test
public void test_zero_permutation_of_empty_with_repetition() {
  List<List<Object>> permutations = Generator.permutation(Collections.emptyList())
      .withRepetitions(0)
      .stream()
      .collect(toList());

  assertThat(permutations).isEmpty();
}

Expected: test should ✓
Actual: java.lang.IndexOutOfBoundsException

java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
	<3 internal lines>
	at java.base/java.util.Objects.checkIndex(Objects.java:359)
	at java.base/java.util.ArrayList.get(ArrayList.java:427)
	at org.paukov.combinatorics3.PermutationWithRepetitionIterator.<init>(PermutationWithRepetitionIterator.java:24)
	at org.paukov.combinatorics3.PermutationWithRepetitionGenerator.iterator(PermutationWithRepetitionGenerator.java:29)
	at org.paukov.combinatorics3.PermutationWithRepetitionGenerator.stream(PermutationWithRepetitionGenerator.java:34)
	at org.paukov.combinatorics3.PermutationsWithRepetitionsTest.test_zero_permutation_of_empty_with_repetition(PermutationsWithRepetitionsTest.java:89)

BitSet Support

Hello,

i looking for a toolkit for java.util.BitSet Permutations with repetitions.
How / Can I use the lib?

with regards