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

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