Construct Matrix with given Permanent

[Albert Chan]

A follow up of previous post example, to produce recursive formula for permanent(m)

PM to JFG Wrote:Imagine row 8 is all 1's, and we move that to the end

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 0,0,1,1,0,0,0,0,0,1,0,1
23 DATA 0,0,1,1,0,0,0,0,0,1,1,1
24 DATA 1,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,1,0,1,1,1
26 DATA 1,0,1,1,1,0,0,1,0,1,1,1
27 DATA 1,0,1,1,1,0,1,1,0,1,1,1
28 DATA 1,0,1,1,1,0,1,1,1,1,1,1
29 DATA 1,0,1,1,1,1,1,1,1,1,1,1
30 DATA 1,1,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

1st row has 2 paths
After we pick a 1 from 1st row, 2nd row has 2 paths
After we pick a 1 from 2nd row, 3rd row has 2 paths
...
After we pick a 1 from 10th row, 11th row has 2 paths
After we pick a 1 from 11th row, 12th row has 1 paths

P of this matrix = 2^(12-1) = 2048

Back to original puzzle, if we flip row 8 bits (0↔1), code would calculate 2048-P
DATA required sorting bit population, we get this new setup:

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 1,0,1,0,0,0,0,0,0,0,1,0
23 DATA 0,0,1,1,0,0,0,0,0,1,0,1
24 DATA 0,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,0,0,1,1,1
26 DATA 1,0,1,1,0,0,0,1,0,1,1,1
27 DATA 1,0,1,1,1,0,0,1,0,1,1,1
28 DATA 1,0,1,1,1,0,1,1,0,1,1,1
29 DATA 1,0,1,1,1,0,1,1,1,1,1,1
30 DATA 1,0,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

Red Line goes from bit population of 9, down to 3.
Also, it get moved up the matrix, reduced search space.
With this setup, code run much faster (~ 5X)

We get 2048-P = 25      → P = 2023

Let f(x) = permanent of "standard form" matrix m, with first row bits = x
Let n = bit_length of x                // leading zeroes ignored

f(2^n-1) = 2^(n-1)                    // explained in quote      
f(x) = 2^(n-1) - f(2^n-1 - x)      // 2nd term argument = flip(x), smaller than x
f(x) = x, if x = 0 or 1                  // base case

(01-03-2024 06:06 PM)Albert Chan Wrote:  "First row" bits (if we move 8th row to top) for Permanent

> 0b11111100110 + 1

2023

f(0b111111001101)
= 2^11 - f(0b110010)
= 2^11 - 2^5 + f(1101)
= 2^11 - 2^5 + 2^3 - f(0b10)
= 2^11 - 2^5 + 2^3 - 2^1 + 1
= 2048 - 32 + 8 - 2 + 1
= 2023