Latar Belakang

Matriks Hankel biner adalah matriks dengan kemiringan diagonal konstan (diagonal miring positif) yang hanya mengandung 0s dan 1s. Contohnya matriks Hankel biner 5x5 terlihat seperti

a b c d e
b c d e f
c d e f g
d e f g h
e f g h i

mana a, b, c, d, e, f, g, h, iyang baik 0atau 1.

Mari kita mendefinisikan matriks M sebagai Hankelable jika ada permutasi urutan baris dan kolom M sehingga M adalah matriks Hankel. Ini berarti seseorang dapat menerapkan satu permutasi pada urutan baris dan yang mungkin berbeda pada kolom.

Tantangan

Tantangannya adalah untuk menghitung berapa banyak Hankelable n dengan nmatriks yang ada untuk semua nhingga nilai sebesar mungkin.

Keluaran

Untuk setiap bilangan bulat n dari 1 ke atas, output jumlah Hankelable n dengan nmatriks dengan entri yang 0atau 1.

Untuk n = 1,2,3,4,5jawabannya harus 2,12,230,12076,1446672. (Terima kasih kepada orlp untuk kode untuk menghasilkan ini.)

Batas waktu

Saya akan menjalankan kode Anda di mesin saya dan menghentikannya setelah 1 menit. Kode yang menampilkan jawaban yang benar hingga nilai n menang terbesar. Batas waktu adalah untuk semuanya, mulai n = 1dari nilai terbesar nyang Anda berikan jawabannya.

Pemenang akan menjadi jawaban terbaik pada akhir Sabtu 18 April.

Tie Breaker

Dalam kasus dasi untuk beberapa maksimum nsaya akan menghitung berapa lama waktu yang dibutuhkan untuk memberikan hasil n+1dan yang tercepat menang. Jika mereka berjalan dalam waktu yang sama hingga dalam satu detik hingga n+1, pengiriman pertama menang.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / juru bahasa / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga tersedia secara bebas untuk Linux.

Mesin saya

Pengaturan waktu akan dijalankan di mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350 pada Motherboard Asus M5A78L-M / USB3 (Socket AM3 +, 8GB DDR3). Ini juga berarti saya harus dapat menjalankan kode Anda. Sebagai konsekuensinya, hanya gunakan perangkat lunak gratis yang mudah tersedia dan harap sertakan instruksi lengkap cara menyusun dan menjalankan kode Anda.

Catatan

Saya merekomendasikan untuk tidak mengulangi semua matriks demi matriks dan mencoba mendeteksi apakah masing-masing memiliki properti yang saya jelaskan. Pertama, ada terlalu banyak dan kedua, sepertinya tidak ada cara cepat untuk melakukan deteksi ini .

Entri terkemuka sejauh ini

• n = 8 oleh Peter Taylor. Jawa
• n = 5 oleh orlp. Python

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;
        }
    }
}

Simpan sebagai HankelCombinatorics.java, kompilasi sebagai javac HankelCombinatorics.java, jalankan sebagai java -Xmx2G HankelCombinatorics.

Dengan NUM_THREADS = 4mesin quad-core saya mendapat 20420819767436untuk n=8di 50 sampai dengan 55 detik berlalu, dengan jumlah wajar variabilitas antara berjalan; Saya berharap bahwa itu harus dengan mudah mengelola hal yang sama pada mesin octa-core Anda tetapi akan memakan waktu satu jam atau lebih untuk mendapatkannya n=9.

Bagaimana itu bekerja

Mengingat n, ada matriks 2^(2n-1)biner nx nHankel. Baris dapat di permutasi dengan n!cara, dan kolom dengan n!cara. Yang perlu kita lakukan adalah menghindari penghitungan ganda ...

Jika Anda menghitung jumlah setiap baris, maka permutasi baris atau permutasi kolom tidak mengubah multiset jumlah. Misalnya

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

memiliki jumlah baris multiset {3, 3, 2, 2, 2}, dan demikian pula semua matriks Hankelable berasal darinya. Ini berarti bahwa kita dapat mengelompokkan matriks Hankel dengan multiset jumlah baris ini dan kemudian menangani setiap grup secara independen, mengeksploitasi beberapa inti prosesor.

Ada juga simetri yang dapat dieksploitasi: matriks dengan nol lebih banyak daripada yang ada di bijih dengan matriks dengan lebih banyak dari nol.

Penghitungan ganda terjadi ketika Hankel matriks M_1dengan baris permutasi r_1dan kolom permutasi c_1cocok Hankel matriks M_2dengan baris permutasi r_2dan kolom permutasi c_2(sampai dengan dua tapi tidak semua tiga M_1 = M_2, r_1 = r_2, c_1 = c_2). Baris dan kolom permutasi independen, jadi jika kita menerapkan baris permutasi r_1untuk M_1dan baris permutasi r_2untuk M_2, kolom sebagai multisets harus sama. Jadi untuk setiap grup, saya menghitung semua multiset kolom yang diperoleh dengan menerapkan permutasi baris ke matriks dalam grup. Cara mudah untuk mendapatkan representasi kanonik dari multiset adalah dengan menyortir kolom, dan itu juga berguna pada langkah berikutnya.

Setelah memperoleh multiset kolom yang berbeda, kita perlu menemukan berapa banyak n!permutasi dari masing-masing yang unik. Pada titik ini, penghitungan ganda hanya dapat terjadi jika multiset kolom yang diberikan memiliki kolom duplikat: apa yang perlu kita lakukan adalah menghitung jumlah kemunculan setiap kolom yang berbeda dalam multiset dan kemudian menghitung koefisien multinomial yang sesuai. Karena kolom diurutkan, mudah untuk menghitung.

Akhirnya kami menambahkan semuanya.

Kompleksitas asimptotik bukanlah hal sepele untuk dihitung dengan presisi penuh, karena kita perlu membuat beberapa asumsi tentang perangkat. Kami mengevaluasi urutan 2^(2n-2) n!multiset kolom, meluangkan n^2 ln nwaktu untuk masing-masing (termasuk penyortiran); jika pengelompokan tidak mengambil lebih dari satu ln nfaktor, kami memiliki kompleksitas waktu Theta(4^n n! n^2 ln n). Tetapi karena faktor eksponensial sepenuhnya mendominasi faktor polinomial, maka faktor itu Theta(4^n n!) = Theta((4n/e)^n).

Python2 / 3

Pendekatan yang cukup naif, dalam bahasa yang lambat:

import itertools

def permute_rows(m):
    for perm in itertools.permutations(m):
        yield perm

def permute_columns(m):
    T = zip(*m)
    for perm in itertools.permutations(T):
        yield zip(*perm)

N = 1
while True:
    base_template = ["abcdefghijklmnopqrstuvwxyz"[i:i+N] for i in range(N)]

    templates = set()
    for c in permute_rows(base_template):
        for m in permute_columns(c):
            templates.add("".join("".join(row) for row in m))

    def possibs(free, templates):
        if free == 2*N - 1:
            return set(int(t, 2) for t in templates)

        s = set()
        for b in "01":
            new_templates = set(t.replace("abcdefghijklmnopqrstuvwxyz"[free], b) for t in templates)
            s |= possibs(free + 1, new_templates)

        return s

    print(len(possibs(0, templates)))
    N += 1

Jalankan dengan mengetik python script.py.

Haskell

import Data.List
import Data.Hashable
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S

main = mapM putStrLn $ map (show.countHankellable) [1..]

a§b=[a!!i|i<-b]

hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
    where
      go _ []     = []
      go s (x:xs) = if x `S.member` s then go s xs
                                    else x : go (S.insert x s) xs

pmap = parMap rseq

makeMatrix :: Int->[Bool]->[[Bool]]
makeMatrix n vars = [vars§[i..i+n-1]|i<-[0..n-1]]

countHankellable :: Int -> Int
countHankellable n = let
    s = permutations [0..n-1]
    conjugates m = concat[permutations[r§q|r<-m]|q<-s]
    variableSets = sequence [[True,False]|x<-[0..2*(n-1)]]
 in
    length.hashNub.concat.pmap (conjugates.makeMatrix n ) $ variableSets

Tidak ada yang secepat Peter - itu pengaturan yang cukup mengesankan dia sampai di sana! Sekarang dengan lebih banyak kode yang disalin dari internet. Pemakaian:

$ ghc -threaded hankell.hs
$ ./hankell