org.uacalc.alg.conlat

Class BasicPartition

java.lang.Object

org.uacalc.util.IntArray

org.uacalc.alg.conlat.BasicPartition

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Comparable, java.lang.Iterable<IntArray>, BinaryRelation, Partition

public class BasicPartition
extends IntArray
implements Partition, java.lang.Comparable

This class implement the basic operations for partition on the set {0, 1, ..., n-1}. A class that wants to implement partitions on an arbibtrary set can use this class internally. It can also be used as a wrapper for an array of int's in order to use the equals and hashCode methods.

It is based on my unpublished note: Partition Algorithms which can be obtained at http://www.math.hawaii.edu/~ralph/Notes/.

Version:

$Id$

Author:

Ralph Freese

Nested Class Summary

Nested classes/interfaces inherited from interface org.uacalc.alg.conlat.Partition

Partition.PrintType

Field Summary

Fields inherited from class org.uacalc.util.IntArray

array, size

Constructor Summary

Constructors

Constructor and Description
BasicPartition(int[] part)
BasicPartition(java.lang.String str)
BasicPartition(java.lang.String str, int length) If length is nonnegative, this converts str into a partition on 0 to length - 1, ignoring any any interger in str greater than length - 1.

Method Summary

Modifier and Type	Method and Description
static java.util.NavigableSet<IntArray>	binaryPolymorphisms(java.util.List<Partition> pars)
static java.util.NavigableSet<IntArray>	binaryPolymorphisms(java.util.List<Partition> pars, java.util.NavigableSet<IntArray> unaryClone, ProgressReport report)
static SmallAlgebra	binaryPolymorphismsAlgebra(java.util.List<Partition> pars, ProgressReport report)
int	blockIndex(int i) The index of the block containing i.
static java.util.List<Partition>	closureAt(java.util.List<BasicPartition> pars)
int	compareTo(java.lang.Object o) The order of a linear extension respecting rank.
BinaryRelation	compose(BinaryRelation beta) The relational composition.
static Partition	directProduct(Partition alpha, Partition beta)
static Partition	firstProjection(int n)
static java.util.Map<IntArray,java.util.List<Partition>>	funcToJIs(int n)
static java.util.List<Partition>	generalizedWeakClosure(java.util.List<BasicPartition> pars, int pow, java.util.Map<IntArray,Partition> rels)
int[][]	getBlocks() Get the block form of this partition as an array of arrays.
java.util.NavigableSet<IntArray>	getPairs()
static boolean	isHereditary(java.util.List<Partition> pars) True if all 0-1 sublattices of the closure of the sublattice generated by pars are themselves closed.
boolean	isInitialLexRepresentative() This will be true if, when the separators of the blocks are removed, it is just 0 to n-1 in order; also the sizes of the blocks are getting smaller, left to right.
boolean	isRelated(int i, int j)
boolean	isRepresentative(int i)
boolean	isZero()
java.util.Iterator<IntArray>	iterator()
static BasicPartition	jbToPartition(int[] a) Takes a partition in JB form and return the corresponding Partition.
Partition	join(Partition part2)
void	joinBlocks(int r, int s) Note r and s must be roots and distinct.
static java.util.List<Partition>	joinClosure(java.util.List<Partition> pars)
static java.util.List<Partition>	joinClosure(java.util.List<Partition> pars, java.util.Map<Partition,Term> termMap)
static java.util.List<Partition>	joinClosure(java.util.List<Partition> pars, java.util.Map<Partition,Term> termMap, Partition projkernel) This is the join closure except that it will stop if it finds a new element above projkernel.
static boolean	leq(int[] u, int[] v)
boolean	leq(Partition part2)
static void	main(java.lang.String[] args)
Partition	meet(Partition part2)
static java.util.List<Partition>	meetClosure(java.util.List<Partition> pars)
static java.util.List<Partition>	meetClosure(java.util.List<Partition> pars, java.util.Map<Partition,Term> termMap)
void	normalize() This modifies this.array.
static void	normalize(int[] part) Modify part so that it is in normal form.
int	numberOfBlocks() Does not need normalized form.
static BasicPartition	one(int asize)
static Partition	partitionFromMatrix(int[][] matrix) If matrix has r rows and s columns whose entries lie in the set 0, ..., rs - 1, this returns a partition essentially on the product of {0,...,r-1} and {0,...,s-1} such that (x,y) is related to (u,v) if the (x,y) entry of the matrix equals to (u,v) entry.
static java.lang.String	partToKissString(int[] part) Make String representation of the partition for the .con and related files.
static int	permutabilityLevel(int a, int b, Partition par0, Partition par1) This returns the least k such that (a,b) is in the k-fold relational product of par0 and par1, with par0 coming first and k counting the total occurances of par0 or par1.
static int	permutabilityLevel(Partition par0, Partition par1) This is the max of permutabilityLevel(a, b, par0, par1) over all (a, b) in the join.
Partition	projection(java.util.List<IntArray> universe, int size, int coord)
int	rank()
int	representative(int i) This is the public way of finding the root.
int[]	representatives()
static Partition	secondProjection(int n)
static int[]	stringToPartition(java.lang.String str, int length)
static java.util.List<Partition>	subUniverseGenerated(java.util.List<Partition> gens)
static java.util.List<Partition>	subUniverseGenerated(java.util.List<Partition> gens, java.util.Map<Partition,Term> termMap)
static java.util.List<Partition>	subUniverseGenerated(java.util.List<Partition> gens, java.util.Map<Partition,Term> termMap, Partition projkernel)
static void	testGeneralizedWeakClosure()
java.lang.String	toString()
java.lang.String	toString(int maxLen)
java.lang.String	toString(Partition.PrintType kind)
java.lang.String	toString(Partition.PrintType kind, int maxLen)
static java.util.NavigableSet<IntArray>	unaryPolymorphisms(java.util.List<? extends Partition> pars, ProgressReport report) The uses a depth first search to find the set of all unary function which respect all partition in pars.
static SmallAlgebra	unaryPolymorphismsAlgebra(java.util.List<? extends Partition> pars)
static SmallAlgebra	unaryPolymorphismsAlgebra(java.util.List<? extends Partition> pars, ProgressReport report)
static BasicPartition	zero(int asize)

Methods inherited from class org.uacalc.util.IntArray

clone, equalIntArrays, equals, get, getArray, hashCode, intArrayToString, isConstant, isIdempotent, lexicographicComparitor, satisfiesBlocksConstraint, satisfiesCongruenceConstraint, satisfiesSetConstraint, satisfiesValuesConstraint, set, setIntArray, stringToArray, toArray, universeSize

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.uacalc.alg.conlat.Partition

toArray, universeSize

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

BasicPartition

public BasicPartition(int[] part)

BasicPartition

public BasicPartition(java.lang.String str)

BasicPartition

public BasicPartition(java.lang.String str,
                      int length)

If length is nonnegative, this converts str into a partition on 0 to length - 1, ignoring any any interger in str greater than length - 1. Str can either use bracket or bar notation: [[1 2][3 4 5]] or |1 2|3 4 5|. Commas or spaces can be used to separate numbers. If length is negative, str must be a full partition on 0 up some n-1.

Parameters:

str -

length -

Method Detail

stringToPartition

public static int[] stringToPartition(java.lang.String str,
                                      int length)

compose

public BinaryRelation compose(BinaryRelation beta)

The relational composition. I might make sense to make this class a subclass of BasicBinaryRelation, but I am not doing that now.

Specified by:

compose in interface BinaryRelation

compareTo

public int compareTo(java.lang.Object o)

The order of a linear extension respecting rank.

Specified by:

compareTo in interface java.lang.Comparable

zero

public static BasicPartition zero(int asize)

one

public static BasicPartition one(int asize)

isRelated

public boolean isRelated(int i,
                         int j)

Specified by:

isRelated in interface BinaryRelation

Specified by:

isRelated in interface Partition

iterator

public java.util.Iterator<IntArray> iterator()

Specified by:

iterator in interface java.lang.Iterable<IntArray>

getPairs

public java.util.NavigableSet<IntArray> getPairs()

Specified by:

getPairs in interface BinaryRelation

numberOfBlocks

public int numberOfBlocks()

Does not need normalized form. Simply counts the negative entries.

Specified by:

numberOfBlocks in interface Partition

jbToPartition

public static BasicPartition jbToPartition(int[] a)

Takes a partition in JB form and return the corresponding Partition. JB form is an array a with a[a[i]] = a[i] and a[i] <= i.

Parameters:

a -

Returns:

rank

public int rank()

joinBlocks

public void joinBlocks(int r,
                       int s)

Note r and s must be roots and distinct.

Specified by:

joinBlocks in interface Partition

join

public Partition join(Partition part2)

Specified by:

join in interface Partition

permutabilityLevel

public static int permutabilityLevel(int a,
                                     int b,
                                     Partition par0,
                                     Partition par1)

This returns the least k such that (a,b) is in the k-fold relational product of par0 and par1, with par0 coming first and k counting the total occurances of par0 or par1. It returns -1 if (a,b) is not in the join.

permutabilityLevel

public static int permutabilityLevel(Partition par0,
                                     Partition par1)

This is the max of permutabilityLevel(a, b, par0, par1) over all (a, b) in the join.

meet

public Partition meet(Partition part2)

Specified by:

meet in interface Partition

leq

public boolean leq(Partition part2)

Specified by:

leq in interface Partition

leq

public static boolean leq(int[] u,
                          int[] v)

normalize

public void normalize()

This modifies this.array.

Specified by:

normalize in interface Partition

normalize

public static void normalize(int[] part)

Modify part so that it is in normal form.

isZero

public boolean isZero()

Specified by:

isZero in interface Partition

toString

public java.lang.String toString()

Overrides:

toString in class IntArray

toString

public java.lang.String toString(int maxLen)

Specified by:

toString in interface Partition

toString

public java.lang.String toString(Partition.PrintType kind)

Specified by:

toString in interface Partition

toString

public java.lang.String toString(Partition.PrintType kind,
                                 int maxLen)

partToKissString

public static java.lang.String partToKissString(int[] part)

Make String representation of the partition for the .con and related files.

getBlocks

public int[][] getBlocks()

Get the block form of this partition as an array of arrays.

Specified by:

getBlocks in interface Partition

representative

public int representative(int i)

This is the public way of finding the root. Unlike root it does not modify array.

Specified by:

representative in interface Partition

isRepresentative

public boolean isRepresentative(int i)

Specified by:

isRepresentative in interface Partition

representatives

public int[] representatives()

Specified by:

representatives in interface Partition

blockIndex

public int blockIndex(int i)

The index of the block containing i. This will be the index in the quotient structure of i modulo this partition.

Specified by:

blockIndex in interface Partition

funcToJIs

public static java.util.Map<IntArray,java.util.List<Partition>> funcToJIs(int n)

directProduct

public static Partition directProduct(Partition alpha,
                                      Partition beta)

isHereditary

public static boolean isHereditary(java.util.List<Partition> pars)

True if all 0-1 sublattices of the closure of the sublattice generated by pars are themselves closed.

Parameters:

pars -

Returns:

unaryPolymorphismsAlgebra

public static SmallAlgebra unaryPolymorphismsAlgebra(java.util.List<? extends Partition> pars)

unaryPolymorphismsAlgebra

public static SmallAlgebra unaryPolymorphismsAlgebra(java.util.List<? extends Partition> pars,
                                                     ProgressReport report)

binaryPolymorphismsAlgebra

public static SmallAlgebra binaryPolymorphismsAlgebra(java.util.List<Partition> pars,
                                                      ProgressReport report)

unaryPolymorphisms

public static java.util.NavigableSet<IntArray> unaryPolymorphisms(java.util.List<? extends Partition> pars,
                                                                  ProgressReport report)

The uses a depth first search to find the set of all unary function which respect all partition in pars.

Parameters:

pars -

Returns:

binaryPolymorphisms

public static java.util.NavigableSet<IntArray> binaryPolymorphisms(java.util.List<Partition> pars)

binaryPolymorphisms

public static java.util.NavigableSet<IntArray> binaryPolymorphisms(java.util.List<Partition> pars,
                                                                   java.util.NavigableSet<IntArray> unaryClone,
                                                                   ProgressReport report)

generalizedWeakClosure

public static java.util.List<Partition> generalizedWeakClosure(java.util.List<BasicPartition> pars,
                                                               int pow,
                                                               java.util.Map<IntArray,Partition> rels)

testGeneralizedWeakClosure

public static void testGeneralizedWeakClosure()

closureAt

public static java.util.List<Partition> closureAt(java.util.List<BasicPartition> pars)

Parameters:

pars -

Returns:

projection

public Partition projection(java.util.List<IntArray> universe,
                            int size,
                            int coord)

joinClosure

public static java.util.List<Partition> joinClosure(java.util.List<Partition> pars)

joinClosure

public static java.util.List<Partition> joinClosure(java.util.List<Partition> pars,
                                                    java.util.Map<Partition,Term> termMap)

joinClosure

public static java.util.List<Partition> joinClosure(java.util.List<Partition> pars,
                                                    java.util.Map<Partition,Term> termMap,
                                                    Partition projkernel)

This is the join closure except that it will stop if it finds a new element above projkernel.

Parameters:

pars -

termMap -

projkernel -

Returns:

meetClosure

public static java.util.List<Partition> meetClosure(java.util.List<Partition> pars)

meetClosure

public static java.util.List<Partition> meetClosure(java.util.List<Partition> pars,
                                                    java.util.Map<Partition,Term> termMap)

subUniverseGenerated

public static java.util.List<Partition> subUniverseGenerated(java.util.List<Partition> gens)

subUniverseGenerated

public static java.util.List<Partition> subUniverseGenerated(java.util.List<Partition> gens,
                                                             java.util.Map<Partition,Term> termMap)

subUniverseGenerated

public static java.util.List<Partition> subUniverseGenerated(java.util.List<Partition> gens,
                                                             java.util.Map<Partition,Term> termMap,
                                                             Partition projkernel)

partitionFromMatrix

public static Partition partitionFromMatrix(int[][] matrix)

If matrix has r rows and s columns whose entries lie in the set 0, ..., rs - 1, this returns a partition essentially on the product of {0,...,r-1} and {0,...,s-1} such that (x,y) is related to (u,v) if the (x,y) entry of the matrix equals to (u,v) entry.

Parameters:

matrix -

Returns:

firstProjection

public static Partition firstProjection(int n)

secondProjection

public static Partition secondProjection(int n)

isInitialLexRepresentative

public boolean isInitialLexRepresentative()

This will be true if, when the separators of the blocks are removed, it is just 0 to n-1 in order; also the sizes of the blocks are getting smaller, left to right.

Specified by:

isInitialLexRepresentative in interface Partition

Returns:

main

public static void main(java.lang.String[] args)