Hankelable 매트릭스 수 계산 n행렬 항목이 함께 0또는 1. 대한 n =

배경

이진 Hankel 행렬0s와 1s 만 포함하는 일정한 기울기 대각선 (양의 경사 대각선)이있는 행렬입니다 . 예를 들어 5×5 바이너리 Hankel 매트릭스는 다음과 같습니다.

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

곳에 a, b, c, d, e, f, g, h, i있습니다 중 하나 0또는 1.

M 이 Hankel 행렬이 되도록 M 의 행과 열 순서의 순열이있는 경우 행렬 MHankelable 로 정의 해 봅시다 . 즉, 행 순서에 순열 하나를 적용하고 열에 다른 순열을 적용 할 수 있습니다.

도전

문제는 가능한 n 한 많은 가치 를 가진 n매트릭스에 의해 얼마나 많은 Hankelable 이 있는지 계산하는 것 n입니다.

산출

각 정수 n이 1 위로, 출력의 수와 Hankelable n 의해 n행렬 항목이 함께 0또는 1.

대한 n = 1,2,3,4,5답해야한다 2,12,230,12076,1446672. (코드를 생성하여 orlp에 감사합니다.)

시간 제한

내 컴퓨터에서 코드를 실행하고 1 분 후에 중지합니다. 정답을 최대 n 개의 값으로 출력하는 코드가 승리합니다. 시간 제한은 답변을 제공하는 n = 1최대 가치 까지 모든 것에 적용됩니다 n.

우승자는 4 월 18 일 토요일까지 최고의 답변이 될 것입니다.

타이 브레이커

최대의 동점 인 경우 n, 출력을 제공하는 데 걸리는 시간 n+1과 가장 빠른 것이 승리 하는 데 시간이 걸립니다 . 동일한 시간 내에 최대 n+11 초 이내에 실행하는 경우 첫 번째 제출이 승리합니다.

언어와 라이브러리

자유롭게 사용할 수있는 컴파일러 / 인터프리터 등이있는 모든 언어를 사용할 수 있습니다. Linux 및 Linux 용으로 무료로 제공되는 모든 라이브러리 용.

내 기계

내 컴퓨터에서 타이밍이 실행됩니다. 이것은 Asus M5A78L-M / USB3 메인 보드 (소켓 AM3 +, 8GB DDR3)의 AMD FX-8350 8 코어 프로세서에 설치된 표준 우분투입니다. 이것은 또한 코드를 실행할 수 있어야 함을 의미합니다. 결과적으로 쉽게 구할 수있는 무료 소프트웨어 만 사용하고 코드를 컴파일하고 실행하는 방법에 대한 전체 지침을 포함하십시오.

노트

모든 n x n 행렬을 반복하지 말고 각각에 내가 설명하는 속성이 있는지 감지하는 것이 좋습니다. 첫째, 너무 많고 둘째, 이 탐지를 수행하는 빠른 방법없는 것 같습니다 .

지금까지 선두 항목

  • Peter Taylor의 n = 8 자바
  • orlp에 의한 n = 5. 파이썬


답변

자바 (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;
        }
    }
}

다른 이름으로 저장하고 다른 이름 HankelCombinatorics.java으로 컴파일하고 다음 javac HankelCombinatorics.java으로 실행하십시오 java -Xmx2G HankelCombinatorics.

NUM_THREADS = 4내 쿼드 코어 시스템에서 그것을 얻을 수 20420819767436에 대한 n=850 ~ 55 초 실행 사이의 변화의 공정한 금액과 경과에; 나는 그것이 옥타 코어 머신에서 동일하게 관리해야하지만 얻을하는데 1 시간 이상이 걸릴 것으로 기대합니다 n=9.

작동 원리

을 감안할 때 n, 거기에 2^(2n-1)nX의 nHankel 행렬은. 행은 n!여러 방식으로, 열은 n!여러 방식 으로 순열 될 수 있습니다 . 우리가해야 할 일은 이중 계산을 피하는 것입니다 …

각 행의 합계를 계산하면 행을 바꾸거나 열을 바꾸지 않아도 여러 집합의 합계가 변경되지 않습니다. 예 :

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

는 row sum multiset을 가지며 {3, 3, 2, 2, 2}, 그로부터 파생 된 모든 Hankelable 행렬도 마찬가지입니다. 즉, 행 행 다중 집합으로 Hankel 행렬을 그룹화 한 다음 여러 프로세서 코어를 활용하여 각 그룹을 독립적으로 처리 할 수 ​​있습니다.

악용 가능한 대칭도 있습니다. 1보다 많은 0을 가진 행렬은 0보다 많은 1을 가진 행렬과 함께 사용됩니다.

Hankel 행렬 때 이중 계산 발생 M_1로우 순열 r_1및 열 순열 c_1Hankel 행렬 일치 M_2로우 순열 r_2및 열 순열 c_2(2 위로지만, 모든 세 M_1 = M_2, r_1 = r_2, c_1 = c_2). 행과 열 순열 우리가 행 순열 적용 그렇다면, 독립적 r_1으로 M_1및 행 순열 r_2로를 M_2, 열 멀티 세트로는 같아야합니다. 따라서 각 그룹에 대해 행 순열을 그룹의 행렬에 적용하여 얻은 모든 열 다중 집합을 계산합니다. 다중 집합을 정식으로 표현하는 쉬운 방법은 열을 정렬하는 것이므로 다음 단계에서도 유용합니다.

고유 한 열 다중 집합을 얻은 후에 n!는 각각 의 순열 수가 몇 개인지를 찾아야합니다 . 이 시점에서 이중 계산은 주어진 열 다중 집합에 중복 열이있는 경우에만 발생할 수 있습니다. 다중 집합에서 각 개별 열의 발생 횟수를 계산 한 다음 해당 다항 계수를 계산하는 것입니다. 열이 정렬되어 있으므로 계산하기가 쉽습니다.

마지막으로 모두 추가합니다.

세트에 대해 약간의 가정을해야하기 때문에 점근 적 복잡도를 정확하게 계산하는 것은 쉽지 않습니다. 우리는 각각의 시간 (소팅 포함)에 2^(2n-2) n!걸리는 열 다중 집합 의 순서를 평가합니다 n^2 ln n. 그룹화가 하나 이상의 ln n요소를 취하지 않으면 시간이 복잡 Theta(4^n n! n^2 ln n)합니다. 그러나 지수 요소가 다항식 요소를 완전히 지배하기 때문에 Theta(4^n n!) = Theta((4n/e)^n).


답변

파이썬 2/3

느린 언어로 꽤 순진한 접근 방식 :

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

을 입력하여 실행하십시오 python script.py.


답변

하스켈

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

Peter ‘s만큼이나 빠른 곳은 없습니다-그가 거기에 도착한 것은 매우 인상적인 설정입니다! 이제 더 많은 코드가 인터넷에서 복사되었습니다. 용법:

$ ghc -threaded hankell.hs
$ ./hankell