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