Group Abstract Group Abstract

Message Boards Message Boards

0
|
5.7K Views
|
7 Replies
|
4 Total Likes
View groups...
Share
Share this post:

Find all possible combinations subject to a condition?

Posted 9 years ago

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

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

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

Stuart,

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

Regards

POSTED BY: Neil Singer

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
POSTED BY: Stuart Griffith

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

POSTED BY: EDITORIAL BOARD

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

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard