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: BasicPartition.java,v 1.31 2010/01/28 01:54:08 ralphfreese Exp $

Author:

Ralph Freese

Field Summary

Fields inherited from class org.uacalc.util.IntArray

array, size

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

BLOCK, EWK, HUMAN, INTERNAL

Constructor Summary

BasicPartition(int[] part)

Method Summary

static java.util.NavigableSet<IntArray>	binaryClone(java.util.List<Partition> pars)
static java.util.NavigableSet<IntArray>	binaryClone(java.util.List<Partition> pars, java.util.NavigableSet<IntArray> unaryClone)
static SmallAlgebra	binaryCloneAlgebra(java.util.List<Partition> pars)
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.
static Partition	directProduct(Partition alpha, Partition beta)
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	isRelated(int i, int j)
boolean	isRepresentative(int i)
boolean	isZero()
java.util.Iterator<IntArray>	iterator()
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 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)
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 java.util.List<Partition>	subUniverseGenerated(java.util.List<Partition> gens)
java.lang.String	toString()
java.lang.String	toString(int kind)
static java.util.NavigableSet<IntArray>	unaryClone(java.util.List<Partition> pars) The uses a depth first search to find the set of all unary function which respect all partition in pars.
static SmallAlgebra	unaryCloneAlgebra(java.util.List<Partition> pars)
static BasicPartition	zero(int asize)

Methods inherited from class org.uacalc.util.IntArray

clone, equalIntArrays, equals, get, getArray, hashCode, intArrayToString, isIdempotent, lexicographicComparitor, satisfiesConstraint, satisfiesConstraint, set, setIntArray, 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

Constructor Detail

BasicPartition

public BasicPartition(int[] part)

Method Detail

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

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

Specified by:

toString in interface Partition

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

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:

unaryCloneAlgebra

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

binaryCloneAlgebra

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

unaryClone

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

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

Parameters:

pars -

Returns:

binaryClone

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

binaryClone

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

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)

meetClosure

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

subUniverseGenerated

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

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:

main

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