퍼머넌트(라이저 공식) 계산기

순열의 부호 sgn(σ)가 있느냐 없느냐뿐입니다. det는 Σ sgn(σ)·∏a[i][σ(i)]이고 perm은 부호를 뺀 Σ ∏a[i][σ(i)]입니다. 그런데 계산 난이도는 하늘과 땅 차이라, 행렬식은 가우스 소거로 O(n³)에 끝나고 퍼머넌트는 #P-완전입니다 — NP 문제를 모두 푸는 것보다도 어렵다고 여겨집니다.

행 연산이 값을 보존하지 않기 때문입니다. 행렬식은 «한 행에 다른 행의 상수배를 더해도 값이 그대로»라는 성질 덕분에 위삼각으로 만들어 대각선만 곱하면 되는데, 퍼머넌트에는 부호가 없어 상쇄가 일어나지 않고 그 성질이 성립하지 않습니다. 이 계산기에서 직접 행 연산을 해 보시면 행렬식은 그대로인데 퍼머넌트만 바뀌는 것이 보입니다.

순열을 모두 훑는 O(n!·n)을 O(2ⁿ·n)으로 줄입니다. n = 20이면 20! ≈ 2.4×10¹⁸과 2²⁰ ≈ 10⁶의 차이라 실용적으로 큽니다. 포함–배제로 «각 행이 고른 열의 집합»을 뒤집어 세는 것이고, 그레이 코드로 부분집합을 훑으면 한 칸 옮길 때 열 하나만 더하고 빼면 되어 안쪽 합을 다시 구하지 않아도 됩니다. 그래도 지수시간인 것은 그대로입니다.

이분 그래프의 완전매칭 개수입니다. a[i][j]를 «i번 사람이 j번 일을 맡을 수 있는가»로 읽으면 퍼머넌트가 사람과 일을 하나씩 짝지어 주는 방법의 수가 됩니다. 매칭이 «있는가»는 호프크로프트–카프로 다항시간에 풀리는데 «몇 개인가»는 #P-완전이라는 대비가 이 문제의 성격을 잘 보여 줍니다.

전부 1인 n×n 행렬의 퍼머넌트가 정확히 n!입니다. 모든 순열이 1을 주기 때문입니다. 반대로 같은 행렬의 행렬식은 0입니다. 대각선만 0이고 나머지가 1인 행렬은 퍼머넌트가 준계승 !n(교란순열의 개수)이 됩니다 — 4×4면 9, 5×5면 44입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.