Dataplot Vol 2 Vol 1

# RANDOM EQUIVALENCE RELATION

Name:
RANDOM EQUIVALENCE RELATION (LET)
Type:
Let Subcommand
Purpose:
Generate a random equivalence relation of an n-element set.
Description:
Given a set S = {1, 2, ..., n}, a random partition of S is defined as a collection of sets T1, T2, ... , Tk satisfying

1. The intersection of Ti and Tj 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}
Syntax:
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>
Examples:
LET N = 5
LET Y = RANDOM EQUIVALENCE RELATION
Note:
Dataplot implements this command using the RANEQU algorithm described in Nijenhuis and Wilf (see Reference section below).
Note:
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.

Default:
None
Synonyms:
None
Related Commands:
 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.
Reference:
Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 12.
Applications:
Combinatorial Analysis
Implementation Date:
2008/6
Program:
```
LET N = 8
LET Y = RANDOM EQUIVALENCE RELATION
PRINT Y

```

Date created: 1/12/2009
Last updated: 1/12/2009