问题描述:

How can I invert a binary equation, such that I can find which inputs will produce a given output.

Example:

`Inputs: i0 through i8`

Outputs: o0 through o8

Operators: ^ = XOR, & = AND

Binary equations:

`(1&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o0`

(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o1

(0&i0) ^ (1&i1) ^ (1&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o2

(1&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o3

(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o4

(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o5

(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (1&i6) ^ (0&i7) ^ (0&i8) = o6

(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (1&i6) ^ (1&i7) ^ (0&i8) = o7

(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (1&i8) = o8

In matrix form:

`1,1,0,1,0,0,0,0,0,1`

0,1,0,1,1,0,0,0,0,1

0,1,1,0,0,1,0,0,0,1

1,0,0,1,0,0,0,0,0,1

0,1,0,1,1,0,0,0,0,1

0,0,0,0,0,1,0,0,0,1

0,0,0,1,0,0,1,0,0,1

0,0,0,1,1,0,1,1,0,1

0,0,0,0,0,1,0,0,1,1

Additional limitations:

- The prime diagonal is always 1
- I am interested if there is a solution or not, more then the solution itself

How can I, algorithmically find inputs i0 -i8 such that outputs o0 - o8 are 1? What I really want to find is if there is such a solution or not.

I need an algorithm which is scalable to larger networks, at least up to 100 inputs/outputs.

With XOR (rather than OR), it seems at first glance that some form of Gauss–Jordan elimination can at least simplify the problem. Adapting the pseudocode from the Wikipedia article on reduced row echelon form, we get:

```
function ToReducedRowEchelonForm(Matrix M) is
// 'lead' is the column index in a row of the leading 1
lead := 0
rowCount := the number of rows in M
columnCount := the number of columns in M
for 0 ≤ r < rowCount do
if columnCount ≤ lead then
stop
end if
i = r
// Find row with lead point
while M[i, lead] = 0 do
i = i + 1
if rowCount = i then
// no pivot in this column, move to next
i = r
lead = lead + 1
if columnCount = lead then
stop
end if
end if
end while
Swap rows i and r
for 0 ≤ i < rowCount do
if i ≠ r do
Set row i to row i XOR row r
end if
end for
lead = lead + 1
end for
end function
```

This converts the sample to:

```
1,0,0,0,0,0,0,1,0,0
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,1,0,0,0,1,0,1
0,0,0,0,1,0,0,1,0,0
0,0,0,0,0,1,0,0,0,1
0,0,0,0,0,0,1,1,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,0
```

From there, you could adapt an integer partitioning algorithm to generate the possible inputs for a row, taking in to account the partitions for previous rows. Generating a partition is a great candidate for memoization.

Still need to do a timing analysis to see if the above is worthwhile.

One interesting thing about `xor`

is that:

```
a ^ b ^ b = a
```

This allows for nice manipulations, let's say you have:

```
a ^ b = c
```

Then you can easily figure out `a`

by `xor`

ing both sides with `b`

, getting:

```
a = c ^ b
```

If I was in your place, I'd use this trick to get the input from the outputs. The `and`

ing that appears in your equations only have the effect of *removing* some input variables from some equations, so it poses no problem to this approach.

First off, you must know, there **might not be a solution for particular coefficient matrices**, for example, if the input never appears in any equation (that is, a column of all-zeros in the matrix), or if an equation appears twice (that is, two identical rows), or if an equation is a combination of two other equations.

Now, assuming the matrix you have **does** yield a solution to your problem, the approach would be use each equation to find one of the inputs. For each equation, `xor`

both sides for all the inputs except one input (and varry this input for each equation). For example, let's say I want to use the first equation to find `i0`

and the second to find `i1`

(notice the input has to appear in the equation to make this value), I would now have:

```
i0 = o0 ^ i1 ^ i3
i1 = o1 ^ i3 ^ i4
```

Continue for the other equations, then substitute all inputs on the right side with their values from the equations. Repeat recursively till the right side only contains outputs. If you repeat for all equations, you'll find the values of all inputs.

I am **sure** this approach can be optimized using already-established methods in solving a linear system of equations, especially utilizing the matrix form.

You can solve the 2-SAT problem in polynomial time, see here.

Here's the link to a paper with a fast algorithm (heavy math I'll keep looking for a better link).

Another link with heavy math and pseudocode.

Edit: While I found many papers on this I didn't see much implementable code. Most of the work was on proving satisfiability. You'll probably have to streamline the clauses (remove the ones with zeroes on each run), then use a recursive algorithm to prove unsatifiability, and if you find you've satifisfied it, then you've solved it.

您可能感兴趣的文章：

- Can you do website manipulation with javascript or actionscript?
- c# - Custom Header Variables being cached on ASP.net Page
- connecting to a URL in Java through a proxy
- architecture - What are the rules of thumb when trying to decide if developing on Google App Engine platform is worthwhile
- jquery - Javascript file stops rest of javascript from working
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**