Java (n = 8)
import java.util.*;
import java.util.concurrent.*;
public class HankelCombinatorics {
public static final int NUM_THREADS = 8;
private static final int[] FACT = new int[13];
static {
FACT[0] = 1;
for (int i = 1; i < FACT.length; i++) FACT[i] = i * FACT[i-1];
}
public static void main(String[] args) {
long prevElapsed = 0, start = System.nanoTime();
for (int i = 1; i < 12; i++) {
long count = count(i), elapsed = System.nanoTime() - start;
System.out.format("%d in %dms, total elapsed %dms\n", count, (elapsed - prevElapsed) / 1000000, elapsed / 1000000);
prevElapsed = elapsed;
}
}
@SuppressWarnings("unchecked")
private static long count(int n) {
int[][] perms = new int[FACT[n]][];
genPermsInner(0, 0, new int[n], perms, 0);
// We partition by canonical representation of the row sum multiset, discarding any with a density > 50%.
Map<CanonicalMatrix, Map<CanonicalMatrix, Integer>> part = new HashMap<CanonicalMatrix, Map<CanonicalMatrix, Integer>>();
for (int m = 0; m < 1 << (2*n-1); m++) {
int density = 0;
int[] key = new int[n];
for (int i = 0; i < n; i++) {
key[i] = Integer.bitCount((m >> i) & ((1 << n) - 1));
density += key[i];
}
if (2 * density <= n * n) {
CanonicalMatrix _key = new CanonicalMatrix(key);
Map<CanonicalMatrix, Integer> map = part.get(_key);
if (map == null) part.put(_key, map = new HashMap<CanonicalMatrix, Integer>());
map.put(new CanonicalMatrix(m, perms[0]), m);
}
}
List<Job> jobs = new ArrayList<Job>();
ExecutorService pool = Executors.newFixedThreadPool(NUM_THREADS);
for (Map.Entry<CanonicalMatrix, Map<CanonicalMatrix, Integer>> e : part.entrySet()) {
Job job = new Job(n, perms, e.getKey().sum() << 1 == n * n ? 0 : 1, e.getValue());
jobs.add(job);
pool.execute(job);
}
pool.shutdown();
try {
pool.awaitTermination(1, TimeUnit.DAYS); // i.e. until it's finished - inaccurate results are useless
}
catch (InterruptedException ie) {
throw new IllegalStateException(ie);
}
long total = 0;
for (Job job : jobs) total += job.subtotal;
return total;
}
private static int genPermsInner(int idx, int usedMask, int[] a, int[][] perms, int off) {
if (idx == a.length) perms[off++] = a.clone();
else for (int i = 0; i < a.length; i++) {
int m = 1 << (a[idx] = i);
if ((usedMask & m) == 0) off = genPermsInner(idx+1, usedMask | m, a, perms, off);
}
return off;
}
static class Job implements Runnable {
private volatile long subtotal = 0;
private final int n;
private final int[][] perms;
private final int shift;
private final Map<CanonicalMatrix, Integer> unseen;
public Job(int n, int[][] perms, int shift, Map<CanonicalMatrix, Integer> unseen) {
this.n = n;
this.perms = perms;
this.shift = shift;
this.unseen = unseen;
}
public void run() {
long result = 0;
int[][] perms = this.perms;
Map<CanonicalMatrix, Integer> unseen = this.unseen;
while (!unseen.isEmpty()) {
int m = unseen.values().iterator().next();
Set<CanonicalMatrix> equiv = new HashSet<CanonicalMatrix>();
for (int[] perm : perms) {
CanonicalMatrix canonical = new CanonicalMatrix(m, perm);
if (equiv.add(canonical)) {
result += canonical.weight() << shift;
unseen.remove(canonical);
}
}
}
subtotal = result;
}
}
static class CanonicalMatrix {
private final int[] a;
private final int hash;
public CanonicalMatrix(int m, int[] r) {
this(permuteRows(m, r));
}
public CanonicalMatrix(int[] a) {
this.a = a;
Arrays.sort(a);
int h = 0;
for (int i : a) h = h * 37 + i;
hash = h;
}
private static int[] permuteRows(int m, int[] perm) {
int[] cols = new int[perm.length];
for (int i = 0; i < perm.length; i++) {
for (int j = 0; j < cols.length; j++) cols[j] |= ((m >> (perm[i] + j)) & 1L) << i;
}
return cols;
}
public int sum() {
int sum = 0;
for (int i : a) sum += i;
return sum;
}
public int weight() {
int prev = -1, count = 0, weight = FACT[a.length];
for (int col : a) {
if (col == prev) weight /= ++count;
else {
prev = col;
count = 1;
}
}
return weight;
}
@Override public boolean equals(Object obj) {
// Deliberately unsuitable for general-purpose use, but helps catch bugs faster.
CanonicalMatrix that = (CanonicalMatrix)obj;
for (int i = 0; i < a.length; i++) {
if (a[i] != that.a[i]) return false;
}
return true;
}
@Override public int hashCode() {
return hash;
}
}
}
Zapisz jako HankelCombinatorics.java, skompiluj jako javac HankelCombinatorics.java, uruchom jako java -Xmx2G HankelCombinatorics.
Z NUM_THREADS = 4moją czterordzeniową maszyną trwa to 20420819767436od n=850 do 55 sekund, z dużą zmiennością między seriami; Oczekuję, że powinno to łatwo zarządzać tym samym na twoim komputerze z ośmiordzeniowym rdzeniem, ale zajmie to godzinę lub dłużej n=9.
Jak to działa
Biorąc pod uwagę n, istnieją macierze 2^(2n-1)binarne nx nHankela. Wiersze można permutować na n!różne sposoby, a kolumny na n!różne sposoby. Wszystko, co musimy zrobić, to uniknąć podwójnego liczenia ...
Jeśli obliczysz sumę każdego wiersza, to ani permutacja wierszy, ani permutacja kolumn nie zmieni multiset sum. Na przykład
0 1 1 0 1
1 1 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 1 0
ma {3, 3, 2, 2, 2}multiset sumy wierszy , podobnie jak wszystkie macierze Hankelable z niego pochodzące. Oznacza to, że możemy pogrupować macierze Hankela według tych multisets sumy wierszy, a następnie obsługiwać każdą grupę niezależnie, wykorzystując wiele rdzeni procesora.
Istnieje również użyteczna symetria: macierze z większą liczbą zer niż jedynki są wstrząsane z macierzami z większą liczbą zer niż zera.
Podwójnego zliczania występuje podczas Hankel matrycy M_1z rzędu permutacji r_1i kolumnę permutacji c_1odpowiada Hankel matrycę M_2z rzędu permutacji r_2i permutacji kolumnowej c_2(w liczbie do dwóch, lecz nie wszystkich trzech M_1 = M_2, r_1 = r_2, c_1 = c_2). Wiersz i kolumna permutacje są niezależne, więc jeśli zastosujemy wiersza permutacji r_1do M_1i wiersza permutacji r_2do M_2, kolumny jak multisets muszą być równe. Tak więc dla każdej grupy obliczam wszystkie wielokrotności kolumn uzyskane przez zastosowanie permutacji wiersza do macierzy w grupie. Prostym sposobem na uzyskanie kanonicznej reprezentacji multisets jest sortowanie kolumn, co jest również przydatne w następnym kroku.
Po uzyskaniu odrębnych multisets kolumnowych musimy dowiedzieć się, ile n!kombinacji każdego z nich jest unikalnych. W tym momencie podwójne liczenie może wystąpić tylko wtedy, gdy dany multiset kolumny ma zduplikowane kolumny: musimy policzyć liczbę wystąpień każdej odrębnej kolumny w multisecie, a następnie obliczyć odpowiedni współczynnik wielomianowy. Ponieważ kolumny są posortowane, łatwo jest policzyć.
Na koniec dodajemy je wszystkie.
Złożoność asymptotyczna nie jest łatwa do obliczenia z pełną precyzją, ponieważ musimy poczynić pewne założenia dotyczące zbiorów. Oceniamy według kolejności 2^(2n-2) n!multisets kolumn, zabierając n^2 ln nczas dla każdego (łącznie z sortowaniem); jeśli grupowanie nie zajmuje więcej niż ln nczynnik, mamy złożoność czasu Theta(4^n n! n^2 ln n). Ale ponieważ czynniki wykładnicze całkowicie dominują w przypadku wielomianów, tak właśnie jest Theta(4^n n!) = Theta((4n/e)^n).