Need for algorithmist

Off Topic Comments Area

Moderators: Balthagor, Legend, Moderators

User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Need for algorithmist

Post by Lea »

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?
User avatar
fool
General
Posts: 1364
Joined: Mar 28 2009

Re: Need for algorithmist

Post by fool »

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)
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."

Sun Tzu, The Art of War
User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Re: Need for algorithmist

Post by Lea »

fool wrote:Isn't that rather too specialised a question to ask in a forum this small?
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:(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)
It is about a minimum of permutations. Already met permutations excluded, e.g. 0123456789 --> 1023456789 (counted) --> 0123456789 (excluded).

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!
User avatar
fool
General
Posts: 1364
Joined: Mar 28 2009

Re: Need for algorithmist

Post by fool »

It is about a minimum of permutations. Already met permutations excluded, e.g. 0123456789 --> 1023456789 (counted) --> 0123456789 (excluded).
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.
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."

Sun Tzu, The Art of War
User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Re: Need for algorithmist

Post by Lea »

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.
One moment please, reversal and transposition are very different therms. I have no idea how to express one over another (or, rather, number of).
User avatar
fool
General
Posts: 1364
Joined: Mar 28 2009

Re: Need for algorithmist

Post by fool »

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?
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."

Sun Tzu, The Art of War
User avatar
fool
General
Posts: 1364
Joined: Mar 28 2009

Re: Need for algorithmist

Post by fool »

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...
"All warfare is based on deception...
Hold out baits to entice the enemy. Feign disorder, and crush him."

Sun Tzu, The Art of War
User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Re: Need for algorithmist

Post by Lea »

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
Had a shortcut found, I would use it.

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
User avatar
fool
General
Posts: 1364
Joined: Mar 28 2009

Re: Need for algorithmist

Post by fool »

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
Draken
General
Posts: 1168
Joined: Jul 14 2004
Human: Yes
Location: Space Coast, FL

Re: Need for algorithmist

Post by Draken »

WOW! That's a very interesting site... I'll take a closer look whenn I'm off work... this sure beats angry birds !!! :D


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
User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Re: Need for algorithmist

Post by Lea »

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 !!! :D


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
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...
My profile
Draken
General
Posts: 1168
Joined: Jul 14 2004
Human: Yes
Location: Space Coast, FL

Re: Need for algorithmist

Post by Draken »

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...)
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
Draken
General
Posts: 1168
Joined: Jul 14 2004
Human: Yes
Location: Space Coast, FL

Re: Need for algorithmist

Post by Draken »

My profile

Decided to go with python... Very interesting language...
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
User avatar
Lea
Brigadier Gen.
Posts: 506
Joined: Aug 31 2009
Human: Yes
Location: Moscow
Contact:

Re: Need for algorithmist

Post by Lea »

Draken wrote:well, you got me hooked ... I created a profile already...
Burnout?

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.
Draken
General
Posts: 1168
Joined: Jul 14 2004
Human: Yes
Location: Space Coast, FL

Re: Need for algorithmist

Post by Draken »

Nope... Not burned out... Just a little side tracked with the holydays....I'll get back to it

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
Post Reply

Return to “Off Topic Comments”