MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Generating systems of constraints

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

  • Prev by Date: Re: GraphPlot display anomaly
  • Next by Date: Merry Christmas! Can somebody help me with this equation? Thank you!
  • Previous by thread: Re: latex label in mathematica graphics
  • Next by thread: Re: Generating systems of constraints