Thread Subject: Logical Rules

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.

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

--

"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

I would expect the solution to be

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

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.

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

--

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.

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?

--

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.

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