Re: Speeding-up FindInstance
- To: mathgroup at smc.vnet.net
- Subject: [mg94950] Re: [mg94919] Speeding-up FindInstance
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 31 Dec 2008 06:10:18 -0500 (EST)
- References: <200812301055.FAA13175@smc.vnet.net>
On 30 Dec 2008, at 19:55, Colletti, Bruce W. wrote:
> Re Mathematica 7.0.
>
> Let X be an n-by-p array of indexed x-variables, e.g., x[1,1],
> x[1,2], etc.
>
> I seek x-values in {-1, 0, 1} so that all column sums are zero and
> no column is the zero vector.
>
> The code below for a 5x3 problem runs forever. What is a faster way
> to get a solution? Thankx.
>
> Bruce
>
> {n,p} = {5,3};
>
> X=Array[x,{n,p}];
>
> Z = Flatten[X];
> FindInstance[And@@Join[Map[#==0&,Total@X],
> Map[#>0&,Map[Abs,Total@X,{2}]],
> Map[Abs@#<=1&,Z]],Z,Integers]
>
FindInstance is not the right tool to use for this sort of thing. It
uses mainly algebraic algorithms, which are not really suited to what
is essentially a combinatorial problem. This particular one is easiest
done by hand, but if you must use Mathematica then
Transpose[NestList[RotateRight, {1, 1, -1, -1, 0}, 2]]
{{1, 0, -1}, {1, 1, 0}, {-1, 1, 1}, {-1, -1, 1}, {0, -1, -1}}
will give you one solution.
Andrzej Kozlowski
- References:
- Speeding-up FindInstance
- From: "Colletti, Bruce W." <bcolletti@nvcc.edu>
- Speeding-up FindInstance