Problem 631: Constrained Permutations

Mathematical Foundation

Theorem 1 (Ryser, 1963). For any $n \times n$ matrix $A$,

Proof. For each subset $S \subseteq [n]$, expand the product $\prod_{i=1}^{n} \bigl(\sum_{j \in S} A_{ij}\bigr)$ as a sum over functions $f : [n] \to S$:

Now consider a fixed bijection $\sigma \in S_n$. The term $\prod_{i} A_{i,\sigma(i)}$ appears in the inner sum whenever $\operatorname{range}(\sigma) \subseteq S$, i.e., $S = [n]$ since $\sigma$ is a bijection. So its contribution to the alternating sum is

For a non-injective function $f : [n] \to S$ with $|\operatorname{range}(f)| = r < n$, the function appears in every $S \supseteq \operatorname{range}(f)$. By inclusion-exclusion, the contribution over all $S$ is

since $n - r \geq 1$. Therefore only bijections survive, yielding $(-1)^n \cdot (-1)^n \operatorname{perm}(A) = \operatorname{perm}(A)$. $\square$

Lemma 1 (Gray Code Update). If subsets of $[n]$ are enumerated in Gray code order, consecutive subsets differ by exactly one element. The row sums $r_i(S) = \sum_{j \in S} A_{ij}$ can therefore be updated in $O(n)$ per transition.

Proof. Let $S' = S \oplus \{j_0\}$ for some $j_0$. Then $r_i(S') = r_i(S) \pm A_{i,j_0}$ for each $i \in [n]$, requiring $n$ additions. The product $\prod_i r_i(S')$ is then computed in $O(n)$. $\square$

Lemma 2 (Bipartite Matching Equivalence). $\operatorname{perm}(A)$ equals the number of perfect matchings in the bipartite graph $G = (U \cup V, E)$ where $U = \{u_1, \ldots, u_n\}$ (positions), $V = \{v_1, \ldots, v_n\}$ (elements), and $(u_i, v_j) \in E$ iff $A_{ij} = 1$.

Proof. A perfect matching $M$ in $G$ is a bijection $\sigma$ with $(u_i, v_{\sigma(i)}) \in E$ for all $i$, i.e., $A_{i,\sigma(i)} = 1$ for all $i$. Summing over all such bijections gives $\operatorname{perm}(A)$. $\square$

Editorial

Compute the permanent of a 0-1 matrix using Ryser’s formula: perm(A) = (-1)^n * sum_{S} (-1)^|S| * prod_i (sum_{j in S} A_ij) Method 1: Ryser’s formula O(2^n * n) Method 2: Brute force O(n! * n) (verification). We ryser’s formula with Gray code enumeration. Finally, else.

Pseudocode

Ryser's formula with Gray code enumeration
if j0 was added to S
else

Complexity Analysis

• Time: $O(2^n \cdot n)$. There are $2^n$ subsets; each transition updates $n$ row sums and computes an $n$-fold product.
• Space: $O(n)$ for storing the row sums and the matrix $A$.

For comparison, the naive summation over all $n!$ permutations costs $O(n! \cdot n)$.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * Problem 631: Constrained Permutations
 *
 * Compute the permanent of a 0-1 matrix via Ryser's formula:
 * perm(A) = (-1)^n * sum_{S} (-1)^|S| * prod_i (sum_{j in S} A_ij)
 *
 * Complexity: O(2^n * n)
 */

ll permanent_ryser(vector<vector<int>>& A) {
    int n = A.size();
    ll total = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int bits = __builtin_popcount(mask);
        ll prod = 1;
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = 0; j < n; j++)
                if (mask & (1 << j))
                    s += A[i][j];
            prod *= s;
        }
        if ((n - bits) % 2 == 0) total += prod;
        else total -= prod;
    }
    if (n % 2 == 1) total = -total;
    return total;
}

// Brute force (verification for small n)
ll permanent_brute(vector<vector<int>>& A) {
    int n = A.size();
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    ll total = 0;
    do {
        ll prod = 1;
        for (int i = 0; i < n; i++) prod *= A[i][perm[i]];
        total += prod;
    } while (next_permutation(perm.begin(), perm.end()));
    return total;
}

int main() {
    // Test: identity matrix
    vector<vector<int>> I3 = {{1,0,0},{0,1,0},{0,0,1}};
    assert(permanent_ryser(I3) == 1);
    assert(permanent_brute(I3) == 1);

    // Test: all-ones matrix
    vector<vector<int>> J3 = {{1,1,1},{1,1,1},{1,1,1}};
    assert(permanent_ryser(J3) == 6);
    assert(permanent_brute(J3) == 6);

    // Random tests
    srand(42);
    for (int trial = 0; trial < 50; trial++) {
        int n = 2 + rand() % 5;
        vector<vector<int>> A(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                A[i][j] = rand() % 2;
        assert(permanent_ryser(A) == permanent_brute(A));
    }

    cout << "All verifications passed." << endl;
    return 0;
}

"""
Problem 631: Constrained Permutations

Compute the permanent of a 0-1 matrix using Ryser's formula:
    perm(A) = (-1)^n * sum_{S} (-1)^|S| * prod_i (sum_{j in S} A_ij)

Method 1: Ryser's formula O(2^n * n)
Method 2: Brute force O(n! * n) (verification)
"""

from itertools import permutations

# --- Method 1: Ryser's formula ---
def permanent_ryser(A):
    """Compute permanent via Ryser's formula."""
    n = len(A)
    # perm = (-1)^n * sum over subsets S of (-1)^|S| * prod_i (row_sum_i restricted to S)
    result = 0
    for mask in range(1 << n):
        bits = bin(mask).count('1')
        sign = (-1) ** (n - bits)
        prod = 1
        for i in range(n):
            row_sum = 0
            for j in range(n):
                if mask & (1 << j):
                    row_sum += A[i][j]
            prod *= row_sum
        result += sign * prod
    return result * ((-1) ** n) if False else result
    # Actually the standard Ryser formula:
    # perm(A) = (-1)^n sum_{S subset [n]} (-1)^|S| prod_i sum_{j in S} A_ij

def permanent_ryser_correct(A):
    n = len(A)
    total = 0
    for mask in range(1 << n):
        bits = bin(mask).count('1')
        sign = (-1) ** (n - bits)
        prod = 1
        for i in range(n):
            s = sum(A[i][j] for j in range(n) if mask & (1 << j))
            prod *= s
        total += sign * prod
    return total * ((-1) ** n)

# --- Method 2: Brute force ---
def permanent_brute(A):
    """Compute permanent by summing over all permutations."""
    n = len(A)
    total = 0
    for perm in permutations(range(n)):
        prod = 1
        for i in range(n):
            prod *= A[i][perm[i]]
        total += prod
    return total

# Verify
# Identity matrix: perm = 1
I3 = [[1,0,0],[0,1,0],[0,0,1]]
assert permanent_ryser_correct(I3) == 1
assert permanent_brute(I3) == 1

# All-ones matrix: perm = n!
J3 = [[1,1,1],[1,1,1],[1,1,1]]
assert permanent_ryser_correct(J3) == 6
assert permanent_brute(J3) == 6

# Random 0-1 matrices
import random
random.seed(42)
for _ in range(20):
    n = random.randint(2, 6)
    A = [[random.randint(0, 1) for _ in range(n)] for _ in range(n)]
    assert permanent_ryser_correct(A) == permanent_brute(A)

print("All verifications passed.")