Tag Info

Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one: Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq ... 6 This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ... 1 Multilinear polynomials If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing. You want to test whether$f(x)=g(x)$holds for all$x$, where$f,g$are multilinear oolynomials. This is an instance of the polynomial identity testing problem. There are effective randomized algorithms for ... 0 Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings$S$and$T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest. One way to detect if a sequence forms a valid balanced parenthesis is to change ( for +1 and ) for -1 and ... 0 it's possible that a clever method of indicating which permutation to use could get below the full 73 bits No, because encoding the permutation/relabelling/rotation/whatever takes you back to 73 bits. Off the top of my head, I'm guessing there are 8 possible symmetries. Then assuming that you need two permutations (rows and columns?) and one relabelling:$$... 1 Here's a no-table method that combines a 75-bit encoding of the solution grid with an 81-bit encoding of which cells are clues to give a 156 bit fixed-length encoding for all puzzles ( also see below for further development of a variable length encoder for the clue positions which needs 73.1 bits on average instead of 81, yielding 148.1 overall with an ... 0 I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed. -1 EDIT: As pointed out in the comments this doesn't work! Copy your graph into$G'$and for every triple of nodes$(u,v,w)$, if NotBetween$(u,v,w)$then add the edges$v\rightarrow u$and$w\rightarrow v$to$G'$(if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph$G'\$ is a valid ...