sdr 0.7

net.cscott.sdr.calls
Class Permutation

java.lang.Object
  extended by 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

sdr 0.7

Copyright © 2006-2009 C. Scott Ananian