|
I have a set of dates [d1, d2, d3, d4,...,dn]
I have a set of constraints [(d1<=d4),(d2
I 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 |
| |
|
| 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. |
|
|
 |
|
Without algebra a constraint solver would operate like this:
1. generate all permutations
2. 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. |
|
|
|
|
|
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 |
| |
|
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" |
|
|
|
|
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 |
| |
|
| 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 |
|
|
|
|
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 permutations
A simplified example is 3 dates:
[d1, d2, d3]
I want all orderings based on (<)
constrained by
so 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 d3
d1[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
[edit] 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 |
| |
|
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 |
|
|
|
|
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 |
| |
|
Well, any natural number n can
expressed as n!/1!(n-1)!
(thus a factorial divided by a product
of factorials)
|
вакансия "Программист Психологической службы"
-але! у нас ошибко! не работает бля-бля-бля
-вы хотите об этом поговорить? |
|
|
|
Nonius
|
| Founding MemberNonius Unbound |
| Total Posts: 11347 |
| Joined: Mar 2004 |
| |
|
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 |
|
|
|
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’. |
|
|
|
|
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 12
2) the 1's digit must only be even numbers
3) the 10's digit must be less than 7
4) the 100's digit must be greater than 4
The 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 numbers
the 10's digit array was initiliazed with 0-6
the 100's digit array was initialized with 5-9
Then, 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. |
|
|
|
