Forums > Basics > Math Question - Filtering Permutations

 Page 1 of 1
Display using:
 Steve Castle Total Posts: 237 Joined: Sep 2010
 Posted: 2012-07-02 17:45 I have a set of dates [d1, d2, d3, d4,...,dn]I have a set of constraints [(d1<=d4),(d2I can model my constraints in an nxn matrix, probabily using more than one for different logical operators. This becomes a kind of mask or filter for the permutations.I want all permutations of the dates subject to the constraints.Let's say I have 10 dates, huersitically I know the number of valid permutations will be much less than 10!, but it will be enough that I'd rather generate this automatically to ensure all cases are hit.Is there some kind of algebra which will get me there? I did not take enough algebra in school for this. If I have the matrix of permutations P, it's something like nx(n!), and I would like to avoid computing all the permutations and then filtering.I can brute force, but there's so much symmetry I feel like there really should be a better solution.I've looked into group theory and it seems like it would be somewhere in there if anywhere, but I can't seem to find anything to do other than brute force it. Maybe that's the only way. in the words of one such quant ‘were on the whole either less quanted or not quanted at all’.
 fr Total Posts: 12 Joined: Nov 2006
 Posted: 2012-07-02 18:09 Probably the most concise way of writing code to do what you want to do would be to use a constraint logic programming (CLP) language. Alternatively, I'd try to find a CLP library for whatever programming language you normally use.
 Praetorian Total Posts: 156 Joined: Apr 2009
 Posted: 2012-07-02 18:10 Without algebra a constraint solver would operate like this:1. generate all permutations2. for all constraints: cycle through active permutations and deactivate each permutation that is invalid under the given constraint.If your constraints are restrictive, each pass will remove permutations and you will end up with the set of permuations that satisfy all given constraints.
 silverside Total Posts: 1231 Joined: Jun 2004
 Posted: 2012-07-02 18:18 if you're interested in algorithms/number theory/computational complexity, the Project Euler series of problems is quite interesting; problem 24 seems vaguely related to what you are trying to do and it may give you some ideas.
 rod Total Posts: 259 Joined: Nov 2006
 Posted: 2012-07-02 21:30 The problem you propose is a generalization of sorting. When one sorts a given list, what one does is to use the predicate Have you ever used Haskell? If so, you can create a list of permutations, then you create a predicate with the constraints that you want, and then you use higher-order function filter to filter out the permutations that satisfy the constraints. "Jeder soll nach seiner Fasson selig werden"
 Steve Castle Total Posts: 237 Joined: Sep 2010
 Posted: 2012-07-03 04:39 Thanks everyone. Will try all the suggestions. I'm familiar with simplex methods from OR, and CLP seems to be a generalization of that. Thanks for pointing me in the right direction in the words of one such quant ‘were on the whole either less quanted or not quanted at all’.
 Nonius Founding MemberNonius Unbound Total Posts: 11347 Joined: Mar 2004
 Posted: 2012-07-23 23:45 steve, not sure to understand the Q. id gladly put some time into it, with a little more clarity of whats to be accomplished. An a=a etc moment....http://www.dinbali.com/?page_id=74
 Steve Castle Total Posts: 237 Joined: Sep 2010
 Posted: 2012-07-24 22:35 The general problem is k "key" dates (think option expiration, coupon, holiday, trade date) which can be arranged on a specific timeline based on the 2 logical operators (<, =).so one example time line is:If I permute all possible operators and dates to get all (mathematical) timelines, a lot of them are nonsense.for example. So adding a constraint filters the permutationsA simplified example is 3 dates:[d1, d2, d3]I want all orderings based on (<)constrained byso by first permuting the dates, I get a list of 3! orderings:*[d1, d2, d3]*[d1, d3, d2][d2, d1, d3][d2, d3, d1]*[d3, d1, d2][d3, d2, d1]The ones w/ * are valid per the constraint.the above is easy enough to brute force.I know how to count the resulting number of 'valid' permutations, but it seems like there is no other way other than brute force to actually get the filtered list.back to k "key" dates, for each operator, I can construct a (kxk) matrix for the constraints, where 1 indicates when the constraint applies, and 0 when it doesn't. using the example with [ ]d1 d2 d3d1[0, 1, 1]d2[0, 0, 1]d3[1, 1, 0]This reads:Something about it just feels like i should be able to directly map to the filtered list of valid permutations. I don't understand if I can't figure it out because I lack the math or because it just cannot be done and brute force / CLP is the way to go. My limited understanding of group theory is that it kind of dealt with this kind of situation, where I'm looking for all possible mapping of the set of dates D onto itself, excluding some set of the mappings which are a specific mapping of D onto itself. But here's where I'm lost, I don't even know if I just described it correctly. I could just be displaying an extreme lack of understanding, all the group theory i know i learned online I'm having issues with less than signs. I'll re-write in TeX later. [/edit][edit2] TeX eqns for legibility [/edit2] in the words of one such quant ‘were on the whole either less quanted or not quanted at all’.
 Nonius Founding MemberNonius Unbound Total Posts: 11347 Joined: Mar 2004
 Posted: 2012-07-25 08:41 the set of constraints is a partially ordered set whose connected components are totally ordered. the set of permutations respecting that order is in on to one correspondence with the group of permutations that leaves that partially ordered set invariant and that restricted to it simply, at most, permutes connected components of equal size.group connected compnents into sets of equal size. for each of those sets, consider the group of permutations for those sets. then take the direct product of thos groups. that is naturally a normal subgroup of the group of permutations of the total set of permutations. your group will be the total group divides by this normal subgroup. your answer will be a factorial divided by a product of factorials. An a=a etc moment....http://www.dinbali.com/?page_id=74
 Steve Castle Total Posts: 237 Joined: Sep 2010
 Posted: 2012-07-31 15:56 Thanks Nonius.I need to work through what you've said, but I get the idea. One question though:your answer will be a factorial divided by a product of factorials.Do you mean the mapping I'm looking for will be this, or is this the # of valid mappings only? I know the count of the mappings takes the same form (factorial / product of factorials). I'm sure there's symmetry there, but since I'm a more on the ignorant side, I wanted to clarify.Thanks! in the words of one such quant ‘were on the whole either less quanted or not quanted at all’.
 pj Total Posts: 2726 Joined: Jun 2004
 Posted: 2012-07-31 16:09 Well, any natural number n canexpressed as n!/1!(n-1)!(thus a factorial divided by a productof factorials) вакансия "Программист Психологической службы" -але! у нас ошибко! не работает бля-бля-бля -вы хотите об этом поговорить?
 Nonius Founding MemberNonius Unbound Total Posts: 11347 Joined: Mar 2004
 Posted: 2012-07-31 23:29 of course pj, of course.anyway, steve, my approach is still not right because you could have a less than b, c less than d, but c between a and b. An a=a etc moment....http://www.dinbali.com/?page_id=74
 Steve Castle Total Posts: 237 Joined: Sep 2010
 Posted: 2012-08-05 06:10 yah, but your approach isn't wrong either.There's something that I'm not taking into account. taking the same example, the components are all connected as a graph. And that's what the constraint matrix really is, it's a graph, not a mapping. I didn't realize that. Now I'm sure graphs are a kind of mapping, but it's a different problem than the one I originally thought it was. I was thinking the constraint matrix was a "first order" mapping of D->D, but it's not, it's a graph, which i dont know about really. I think it just means a compound mapping, but it's no longer one-to-one.What's interesting is that there's a 2nd interpretation which groups the vertices on the graph. 2 groups are total orderings with equal size, and one is a total ordering with a different size.I need to spend more time on it. I am starting to think the single constraint example doesn't show the interaction between constraints, which is where the real interesting part of the problem is. in the words of one such quant ‘were on the whole either less quanted or not quanted at all’.
 meteoraln Total Posts: 31 Joined: May 2012
 Posted: 2012-08-24 04:59 Don't know if you're still working on this problem, but I had to tackle a similar problem. I'll simplify the problem here, but hopefully, it'll give you some ideas.Not the exact problem as what I worked on but as a simplified version:I had to find all 3 digit numbers that satisfy a particular set of conditions.1) the sum of all 3 digits must be less than 122) the 1's digit must only be even numbers3) the 10's digit must be less than 74) the 100's digit must be greater than 4The idea was to do this without testing all 1000 possible numbers. To do this, I created a Digit class, which would contain an array initialized with a list of valid values for that particular digit.The 1's digit array was initalized with only even numbersthe 10's digit array was initiliazed with 0-6the 100's digit array was initialized with 5-9Then, I incremented each digit and applied the sum less than 12 rule. If the sum was more than 12, I could increment the higher order digit rather than wastefully increment the lower order digit. This allowed me to eliminate the testing of most of the useless (incorrect) combinations.
 Page 1 of 1