net.cscott.sdr.calls
Class Permutation

java.lang.Object
  net.cscott.sdr.calls.Permutation

All Implemented Interfaces:

Comparable<Permutation>

public class Permutation
extends Object
implements Comparable<Permutation>

A Permutation represents a reordering of dancers.

Field Summary

static Permutation

IDENTITY8 The identity permutation for 8 dancers.

Method Summary

Permutation	canonical() The canonical form of a formation permutation is the smallest lexicographically among the four rotational equivalents.
int	compareTo(Permutation p) Compare two permutations lexicographically.
Permutation	divide(Permutation p)
boolean	equals(Object o)
static Permutation	fromFormation(Formation f) Generate a Permutation corresponding to the given formation.
static Iterator<Permutation>	generate(Permutation first) Generate all symmetric permutations.
int	hashCode()
static Permutation	identity(int size) The identity permutation for an arbitrary number of dancers.
Permutation	inverse() Invert a permutation.
boolean	isSymmetric()
Permutation	multiply(Permutation other) Compose a permutation.
Formation	permute(Formation f) Permute the given formation according to the specified permutation.
<T> void	permute(List<T> l) Permute the given list according to this permutation.
Iterator<Permutation>	rotated() Generate the four rotated versions of the given permutation.
String	toString() External representation is a string like "01234567".
static Permutation	valueOf(String p) Return a permutation corresponding to the given string.

Methods inherited from class java.lang.Object

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

Field Detail

IDENTITY8

public static Permutation IDENTITY8

The identity permutation for 8 dancers.

Tests:

js> Permutation.IDENTITY8.toString()
01234567
js> Permutation.IDENTITY8.inverse().toString()
01234567
js> Permutation.identity(8) === Permutation.IDENTITY8
true

Method Detail

toString

public String toString()

External representation is a string like "01234567".

Overrides:

toString in class Object

valueOf

public static Permutation valueOf(String p)

Return a permutation corresponding to the given string.

Tests:

js> Permutation.valueOf("01234567").equals(Permutation.IDENTITY8)
true

Test digits above 9

js> Permutation.valueOf("0123456789ABC").toString()
0123456789ABC

inverse

public Permutation inverse()

Invert a permutation.

Tests:

The identity transform is its own inverse.

js> Permutation.IDENTITY8.inverse().equals(Permutation.IDENTITY8)
true

Composing a permutation and its inverse results in identity.

js> p = Permutation.valueOf("13025746")
13025746
js> p.multiply(p.inverse())
01234567
js> p.inverse().multiply(p)
01234567

multiply

public Permutation multiply(Permutation other)

Compose a permutation. We use Knuth's order of operations (TAOCP 7.2.1.2) where alpha * beta means apply alpha first, then apply beta to the result.

Tests:

Clarify the order of operations:

js> a = Permutation.valueOf('250143')
250143
js> // b is the 'reflection' permutation
js> b = Permutation.valueOf('543210')
543210
js> // a*b is "apply b after a"
js> a.multiply(b)
305412
js> // b*a is 'a' reflected (apply b *to* a)
js> b.multiply(a)
341052

Applying a permutation to IDENTITY results in itself.

js> p = Permutation.valueOf("13025746");
13025746
js> Permutation.IDENTITY8.multiply(p)
13025746

Applying IDENTITY leaves a permutation unchanged.

js> p = Permutation.valueOf("13025746");
13025746
js> p.multiply(Permutation.IDENTITY8)
13025746

divide

public Permutation divide(Permutation p)

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

compareTo

public int compareTo(Permutation p)

Compare two permutations lexicographically.

Specified by:

compareTo in interface Comparable<Permutation>

Tests:

Permutations of shorter sequences are smaller.

js> importPackage(java.util);
js> l=Arrays.asList(Permutation.valueOf("01"), Permutation.valueOf("0"), Permutation.valueOf("012"))
[01, 0, 012]
js> Collections.sort(l)
js> l
[0, 01, 012]

Permutations of the same length are compared left to right:

js> importPackage(java.util)
js> l=Arrays.asList(Permutation.valueOf("012"), Permutation.valueOf("201"), Permutation.valueOf("120"))
[012, 201, 120]
js> Collections.sort(l)
js> l
[012, 120, 201]

identity

public static Permutation identity(int size)

The identity permutation for an arbitrary number of dancers.

Tests:

js> Permutation.identity(2)
01
js> Permutation.identity(4)
0123
js> Permutation.identity(8)
01234567
js> Permutation.identity(16)
0123456789ABCDEF

permute

public <T> void permute(List<T> l)

Permute the given list according to this permutation.

Tests:

Reverse a list:

js> importPackage(java.util);
js> l = Arrays.asList("A","B","C","D","E");
[A, B, C, D, E]
js> p = Permutation.valueOf("43210");
43210
js> p.permute(l)
js> l
[E, D, C, B, A]

isSymmetric

public boolean isSymmetric()

Tests:

js> Permutation.valueOf("01234567").isSymmetric()
true
js> Permutation.fromFormation(Formation.SQUARED_SET).isSymmetric()
true
js> Permutation.valueOf("10234567").isSymmetric()
false

fromFormation

public static Permutation fromFormation(Formation f)

Generate a Permutation corresponding to the given formation.

Tests:

The permutation corresponding to a squared set is almost the identity permutation:

js> Permutation.fromFormation(Formation.SQUARED_SET);
12345670

permute

public Formation permute(Formation f)

Permute the given formation according to the specified permutation.

Tests:

js> p = Permutation.valueOf("23456701") // rotate 1/4
23456701
js> f = Formation.SQUARED_SET; f.toStringDiagram()
     3Gv  3Bv

4B>            2G<

4G>            2B<

     1B^  1G^
js> p.permute(f).toStringDiagram()
     4Gv  4Bv

1B>            3G<

1G>            3B<

     2B^  2G^

generate

public static Iterator<Permutation> generate(Permutation first)

Generate all symmetric permutations. There are 96, if we rule out permutations where the heads and sides can be swapped. Dancer n's opposite is Dancer 4+n.

Tests:

Count the number of permutations

js> p = Permutation.IDENTITY8
01234567
js> [pp for each (pp in Iterator(Permutation.generate(p)))].length
96

Ensure they are unique:

js> o = {}
[object Object]
js> i=0
0
js> for each (pp in Iterator(Permutation.generate(Permutation.valueOf("01234567")))) {
  >   for each (rp in Iterator(pp.rotated())) {
  >     if (rp.toString() in o) throw new Error(i+" "+rp+" not unique!");
  >     o[rp.toString()] = rp;
  >   }
  >   i++;
  > }; i
96

Ensure they are symmetric:

js> p = Permutation.IDENTITY8
01234567
js> p = [pp for each (pp in Iterator(Permutation.generate(p)))]; p.length
96
js> p.every(function(pp) { return pp.isSymmetric(); })
true

Ensure that each permutation returned is canonical

js> for each (pp in Iterator(Permutation.generate(Permutation.valueOf("01234567")))) {
  >   if (pp.canonical() !== pp)
  >     throw new Error("Not canonical! "+pp);
  > }; "OK";
OK

Generate permutations of normal in-sequence RH ocean waves:

js> const SD = StandardDancer;
js> FormationList = FormationList.js(this); undefined;
js> f = FormationList.PARALLEL_RH_WAVES; undefined
js> f = f.mapStd([SD.COUPLE_2_BOY, SD.COUPLE_2_GIRL,
  >               SD.COUPLE_1_GIRL, SD.COUPLE_1_BOY]
  >              ); f.toStringDiagram()
2B^  2Gv  1G^  1Bv

3B^  3Gv  4G^  4Bv
js> p = Permutation.IDENTITY8;
01234567
js> fs = [pp.permute(f) for each
  >       (pp in Iterator(Permutation.generate(p)))]; fs.length
96
js> fs[0].toStringDiagram()
2B^  2Gv  1G^  1Bv

3B^  3Gv  4G^  4Bv
js> fs[1].toStringDiagram()
2G^  2Bv  1G^  1Bv

3B^  3Gv  4B^  4Gv
js> fs[95].toStringDiagram()
3G^  2Gv  2B^  3Bv

1B^  4Bv  4G^  1Gv

rotated

public Iterator<Permutation> rotated()

Generate the four rotated versions of the given permutation.

Tests:

js> [p for each (p in Iterator(Permutation.valueOf("01234567").rotated()))]
01234567,23456701,45670123,67012345

canonical

public Permutation canonical()

The canonical form of a formation permutation is the smallest lexicographically among the four rotational equivalents.

Tests:

js> Permutation.valueOf("23456701").canonical()
01234567
js> [p.canonical() for each (p in Iterator(Permutation.valueOf("23456701").rotated()))]
01234567,01234567,01234567,01234567