Skip to content

Latest commit

 

History

History
569 lines (551 loc) · 17.5 KB

README.md

File metadata and controls

569 lines (551 loc) · 17.5 KB
Raw

JNumberTools V1.0.0

JNumberTools is the open source java-library of combinatorics and number-theory

Currently Available Algorithms

  1. Permutations (12 different types of permutation ranking and un-ranking)
  2. Combinations (4 different types of combination ranking and un-ranking)
  3. Set/subset generations
  4. Factoradic number system aka Factoradic.
  5. Combinadic number system aka Combinadic
  6. Permutational Number System aka Permutadic (A new concept for nth k-Permutation)

Permutation Generation Examples: permutation examples

<iframe src="/md_files/permutation_table.html" title="permutation examples"> </iframe>
# Permutation Type Description API Output Count
1 Unique permutation in lex order All unique permutations of input elements in lex order. 
JNumberTools
    .permutationsOf(size)
    .unique()
    .forEach(System.out::println);
 
JNumberTools.permutationsOf("A","B","C")
    .unique()
    .forEach(System.out::println);
 [A,B,C] 
[A,C,B] 
[B,A,C] 
[B,C,A] 
[C,A,B] 
[C,B,A] 		m!
2 Nth unique permutation in lex order Generate permutations with repeated values starting from 0th permutation(input) and then generate every nth permutation in lexicographical order of indices of input values.

This is important because say, if we need to generate next 100 trillionth permutation of 100 items then it will take months to compute if we go sequentially and then increment to the desired permutation because the total # of permutations is astronomical  (100!= 9.3326 x 10157) 
JNumberTools
    .permutationsOf(size)
    .uniqueNth(increment)
    .forEach(System.out::println);
 
JNumberTools
    .permutationsOf("A","B","C")
    .uniqueNth(increment)
    .forEach(System.out::println);
 [A,B,C]
[B,A,C]
[C,A,B] 		m!/n
3 Repetitive Permutation in lex order This is same as generating base-n numbers of max size r-digits with given n symbols, starting from zero in lex order. 
JNumberTools
    .permutationsOf(size)
    .repetitive(repetitionSize)
    .forEach(System.out::println);
     
JNumberTools
    .permutationsOf("A","B","C")
    .repetitive(repetitionSize)
    .forEach(System.out::println);
 [A, A] 
[A, B] 
[A, C] 
[B, A] 
[B, B] 
[B, C] 
[C, A] 
[C, B] 
[C, C] 		mr
4 Nth Repetitive Permutation in lex order This is same as generating AP series of base-n numbers with given n-symbols and a=0, d=m and with max-digits = r 
JNumberTools
    .permutationsOf(size)
    .repetitiveNth(repetitionSize, increment)
    .forEach(System.out::println);
     
JNumberTools
    .permutationsOf("A","B","C")
    .repetitiveNth(repetitionSize, increment)
    .forEach(System.out::println);
 [A, A]
[B, A]
[C, A] 		mr/n
5 k-permutation For a given m elements, it generates all unique permutations of size k where 0 ≤ k ≤ m
In number theory, this is also known as k-permutation. 
JNumberTools
    .permutationsOf(size)
    .k(k)
    .lexOrder()
    .forEach(System.out::println);
     
JNumberTools
    .permutationsOf("A","B","C")
    .k(k)
    .lexOrder()
    .forEach(System.out::println);
 [A, B]
[A, C]
[B, A]
[B, C]
[C, A]
[C, B] 		mPk
6 Nth k-permutation Generates every nth k-permutation in lex order without explicitly computing all the permutations preceding it.
This concept is important because the total number of permutations can grow astronomically large. For instance, the number of permutations of 100 elements selected 50 at a time is 100P50 = 3.068518756 x 1093, which is way beyond the practical limit to be generated sequentially to reach the desired permutation.
To achieve this, a new concept called Permutadic and Deep-code(an extension of Lehmer code) is used. Details can be found in the research paper - Generating the nth Lexicographical Element of a Mathematical k-Permutation using Permutational Number System 
JNumberTools
    .permutationsOf(size)
    .k(k)
    .lexOrderNth(increment)
    .forEach(System.out::println);
 
JNumberTools
    .permutationsOf("A","B","C")
    .k(k)
    .lexOrderNth(increment)
    .forEach(System.out::println);
 [A, B]
[B, A]
[C, A] 		mPk/n
7 k-permutation combination order Generates all k-permutations in the lexicographical order of combination. For example, [C,A] comes before [B,C] because combination-wise [C,A] = [A,C] which comes before [B,C]
Note that the API does not sort the output to achieve this, but it generates the permutation in said order, so it is very efficient. 
JNumberTools
    .permutationsOf(size)
    .k(k)
    .combinationOrder()
    .forEach(System.out::println);
     
JNumberTools
    .permutationsOf("A","B","C")
    .k(k).combinationOrder()
    .forEach(System.out::println);
 [A, B]
[B, A]
[A, C]
[C, A]
[B, C]
[C, B] 		mPk
8 Nth k-permutation combination order Nth Generates every nth k-permutation in the lexicographical order of combination.
This API does not sort or search to achieve this but generates the desired permutation directly, so it is very efficient. 
JNumberTools
    .permutationsOf(size)
    .k(k)
    .combinationOrderNth(increment)
    .forEach(System.out::println);
     
JNumberTools
    .permutationsOf("A","B","C")
    .k(k).combinationOrderNth(increment)
    .forEach(System.out::println);
 [A, B]
[A, C]
[B, C] 		mPk/n
9 Multi-set permutation in lex order Permutation, where every item has an associated frequency that denotes how many times an item can be repeated in a permutation.

For example, permutations of 3 apples and 2 oranges. 
int[] multisetFreqArray = new int[]{1,2};
JNumberTools
    .permutationsOf(size)
    .multiset(multisetFreqArray)
    .forEach(System.out::println);
 
JNumberTools
.permutationsOf("A","B")
.multiset(multisetFreqArray)
.forEach(System.out::println);
 [A,B,B]
[B,A,B]
[B,B,A] 		( ∑ ai . si )! / Π(si!)
10 Nth multi-set permutation in lex order Generates every nth multiset-permutation.
This API does not search for the nth permutation in a sorted list but directly generates the next nth multiset-permutation and hence it is very efficient. 
int increment = 2;
int[] multisetFreqArray = new int[]{1,2};	
 
JNumberTools
    .permutationsOf(size)
    .multisetNth(increment,multisetFreqArray)
    .forEach(System.out::println);
 
JNumberTools
    .permutationsOf("A","B")
    .multisetNth(increment,multisetFreqArray)
    .forEach(System.out::println);
 [A,B,B]
[B,B,A] 		( ∑ ai . si )! / (n*Π(si!))
11 Rank of unique permutation Finds the rank of a given unique permutation. For example, [2,1,0] is the 5th permutation of 3 elements starting from 0, hence its rank is 5. 
int[] permutation = new int[]{1,3,0,2};
int rank = JNumberTools
    .rankOf()
    .uniquePermutation(permutation)
    .intValue();
 10 NA
12 Rank of k-permutation Finds the rank of a given k-permutation 
int[] permutation = new int[]{1,3,0};
int size=3;
int rank = JNumberTools.rankOf()
    .kPermutation(size, permutation).intValue();
4  
13 Rank of repetitive permutation TODO: This can be easily achieved. It’s just a base conversion from a given number system to a decimal (base 10) number system.      
14 Rank of multiset permutation TODO: Coming soon      

Combination Generation Examples:

# Combination Type Description API Output Count
1 Unique Combination of size r Selection of r distinct items out of m items.In mathematics, this is also known as m-Choose-r. Generates all combinations in lex order. 
int m=3;
int size = 2;
 
JNumberTools.combinationsOfnCr(n,size)
    .unique()
    .forEach(System.out::println);
 
JNumberTools.combinationsOf(size,"A","B","C")
    .unique()
    .forEach(System.out::println);
[A, B] [A, C] [B, C] mCr
2 Nth Unique Combination of size r Same as m-Choose-r but generates every nth combination in lex order.  This concept is important because the count of combinations can grow astronomically large. For example, to generate, say, the next 1 billionth combination of 34-Choose-17,  we need to wait for days to generate the desired billionth combination if we generate all combinations sequentially and then select the billionth combination. 
int m=3;
int size = 2;
int increment = 2;
 
JNumberTools
    .combinationsOfnCr(m,size)
    .uniqueNth(increment)
.forEach(System.out::println);
 
JNumberTools
    .combinationsOf(size,"A","B","C")
    .uniqueNth(increment)
    .forEach(System.out::println);
[A, B]
[B, C] 		mCr/n
3 Repetitive Combination of size r Generates combinations of repeated values of size r in lexicographical order. 

int m=3;
int size = 2;
 
JNumberTools.combinationsOfnCr(m,size)
    .repetitive()
    .forEach(System.out::println);
 
JNumberTools
    .combinationsOf(size,"A","B","C")
    .repetitive()
    .forEach(System.out::println);
 [A, A]
[A, B]
[A, C]
[B, B]
[B, C]
[C, C] 		m+r-1
4 Repetitive Combination of multiset Also known as multiset-combination.This is a special case of repetitive combination where every item has an associated frequency that denotes how many times an item can be repeated in a combination. For example, combinations of 3 apples and 2 oranges. 

int m=3;
int size = 2;
int[] multisetFreqArray = new int[]{1,2,1};
 
JNumberTools.combinationsOfnCr(m,size)
    .repetitiveMultiset(multisetFreqArray)
    .forEach(System.out::println);
 
JNumberTools.combinationsOf(size,"A","B","C")
    .repetitiveMultiset(multisetFreqArray)
    .forEach(System.out::println);
 [A, B]
[A, C]
[B, B]
[B, C] 		 

Subset Generation Examples:

Type of set API Output Count
All subsets JNumberTools.subsetsOf("A","B","C")
.all()
.forEach(System.out::println); 		[]//represents φ set
[A]
[B]
[C]
[A, B]
[A, C]
[B, C]
[A, B, C]		 2n
Subsets in size-range from a to b JNumberTools.subsetsOf("A","B","C")
.inRange(2,3)
.forEach(System.out::println);		 [A, B]
[A, C]
[B, C]
[A, B, C]		 ∑ nCi for i= a to b