RANDOM EQUIVALENCE RELATION

RANDOM EQUIVALENCE RELATION (LET)

Let Subcommand

Generate a random equivalence relation of an n-element set.

Given a set S = {1, 2, ..., n}, a random partition of S is defined as a collection of sets T₁, T₂, ... , T_k satisfying
1. The intersection of T_i and T_j is the empty set for i not equal j.

2. The union of all k sets contains all the elements of S.

For example, if n = 3, then there are 5 possible partitions:

{1, 2, 3}
{1,2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}


The output of this command is an array of size n where the ith element identifies the class which i belongs to. For example, the following array (for n = 5)

3 3 1 2 2

identifies the partition

{3} {4, 5} {1, 2}

LET <y> = RANDOM EQUIVALENCE RELATION
where <y> is a variable where the random equivalence relation is saved.

This command must be preceeded with the command

LET N = <value>

LET N = 5
LET Y = RANDOM EQUIVALENCE RELATION

Dataplot implements this command using the RANEQU algorithm described in Nijenhuis and Wilf (see Reference section below).

Dataplot supports a number of different random number generators. Enter HELP RANDOM NUMBER GENERATOR for details.

The SEED command can be used to specify a seed for the random number generator.

None

None

LET	= Generate data transformations.
RANDOM PERMUTATION	= Generate a random permutation.
RANDOM K-SET OF N-SET	= Generate a random k-set of n-set.
RANDOM COMPOSITION	= Generate a random composition.
RANDOM PARTITION	= Generate a random partition.
RANDOM SUBSET	= Generate a random subset.
NEXT SUBSET	= Generate the next subset of a set.
NEXT PERMUTATION	= Generate the next permutation.
NEXT K-SET OF N-SET	= Generate the next k-set of n-set.
NEXT COMPOSITION	= Generate the next composition.
NEXT PARTITION	= Generate the next partition.
NEXT EQUIVALENCE RELATION	= Generate the next composition.

Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 12.

Combinatorial Analysis

2008/6

 
LET N = 8
LET Y = RANDOM EQUIVALENCE RELATION
PRINT Y