Skip to content

Instantly share code, notes, and snippets.

@joriki
Created July 2, 2015 07:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save joriki/a9fd5ea8f60ebfdfb06f to your computer and use it in GitHub Desktop.
Save joriki/a9fd5ea8f60ebfdfb06f to your computer and use it in GitHub Desktop.
Calculate the number of permutation recipes that have a given effect (see http://math.stackexchange.com/questions/769362)
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class Question769362 {
final static String from = "cat";
final static String to = "abc";
final static int n = 26;
public static void main (String [] args) {
Map<String,BigInteger> counts = new HashMap<String,BigInteger> ();
counts.put (from,BigInteger.ONE);
for (int i = 0;i < n;i++) {
Map<String,BigInteger> newCounts = new HashMap<String,BigInteger> ();
char c = (char) ('a' + i);
for (int j = 0;j < n;j++)
if (j != i) {
char d = (char) ('a' + j);
for (Map.Entry<String,BigInteger> entry : counts.entrySet ()) {
String s = entry.getKey ();
BigInteger count = entry.getValue ();
s = s.replace (c,'*');
s = s.replace (d,c);
s = s.replace ('*',d);
newCounts.compute (s,(k,v) -> (v == null ? count : count.add (v)));
}
}
counts = newCounts;
}
System.out.println (counts.getOrDefault (to,BigInteger.ZERO));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment