Message Boards Message Boards

Find all possible combinations subject to a condition?

GROUPS:

Hello! I am trying to find all possible ways to obtain p3[1] from the following list of constraints:

p2[1] = p1[1] + p1[2],

p2[2] = p1[3] + p1[4],

p2[3] = p1[5] + p1[6],

p2[4] = p1[7] + p1[8],

p3[1] = p2[1] + p2[2],

p3[2] = p2[3] + p2[4],

p4[1] = p3[1] + p3[2]

Let's say p3[1] can be written as p2[1]+p2[2], p1[1]+p1[2]+p2[2] and so on... Reduce seems to give me some of it, but I have to put in the quantifiers one by one myself. FrobeniusSolve is similar but only works for actual numbers. Is there a better/programmatic way to obtain all possible expressions equivalent to p3[1]? Thanks a lot!

POSTED BY: Stuart Griffith
Answer
6 months ago

It would be easier to help if you post what you have done.

POSTED BY: Frank Kampas
Answer
6 months ago

Welcome to Wolfram Community! Please make sure you know the rules: https://wolfr.am/READ-1ST Please post you code.

POSTED BY: Moderation Team
Answer
6 months ago

Ok let's use a simplified case as an example.

There are 4 pixels. We can measure them in three ways, bins of 1 (x[1], x[2], x[3], x[4]), bins of 2 (y[1], y[2]) and bins of 4 (z[1]). I want to find all possible way to get y[1]. Here is my code attempting to find the solutions:

Reduce[{y[1] == x[1] + x[2], y[2] == x[3] + x[4], 
  z[1] == x[1] + x[2] + x[3] + x[4]}, {y[1]}]

x[3] == -x[4] + y[2] && x[1] == -x[2] - y[2] + z[1] && 
 y[1] == -y[2] + z[1]

Reduce[{y[1] == x[1] + x[2], y[2] == x[3] + x[4], 
  z[1] == x[1] + x[2] + x[3] + x[4]}, {y[1], y[2]}]

x[1] == -x[2] - x[3] - x[4] + z[1] && y[1] == -x[3] - x[4] + z[1] && 
 y[2] == x[3] + x[4]

So we get these two:

y[1] == -y[2] + z[1]
y[1] == -x[3] - x[4] + z[1]

This seems like a stupid way to do so. Is there anyway to programmatically list all possible ways to get y[1] from other terms? In addition, I would like to extend to the case of higher terms, like 8 pixels having bins of 1,2,4,8, and so on. Can I write a for loop to write those equations?

Thanks in advance!

POSTED BY: Stuart Griffith
Answer
6 months ago

Stuart,

I think you can do this as follows setting solveVariable to p3[1] --> the variable you want to solve for.

eqns = {p2[1] == p1[1] + p1[2], p2[2] == p1[3] + p1[4]; 
  p2[3] == p1[5] + p1[6], p2[4] == p1[7] + p1[8], 
  p3[1] == p2[1] + p2[2], p3[2] == p2[3] + p2[4], 
  p4[1] == p3[1] + p3[2]}
solveVariable = p3[1]

The code below grabs all of the variables in the equations and sets them equal to vars. (this will only run in Version 10 or 11, otherwise do a DeleteCases to remove the solveVariable)

vars = DeleteDuplicates[Cases[eqns, _[_], Infinity]] /. 
  solveVariable -> Nothing

{p2[1], p1[1], p1[2], p2[3], p1[5], p1[6], p2[4], p1[7], p1[8], p2[2], p3[2], p4[1]}

Now create all possible sets of variables (excluding the solveVariable) and then add the solveVariable to every set. Only create sets up to the number of equations - 1 because you can't have more variables than you have equations.

solveVarsSets = 
 Map[Prepend[solveVariable], Subsets[vars, Length[eqns] - 1]]

Run the Reduce to get your equations and delete the empty solutions and all duplicates. Only keep the equations in the form of the solveVariable == ....

answers = 
 DeleteDuplicates[
  DeleteCases[
   Map[Cases[Reduce[eqns, #], Equal[solveVariable, _]] & , 
    solveVarsSets], {}]]

to get all possible equations that you want:

{{p3[1] == -p3[2] + p4[1]}, {p3[1] == -p2[3] - p2[4] + p4[1]}, {p3[ 1] == p2[1] + p2[2]}, {p3[1] == p1[1] + p1[2] + p2[2]}, {p3[1] == -p1[5] - p1[6] - p2[4] + p4[1]}, {p3[1] == -p1[7] - p1[8] - p2[3] + p4[1]}, {p3[ 1] == -p1[5] - p1[6] - p1[7] - p1[8] + p4[1]}}

I hope this helps

Regards

Neil

POSTED BY: Neil Singer
Answer
6 months ago

Stuart,

Just curious -- did this work? did it do what you wanted?

Regards

POSTED BY: Neil Singer
Answer
6 months ago

Hi Neil,

Thanks a lot for your kind help! It worked perfectly! I have been investigating two problems - one is about how to extend the program such that it can find all possible combinations to build, let's say, p1[2]+p1[3]. another is about how to extend such method to longer pixels - the program dies at chip length of 2^4 already...

But anyway thanks again for your great great help!

Stuart

POSTED BY: Stuart Griffith
Answer
6 months ago

Stuart,

I suspected that the scaling would be a problem with my brute force approach. The number of subsets grows rapidly. I was not sure if you planned on extending this to larger problems. I believe there may be a more intelligent way to get a list of viable subsets of variables. I'll think about that...

Regards

POSTED BY: Neil Singer
Answer
6 months ago

Group Abstract Group Abstract