Skip to content

Instantly share code, notes, and snippets.

@joriki
Created March 11, 2012 15:03
Show Gist options
  • Save joriki/2016748 to your computer and use it in GitHub Desktop.
Save joriki/2016748 to your computer and use it in GitHub Desktop.
Determine the number of transitions between conjugacy classes induced by scrambling three elements
// This version counts the transitions by tallying the different ways in which the scrambling can rearrange the cycles
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Partition {
List<Integer> parts = new ArrayList<Integer> ();
// generate all partitions of n according to The Art of Computer Programming by Donald E. Knuth, Algorithm P on p. 2 of http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz
public static List<Partition> generatePartitions (int n) {
List<Partition> partitions = new ArrayList<Partition> ();
int [] a = new int [n + 1];
int q,x,m = 1;
for (;;) {
a [m] = n;
q = m;
if (n == 1)
q--;
for (;;) {
Partition partition = new Partition ();
for (int i = 1;i <= m;i++)
partition.parts.add (a [i]);
partitions.add (partition);
if (a [q] != 2)
break;
a [q] = 1;
q--;
m++;
a [m] = 1;
}
if (q == 0)
break;
x = a [q] - 1;
a [q] = x;
n = m - q + 1;
m = q + 1;
while (n > x) {
a [m] = x;
m++;
n -= x;
}
}
return partitions;
}
private void canonicalize () {
Collections.sort (parts);
}
public boolean equals (Object o) {
if (!(o instanceof Partition))
return false;
Partition p = (Partition) o;
canonicalize ();
p.canonicalize ();
return p.parts.equals (parts);
}
public int hashCode () {
canonicalize ();
return parts.hashCode ();
}
public String toString () {
canonicalize ();
StringBuffer buffer = new StringBuffer ();
for (int part : parts) {
if (buffer.length () != 0)
buffer.append ('+');
buffer.append (part);
}
return buffer.toString ();
}
}
public class Question118794a {
public static void main (String [] args) {
int n = Integer.parseInt (args [0]);
List<Partition> partitions = Partition.generatePartitions (Integer.parseInt (args [0]));
Map<Partition,Integer> indices = new HashMap<Partition,Integer> ();
int npartitions = partitions.size ();
for (int i = 0;i < npartitions;i++)
indices.put (partitions.get (i),i);
int [] [] transitions = new int [npartitions] [npartitions]; // transitions [i] [j] is the number of transitions from i to j
// for each conjugacy class, figure out which other conjugacy classes it can transition to when composed with scrambling of three elements
for (Partition partition : partitions) {
int index = indices.get (partition);
System.out.println (index + " : " + partition);
List<Integer> parts = partition.parts;
// first case: identity permutation
transitions [index] [index] += (n * (n - 1) * (n - 2)) / 6; // number of ways to select three different random elements
// second case : transposition
// first subcase : one part is split
for (int part : parts) // loop over all parts ...
if (part > 1)
// ... and all ways to split them up
for (int i = 1;i < part;i++)
for (int j = 0;j < i;j++)
if (j != i) {
Partition split = new Partition ();
split.parts.addAll (parts);
split.parts.remove (new Integer (part));
split.parts.add ((part + i - j) % part);
split.parts.add ((part + j - i) % part);
transitions [index] [indices.get (split)] += n - 2; // number of ways to select the third element
}
// second subcase : two parts are joined
// loop over all unordered pairs of parts to join
// this could be done in the other loop by looping over the joint part instead, but that would require some error-prone counting
for (int i = 1;i < parts.size ();i++)
for (int j = 0;j < i;j++) {
int part1 = parts.get (i);
int part2 = parts.get (j);
Partition joint = new Partition ();
joint.parts.addAll (parts);
joint.parts.remove (new Integer (part1));
joint.parts.remove (new Integer (part2));
joint.parts.add (part1 + part2);
transitions [index] [indices.get (joint)] += (n - 2) * part1 * part2;
}
// third case : 3-cycle
// first subcase: one part is split into three
for (int part : parts) // loop over all parts ...
if (part > 2)
for (int i = 2;i < part;i++) // ... and over all ways to split it into three
for (int j = 1;j < i;j++)
for (int k = 0;k < j;k++) {
Partition split = new Partition ();
split.parts.addAll (parts);
split.parts.remove (new Integer (part));
split.parts.add ((part + i - j) % part);
split.parts.add ((part + j - k) % part);
split.parts.add ((part + k - i) % part);
transitions [index] [indices.get (split)]++;
transitions [index] [index]++; // if the points are permuted in the opposite order, the cycle doesn't change length
}
// second subcase: part of one part is spliced into another
for (int i = 0;i < parts.size ();i++) // loop over all ordered pairs of parts...
for (int j = 0;j < parts.size ();j++)
if (j != i) {
int part1 = parts.get (i);
int part2 = parts.get (j);
if (part1 > 1)
for (int k = 0;k < part1;k++) // and over all ways to splice a part out of the first
for (int l = 0;l < part1;l++)
if (l != k) {
Partition spliced = new Partition ();
spliced.parts.addAll (parts);
spliced.parts.remove (new Integer (part1));
spliced.parts.remove (new Integer (part2));
spliced.parts.add (part2 + ((part1 + k - l) % part1));
spliced.parts.add ((part1 + l - k) % part1);
transitions [index] [indices.get (spliced)] += part2; // number of ways of selecting the element in the second part
}
}
// third subcase: three parts are joined into one
for (int i = 2;i < parts.size ();i++) // loop over all unordered triples of parts to join
for (int j = 1;j < i;j++)
for (int k = 0;k < j;k++) {
int part1 = parts.get (i);
int part2 = parts.get (j);
int part3 = parts.get (k);
Partition joint = new Partition ();
joint.parts.addAll (parts);
joint.parts.remove (new Integer (part1));
joint.parts.remove (new Integer (part2));
joint.parts.remove (new Integer (part3));
joint.parts.add (part1 + part2 + part3);
transitions [index] [indices.get (joint)] += 2 * part1 * part2 * part3; // two possible orders of the three elements
}
}
System.out.println ();
for (int i = 0;i < npartitions;i++) {
for (int t : transitions [i])
System.out.print (t + " ");
System.out.println ();
}
}
}
// This version counts the transitions by brute force by applying all possible scramblings of three elements to a permutation in a given conjugacy class and determining the conjugacy classes of the results
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Partition {
List<Integer> parts = new ArrayList<Integer> ();
// generate all partitions of n according to The Art of Computer Programming by Donald E. Knuth, Algorithm P on p. 2 of http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz
public static List<Partition> generatePartitions (int n) {
List<Partition> partitions = new ArrayList<Partition> ();
int [] a = new int [n + 1];
int q,x,m = 1;
for (;;) {
a [m] = n;
q = m;
if (n == 1)
q--;
for (;;) {
Partition partition = new Partition ();
for (int i = 1;i <= m;i++)
partition.parts.add (a [i]);
partitions.add (partition);
if (a [q] != 2)
break;
a [q] = 1;
q--;
m++;
a [m] = 1;
}
if (q == 0)
break;
x = a [q] - 1;
a [q] = x;
n = m - q + 1;
m = q + 1;
while (n > x) {
a [m] = x;
m++;
n -= x;
}
}
return partitions;
}
// return some permutation whose conjugacy class corresponds to this partition
public Permutation getPermutation () {
int total = 0;
for (int part : parts)
total += part;
Permutation permutation = new Permutation (total);
int offset = 0;
for (int part : parts) {
for (int i = 0;i < part;i++)
permutation.p [offset + i] = offset + (i + 1) % part;
offset += part;
}
return permutation;
}
private void canonicalize () {
Collections.sort (parts);
}
public boolean equals (Object o) {
if (!(o instanceof Partition))
return false;
Partition p = (Partition) o;
canonicalize ();
p.canonicalize ();
return p.parts.equals (parts);
}
public int hashCode () {
canonicalize ();
return parts.hashCode ();
}
public String toString () {
canonicalize ();
StringBuffer buffer = new StringBuffer ();
for (int part : parts) {
if (buffer.length () != 0)
buffer.append ('+');
buffer.append (part);
}
return buffer.toString ();
}
}
class Permutation {
int [] p;
public Permutation (int n) {
p = new int [n];
}
public Permutation (Permutation p1,Permutation p2) {
this (p1.p.length);
if (p1.p.length != p2.p.length)
throw new IllegalArgumentException ();
for (int i = 0;i < p1.p.length;i++)
p [i] = p1.p [p2.p [i]];
}
public Partition getConjugacyClass () {
Partition conjugacyClass = new Partition ();
boolean [] done = new boolean [p.length];
for (int i = 0;i < p.length;i++)
if (!done [i]) {
int length = 0;
int j = i;
do {
length++;
j = p [j];
done [j] = true;
} while (j != i);
conjugacyClass.parts.add (length);
}
return conjugacyClass;
}
public String toString () {
StringBuffer buffer = new StringBuffer ();
for (int i : p) {
if (buffer.length () != 0)
buffer.append (' ');
buffer.append (i);
}
return buffer.toString ();
}
}
public class Question118794b {
public static void main (String [] args) {
int n = Integer.parseInt (args [0]);
List<Partition> partitions = Partition.generatePartitions (Integer.parseInt (args [0]));
Map<Partition,Integer> indices = new HashMap<Partition,Integer> ();
int npartitions = partitions.size ();
for (int i = 0;i < npartitions;i++)
indices.put (partitions.get (i),i);
int [] [] transitions = new int [npartitions] [npartitions]; // transitions [i] [j] is the number of transitions from i to j
for (Partition partition : partitions) {
int index = indices.get (partition);
System.out.println (index + " : " + partition);
Permutation permutation = partition.getPermutation ();
Permutation shuffle = new Permutation (n);
int [] i = new int [3];
for (int [] p : new int [] [] {{0,1,2},{1,0,2},{2,0,1},{0,2,1},{1,2,0},{2,1,0}})
for (i [0] = 2;i [0] < n;i [0]++)
for (i [1] = 1;i [1] < i [0];i [1]++)
for (i [2] = 0;i [2] < i [1];i [2]++) {
for (int j = 0;j < n;j++)
shuffle.p [j] = j;
for (int j = 0;j < 3;j++)
shuffle.p [i [j]] = i [p [j]];
Permutation shuffled = new Permutation (shuffle,permutation);
transitions [indices.get (permutation.getConjugacyClass ())] [indices.get (shuffled.getConjugacyClass ())]++;
}
}
System.out.println ();
for (int i = 0;i < npartitions;i++) {
for (int t : transitions [i])
System.out.print (t + " ");
System.out.println ();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment