Determine the number of transitions between conjugacy classes induced by scrambling three elements

Question118794a.java

// 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 ();
	}
    }
}

Question118794b.java

// 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 ();
	}
    }
}