MATLAB Central Newsreader - Logical Rules

Logical Rules

Christopher Mouton — Thu, 13 Sep 2007 16:49:42 -0400

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.

Re: Logical Rules

dpb — Thu, 13 Sep 2007 17:25:21 -0400

Christopher Mouton 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?

unique(), maybe?

But, strictly speaking, by my reading your example is inconsistent to
start with -- if each value can be used only once, then A(2) would have
to be [3] and then A(3) would have to be []?

Think need more precise definition of the problem and the expected
solution...

--

Re: Logical Rules

Kelly Kearney — Thu, 13 Sep 2007 17:47:43 -0400

"Christopher Mouton" <mouton.no.spam@caltech.edu> wrote in
message <fcbpn6$eo0$1@fred.mathworks.com>...
> 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.

The most straightforward way would be to just form all
combinations possible, then throw out any that don't meet
the uniqueness criteria.

A{1}=[1,2];
A{2}=[2,3];
A{3}=[1,3];
A{4}=[1,2,3,4];

combos = [];
for a = A{1}
    for b = A{2}
        for c = A{3}
            for d = A{4}
                temp = [a b c d];
                if length(unique(temp)) == 4
                    combos = [combos;temp];
                end
            end
        end
    end
end

-Kelly

Re: Logical Rules

Christopher Mouton — Thu, 13 Sep 2007 17:57:21 -0400

I would expect the solution to be

A{1}=[1,2]
A{2}=[2,3]
A{3}=[1,3]
A{4}=[4]

Re: Logical Rules

Christopher Mouton — Thu, 13 Sep 2007 17:58:20 -0400

This would definitely work for this example.

But now I would like to be able to find much larger sets.
In particular A{1...256}, so it will require something
smart.

Re: Logical Rules

dpb — Thu, 13 Sep 2007 18:00:51 -0400

Christopher Mouton wrote:
> I would expect the solution to be
>
> A{1}=[1,2]
> A{2}=[2,3]
> A{3}=[1,3]
> A{4}=[4]

Oh? Why? Then "used only once" means something different than used
only once. The answer to that would perhaps lead the "something clever"
solution...

Maybe I'm just dense today (some say every day :) ), but I don't yet see
the general rule...

--

Re: Logical Rules

Christopher Mouton — Thu, 13 Sep 2007 18:07:46 -0400

I hope I am not being stupid. Here are the two possible
solutions:

A{1}=[1]
A{2}=[2]
A{3}=[3]
A{4}=[4]

A{1}=[2]
A{2}=[3]
A{3}=[1]
A{4}=[4]

Thanks.

Re: Logical Rules

dpb — Thu, 13 Sep 2007 18:48:06 -0400

Christopher Mouton wrote:
> I hope I am not being stupid. Here are the two possible
> solutions:
...

Oh, oops! I got my eyes crossed somehow... :(

But, sorry, I've no cleverer ideas. Not my area, but would some of the
genetics-related pattern matching have any bearing here for tricks?

--

Re: Logical Rules

"J.N. — Thu, 13 Sep 2007 18:57:00 -0400

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.

Re: Logical Rules

Randy Poe — Thu, 13 Sep 2007 20:03:30 -0400

On Sep 13, 2:57 pm, "J.N." <joao.nat...@gmail.com> wrote:
> 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
>

Hmm. There are some problems on that page, mainly the
misuse of the term "Linear Program" which normally refers
to problems in which the variables can be any (positive)
real, not restricted to integers.

> 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.

Yes, the Wiki page describes the setup as an LP with these
n^2 variables. At n=256, that's not an unwieldy problem, but
you can see that it doesn't take much for such a problem to
get too large to fit in memory.

If you relax the requirement that the L(i,j) be integers, then
you do actually have a standard linear program and you can
use fast LP solving algorithms to solve it (this is called an
"LP relaxation"). The Optimization Toolbox includes one called
LINPROG.

Then you have to decide what to do with fractional values,
but usually some rounding scheme works and often
gives you a pretty good solution, though only in
special cases is that solution guaranteed optimal.

- Randy