Wikipedia:Reference desk/Archives/Mathematics/2011 January 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 19

Satisfiability Problem

So I am testing a satisfiability program and I want it to return a permutation of S={1,2,3,4,5,6,7,8,9}. Any permutation is acceptable but it needs to be a permutation, meaning nothing should be repeated. My first thought was a naive one where I requires that all integers be between 1 and 9 (inclusive) and then just check all the elements against the rest to make sure that nothing is repeating. But that requires a bunch of tests so I was wondering if there any smart way of checking to see if a given list is a permutation of S. I was thinking more like check to see if the sum is 45 (but that allows something like {8,8,8,8,9,1,1,1,1}). Then I thought checking the sum to be 45 and the product of all the elements in the list to be 9!=362880 but that seems like it will take forever (and I also don't know if it will always guarantee a permutation). So what are some good (good can mean the simplest,easiest, shortest, easy to describe, easy to implement, or fast) ways for me to do this? Any suggestions?168.103.71.231 (talk) 22:40, 19 January 2011 (UTC)

What's wrong with just walking through the list, using an array of booleans to remember which numbers you've seen already? –Henning Makholm (talk) 23:14, 19 January 2011 (UTC)

If these two polynomials are identical:

$P_{1}(x)=(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9)$

$P_{2}(x)=(x-s_{1})(x-s_{2})(x-s_{3})(x-s_{4})(x-s_{5})(x-s_{6})(x-s_{7})(x-s_{8})(x-s_{9})$

then, and only then, is $(s_{1},s_{2},s_{3},s_{4},s_{5},s_{6},s_{7},s_{8},s_{9})$ a permutation of $(1,2,3,4,5,6,7,8,9)$. The fast way is to sort S. Bo Jacoby (talk) 23:17, 19 January 2011 (UTC).

Actually that's not the fastest way—sorting takes $\Omega (n\log n)$ time, while maintaining boolean flags and just walking through the list as Henning Makholm suggests above takes $\Theta (n)$ time. On the other hand, sorting might be the easiest solution to implement, if you already have access to a sort routine. —Bkell (talk) 06:30, 20 January 2011 (UTC)

I don't quite understand your situation, but if you are testing a constraint satisfier you found somewhere else (say, a commercial constraint satisfier or an open-source constraint satisfier or something, rather than a program you wrote yourself), you should look to see if it supports something called an "alldiff" constraint, which is a very common kind of constraint in the constraint-programming world. If it does, then your constraint can just be written $\mathrm {alldiff} (x_{1},x_{2},\ldots ,x_{9})$. Of course, if it's your own program you're testing, then this isn't helpful advice, and the advice above is better. —Bkell (talk) 06:25, 20 January 2011 (UTC)