Need for algorithmist
Moderators: Balthagor, Legend, Moderators
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Need for algorithmist
Recently I started to solve tasks in bioinformatics in my spare time (I've done 32 and continue now). However another one put me at a stand (or very close to it).
Here is link: http://rosalind.info/problems/rear/ Apropos, I highly recommend the RosaLind site.
I could not figure out how to link the number of reversals with the permutation. So, because I work with RDBMS, I try to make a total calculation: store all possible reversals of initial permutation (0123456789 to 45 pieces), than reversals of reversals, etc. without collisions of current and previous steps (total 3,620,880 permutations). The rest (replacing the original numbers and select results from the table) as simple as ABC.
However, each step is calculated more and more slowly. The 5th iteration has exceeded 5 minutes (I think preliminary calculation and high-performance servers isn't the fair game) although I was going to do 9! I use MS SQL Express, then try it for Visual Basic with similar results. Now I run back over 20 years to assembler and adapt the algorithm for it. Is there some ideas of help to calculate this task?
Here is link: http://rosalind.info/problems/rear/ Apropos, I highly recommend the RosaLind site.
I could not figure out how to link the number of reversals with the permutation. So, because I work with RDBMS, I try to make a total calculation: store all possible reversals of initial permutation (0123456789 to 45 pieces), than reversals of reversals, etc. without collisions of current and previous steps (total 3,620,880 permutations). The rest (replacing the original numbers and select results from the table) as simple as ABC.
However, each step is calculated more and more slowly. The 5th iteration has exceeded 5 minutes (I think preliminary calculation and high-performance servers isn't the fair game) although I was going to do 9! I use MS SQL Express, then try it for Visual Basic with similar results. Now I run back over 20 years to assembler and adapt the algorithm for it. Is there some ideas of help to calculate this task?
- fool
- General
- Posts: 1364
- Joined: Mar 28 2009
Re: Need for algorithmist
Isn't that rather too specialised a question to ask in a forum this small?
(also since you got that far I'm guessing you understand: what exactly is a reversal? I don't understand how it can be, as they say, an inverse of some interval of a permutation since the first problem involves the identity permutation which obviously will only transform to itself no matter how many inverses you apply)
(also since you got that far I'm guessing you understand: what exactly is a reversal? I don't understand how it can be, as they say, an inverse of some interval of a permutation since the first problem involves the identity permutation which obviously will only transform to itself no matter how many inverses you apply)
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Re: Need for algorithmist
I don't want to shout at the top of my throat. I'd better whisper it under my breath... There is should be some programmers.fool wrote:Isn't that rather too specialised a question to ask in a forum this small?
It is about a minimum of permutations. Already met permutations excluded, e.g. 0123456789 1023456789 (counted) 0123456789 (excluded).fool wrote:(also since you got that far I'm guessing you understand: what exactly is a reversal? I don't understand how it can be, as they say, an inverse of some interval of a permutation since the first problem involves the identity permutation which obviously will only transform to itself no matter how many inverses you apply)
Note: I don't want to mess around sparse arrays so I convert every possible permutation to number (0...3'628'799). But they need to convert back for reversal!
- fool
- General
- Posts: 1364
- Joined: Mar 28 2009
Re: Need for algorithmist
Yeah, unfortunately I'm still totally lost.It is about a minimum of permutations. Already met permutations excluded, e.g. 0123456789 1023456789 (counted) 0123456789 (excluded).
I do maths, I think we use different terminology. That said, if the problem is anything difficult I'm still a year or two too early to help anyway. I was thinking that to get from π to σ, it would be easier to consider going from σπ^-1 to 1 (identity permutation), writing σπ^-1 as a product of disjoint cycles and then (somehow) finding the minimum number of transpositions that make it up. σπ^-1 will have the same minimum number of transpositions as (σπ^-1)^-1, which by definition is the function we need to apply to get from σπ^-1 to 1. The trouble is, I: i) am not sure how to do this last step, and ii) am still not sure what a reversal is, and so I'm not sure that that is even what we're trying to find. If a reversal isn't what I've half-guessed it is, all these steps were pretty much a waste of time.
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Re: Need for algorithmist
One moment please, reversal and transposition are very different therms. I have no idea how to express one over another (or, rather, number of).fool wrote:Yeah, unfortunately I'm still totally lost.
I do maths, I think we use different terminology. That said, if the problem is anything difficult I'm still a year or two too early to help anyway. I was thinking that to get from π to σ, it would be easier to consider going from σπ^-1 to 1 (identity permutation), writing σπ^-1 as a product of disjoint cycles and then (somehow) finding the minimum number of transpositions that make it up. σπ^-1 will have the same minimum number of transpositions as (σπ^-1)^-1, which by definition is the function we need to apply to get from σπ^-1 to 1. The trouble is, I: i) am not sure how to do this last step, and ii) am still not sure what a reversal is, and so I'm not sure that that is even what we're trying to find. If a reversal isn't what I've half-guessed it is, all these steps were pretty much a waste of time.
- fool
- General
- Posts: 1364
- Joined: Mar 28 2009
Re: Need for algorithmist
I suspected as much, but I can't find the definition for reversal anywhere except on your link and I don't quite understand what it means by "inverting some interval of the permutation". If it means an inverse as I understand it (g is an inverse of f if applying g to the codomain of f returns the domain of f) there's no way the first sample problem could ever be solved. So I'm rather confused at to what they mean by a reversal here, and I suspect as often happens in these sorts of situations they're using different terminology than what I'm used to. That they meant a transposition was only a guess: from your reaction though, totally wrong.
Do you know anywhere I can find another (hopefully fuller) definition of a reversal?
Do you know anywhere I can find another (hopefully fuller) definition of a reversal?
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
- fool
- General
- Posts: 1364
- Joined: Mar 28 2009
Re: Need for algorithmist
Ok, I looked on the "tree" for previous problems, and it seems you're not thinking of permutations as functions in this case. So obviously by "inverse" they mean something else, and that's where the confusion came from.I think I cleared it up now though: they mean swapping round some of the numbers in the permutation, correct? So for example, taking (1,2,3,4,5) you could perform a reversal to get (5,4,3,2,1) if you take the whole permutation as the interval, or (1,2,3,5,4) if you take just the last two values.
It seems to me like you'll need to find a shortcut. The problem you've got is you're doing it exhaustively; in practice, there's probably some way of finding a solution without trying every permutation possible. I might have a think about this later; rather busy now and to be honest I'm not a fan of these sorts of problems anyway. But usually methods like the one you're trying take ridiculously huge amounts of processing power as you get something harder than a very simple example. It gets to the stage where the 5th iteration takes 5 minutes and the 6th iteration takes a couple of centuries...
It seems to me like you'll need to find a shortcut. The problem you've got is you're doing it exhaustively; in practice, there's probably some way of finding a solution without trying every permutation possible. I might have a think about this later; rather busy now and to be honest I'm not a fan of these sorts of problems anyway. But usually methods like the one you're trying take ridiculously huge amounts of processing power as you get something harder than a very simple example. It gets to the stage where the 5th iteration takes 5 minutes and the 6th iteration takes a couple of centuries...
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Re: Need for algorithmist
Had a shortcut found, I would use it.fool wrote:It seems to me like you'll need to find a shortcut. The problem you've got is you're doing it exhaustively
P.S. So far I think about optimize of translation 10-figure string to permutation Id. I don't like 9 substring shift or 36 comparisons... The reverse action has already been done: a some preliminary calculation and...
Num2Str PROC
; In: EAX - number
; Out: EAX - Address of string
; the same as "imul eax, 10"
shl eax, 1
lea eax, [eax + eax * 4]
add eax, [N2S]
ret
Num2Str ENDP
- fool
- General
- Posts: 1364
- Joined: Mar 28 2009
Re: Need for algorithmist
Yeah, so I'm no good at the actual programming. But I might take a look at this later and if I do find a shortcut I'll let you know about it (although I'd be unable to tell you how to code it).
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
Hold out baits to entice the enemy. Feign disorder, and crush him."
Sun Tzu, The Art of War
-
- General
- Posts: 1168
- Joined: Jul 14 2004
- Human: Yes
- Location: Space Coast, FL
Re: Need for algorithmist
WOW! That's a very interesting site... I'll take a closer look whenn I'm off work... this sure beats angry birds
Right out of the bat (as a DBA for RDBMS / MS-SQL sppecificaly) I can tell you that TSQL is not the right tool for this ... This kindof problems calll for language that allow the use of recursive algorithms ... (Sure, TSQL can be used as you probe it but there better languages out ther for this) ...
Thanks for sharing this Lea
Right out of the bat (as a DBA for RDBMS / MS-SQL sppecificaly) I can tell you that TSQL is not the right tool for this ... This kindof problems calll for language that allow the use of recursive algorithms ... (Sure, TSQL can be used as you probe it but there better languages out ther for this) ...
Thanks for sharing this Lea
Violence is the last refuge of the incompetent.
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Re: Need for algorithmist
I solve all tasks by T-SQL, conceptually. Excluding that. Also I have done 1st task by PL/SQL but later need to put a long strings as result. Because I didn't want to bother with files I take MS...Draken wrote:WOW! That's a very interesting site... I'll take a closer look whenn I'm off work... this sure beats angry birds
Right out of the bat (as a DBA for RDBMS / MS-SQL sppecificaly) I can tell you that TSQL is not the right tool for this ... This kindof problems calll for language that allow the use of recursive algorithms ... (Sure, TSQL can be used as you probe it but there better languages out ther for this) ...
Thanks for sharing this Lea
My profile
-
- General
- Posts: 1168
- Joined: Jul 14 2004
- Human: Yes
- Location: Space Coast, FL
Re: Need for algorithmist
well, you got me hooked ... I created a profile already...
And decided to go back to my origins: PASCAL ! Just for fun... I'll download it as soon as I get home... I think I will skip the introductory pproblems with phyton ...
I work with TSQL every day so, I don't want to see it at home:D and I have great memories from Pascal... Leraning about Graphs way back in mid 80's.. (BTW, I'm getting involved with Graph Databases (neo4j) so, this can get interesting...)
And decided to go back to my origins: PASCAL ! Just for fun... I'll download it as soon as I get home... I think I will skip the introductory pproblems with phyton ...
I work with TSQL every day so, I don't want to see it at home:D and I have great memories from Pascal... Leraning about Graphs way back in mid 80's.. (BTW, I'm getting involved with Graph Databases (neo4j) so, this can get interesting...)
Violence is the last refuge of the incompetent.
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
-
- General
- Posts: 1168
- Joined: Jul 14 2004
- Human: Yes
- Location: Space Coast, FL
Re: Need for algorithmist
Violence is the last refuge of the incompetent.
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
- Lea
- Brigadier Gen.
- Posts: 506
- Joined: Aug 31 2009
- Human: Yes
- Location: Moscow
- Contact:
Re: Need for algorithmist
Burnout?Draken wrote:well, you got me hooked ... I created a profile already...
So, during the New Year holidays, I went back to the task. It was a lot of reading about the new features of processors. I've given this a lot of thought (we say that the brains were boiling). MMX, SSE, SSE2-3-4, SSSE-3, AVX... for 1 week... OMG! I got my knuckles rapped for acronyms CUDA and OpenCL (was tempted, because calculations perfectly parallelize to 45 threads). Multithreading in assembler... Oh no, it's too much for me now, even without programming GPU.
The chosen path led to success. Most of the algorithm has been implemented with the good old i386 assembler. For long time I hold that the right data structure is a 90% of performance. SSE/AVX operators only used to find the next byte per 3'620'800 (vpcmpestri with bound test given a gain of 3.5 times compared to repnz scasb) and to create the reversal (vpshufb worked perfectly). Overall it's not very much. Time of each step calculated by using of operator RDTSC and print to the console.
The first successful launch took 12.5 seconds. The result file was embedded in the library of .CLR function. Small SQL code parses input strings and converts them into numbers then call the function. The task is complete.
-
- General
- Posts: 1168
- Joined: Jul 14 2004
- Human: Yes
- Location: Space Coast, FL
Re: Need for algorithmist
Nope... Not burned out... Just a little side tracked with the holydays....I'll get back to it
Been playing update 3
Been playing update 3
Violence is the last refuge of the incompetent.
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire
Isaac Asimov, Salvor Hardin in "Foundation"
-
Si vis pacem, para bellum
-
It is hard to free fools from the chains they revere.
Voltaire