Re: Speeding-up FindInstance
- To: mathgroup at smc.vnet.net
- Subject: [mg94931] Re: [mg94919] Speeding-up FindInstance
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Wed, 31 Dec 2008 06:06:50 -0500 (EST)
- References: <200812301055.FAA13175@smc.vnet.net>
- Reply-to: drmajorbob at longhorns.com
Bruce,
The following function creates ONE column with p elements, of which k are
1, k are -1, and the rest are zero:
Clear[sorted]
sorted[p_][k_] /; 2 k <= p :=
Join[ConstantArray[-1, k], ConstantArray[0, p - 2 k],
ConstantArray[1, k]]
So here are all the length-10 columns made up of 0, 1, -1 that add to zero:
p = 10
sorted[p] /@ Range[p/2 // Floor]
10
{{-1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {-1, -1, 0, 0, 0, 0, 0, 0, 1,
1}, {-1, -1, -1, 0, 0, 0, 0, 1, 1, 1}, {-1, -1, -1, -1, 0, 0, 1, 1,
1, 1}, {-1, -1, -1, -1, -1, 1, 1, 1, 1, 1}}
Each such column can be permuted, as in
sorted[10][3] // Permutations // Length
4200
Adding permutations over all columns listed above, there are, for each
column, this many choices:
Length@Permutations@# & /@ (sorted[p] /@ Range[p/2 // Floor])
Total@%
{90, 1260, 4200, 3150, 252}
8952
With n columns, there would be 8952^n possible X matrices. For your small
example with {n,p} = {5,3}, the total is 50^3 or 125000.
It is surprising, with so many to choose from, that FindInstance couldn't
find ONE!!
Bobby
On Tue, 30 Dec 2008 04:55:22 -0600, Colletti, Bruce W.
<bcolletti at nvcc.edu> 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]
>
--
DrMajorBob at longhorns.com
- References:
- Speeding-up FindInstance
- From: "Colletti, Bruce W." <bcolletti@nvcc.edu>
- Speeding-up FindInstance