Re: Generating systems of constraints

*To*: mathgroup at smc.vnet.net*Subject*: [mg72390] Re: Generating systems of constraints*From*: danl at wolfram.com*Date*: Sun, 24 Dec 2006 03:40:17 -0500 (EST)*References*: <emdp92$k3f$1@smc.vnet.net>

Alec Resnick wrote: > Good day! I was hoping someone might be able to point me in the > right direction with a problem I ran into. I'm trying to solve an > arbitrarily large system of linear, Diophantine equations whose > solutions are subject to two constraints > 1) All the variables are distinct; i.e., none of the variables are > equal to one another. > 2) All of the variables are bounded by 1 <= x <= # of variables. > > So in essence, I have a system of equations with N variables that I > would like to generate solutions for by assigning {1,2...,N} to each > variable. > > Now, I know that I can use Reduce to solve this system; however, I > don't know how to generate constraints like this for a given N, and > I'd rather not type them all out. Does anyone have any suggestions? > I don't need to do this for very many systems, but more than four, so > I don't want to have to do too much of it manually. > > Thanks! > > Gratefully, > a. There may be various ways to do this. What I often do is create n^2 variables, using n for each original variable. Index them x[i,j] where {i,j} run from 1 to n, all take on values either 0 or 1, and x[i,j]=1 means the ith original variable is equal to j. The constraints then become Sum[x[i,j],{j,1,n}]==1 for each i, and Sum[x[i,j],{i,1,n}==1 for each j. These together with the constraint that each take on integer values (that is, either 0 or 1) means each original variable takes a distinct value in {1,...,n}. If you have more than 20-30 variables, chances are this will become intractable for the problem at hand. If that describes you problems then I'll need to give this more thought. Daniel Lichtblau Wolfram Research