Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!57g2000hsv.googlegroups.com!not-for-mail
From:  "J.N." <joao.natali@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Logical Rules
Date: Thu, 13 Sep 2007 18:57:00 -0000
Organization: http://groups.google.com
Lines: 41
Message-ID: <1189709820.546157.183460@57g2000hsv.googlegroups.com>
References: <fcbpn6$eo0$1@fred.mathworks.com>
NNTP-Posting-Host: 128.238.52.146
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1189709820 12970 127.0.0.1 (13 Sep 2007 18:57:00 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 13 Sep 2007 18:57:00 +0000 (UTC)
In-Reply-To: <fcbpn6$eo0$1@fred.mathworks.com>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.6) Gecko/20070725 Firefox/2.0.0.6,gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: 57g2000hsv.googlegroups.com; posting-host=128.238.52.146;
Xref: news.mathworks.com comp.soft-sys.matlab:428424



On Sep 13, 12:49 pm, "Christopher Mouton" <mouton.no.s...@caltech.edu>
wrote:
> I am trying to see if Matlab has a toolbox for something
> like this, or where I might look for ideas on how to
> efficiently solve the following
>
> A{1}=[1,2]
> A{2}=[2,3]
> A{3}=[1,3]
> A{4}=[1,2,3,4]
>
> This reads:
>
> Position 1 can be 1 or 2
> Position 2 can be 2 or 3
> Position 3 can be 1 or 3
> Position 4 can be 1, 2, 3 or 4
>
> Given that each number can only be used once, we know that
> Position 4 must be 4.
>
> So my question is, how could I perform such logic in a
> general way? Any ideas where I should look?
>
> Thanks so much.

This is called an Assignment Problem:
http://en.wikipedia.org/wiki/Assignment_problem

You are essentially trying to assign a set of entities {1,2,...,n} to
a set of slots {A1,A2,...,An}, with constraints that state that a slot
Ai is able to accept only a subset of the entities.

One way to model this is to create a n x n logical variable L (with
slots as rows and entities as columns) such that L(i,j) = true iff
entity j can be assigned to slot Ai.

hth

J.N.