5uperb0y's blog

二十歲的松浦夏子是個言出必行的女孩，她有著一旦下定決心便不肯輕言放棄的頑固個性，七歲那年，她受夠了菠菜，她的筷子再也不曾沾過這種蔬菜；等到十五歲時，聽聞他人評論紅色不適合她，夏子便立誓不再穿紅色系的衣服，任誰來勸說也無法動搖她的決心。

（三島由紀夫（1951），夏子的冒險。）

給定一對數列，計算兩者的最小反轉距離，並依序列出反轉數列的步驟。

A reversal of a permutation can be encoded by the two indices at the endpoints of the interval that it inverts; for example, the reversal that transforms (4,1,2,6,3,5) into (4,1,3,6,2,5) is encoded by [3,5] .
A collection of reversals sorts π into γ if the collection contains drev(π,γ) reversals, which when successively applied to π yield γ .

Given: Two permutations π and γ , each of length 10.
Return: The reversal distance drev(π,γ) , followed by a collection of reversals sorting π into γ . If multiple collections of such reversals exist, you may return any one.

(https://rosalind.info/problems/sort/)

給定 5 對長度為 10 的數列，計算將各對數列互相轉換所需的最少反轉次數。

A reversal of a permutation creates a new permutation by inverting some interval of the permutation; (5,2,3,1,4) , (5,3,4,1,2) , and (4,1,2,3,5) are all reversals of (5,3,2,1,4) . The reversal distance between two permutations π and σ , written drev(π,σ) , is the minimum number of reversals required to transform π into σ (this assumes that π and σ have the same length).

Given: A collection of at most 5 pairs of permutations, all of which have length 10.

Return: The reversal distance between each permutation pair.

(https://rosalind.info/problems/rear/)

給一正整數列，求其最長的遞增與遞減子數列。例如數列 5, 1, 4, 2, 3 的最長遞增數列為 1, 2, 3，最長遞減數列則為 5, 4, 3。

Given: A positive integer n≤10000 followed by a permutation π of length n.

Return: A longest increasing subsequence of π , followed by a longest decreasing subsequence of π.

(https://rosalind.info/problems/lgis/)

給定一 FASTA 檔案，內含數條由 A、C、G、T 組成的字串，求這些字串共享的最長子字串。

A common substring of a collection of strings is a substring of every member of the collection. We say that a common substring is a longest common substring if there does not exist a longer common substring. For example, “CG” is a common substring of “ACGTACGT” and “AACCGTATA”, but it is not as long as possible; in this case, “CGTA” is a longest common substring of “ACGTACGT” and “AACCGTATA”.
Note that the longest common substring is not necessarily unique; for a simple example, “AA” and “CC” are both longest common substrings of “AACC” and “CCAA”.

Given: A collection of k (k≤100) DNA strings of length at most 1 kbp each in FASTA format.

Return: A longest common substring of the collection. (If multiple solutions exist, you may return any single solution.)

(https://rosalind.info/problems/lcsm/)

Problem

給定字串 s 與 t，其中 t 的長度小於等於 s，求 s 與 t 一致之子序列的起始位置。

Given: Two DNA strings s and t (each of length at most 1 kbp).

Return: All locations of t as a substring of s.

(https://rosalind.info/problems/subs/)

給定字符序列 $\mathscr{A}$，求由這些字符組成且長度小於等於 k 的所有字串。這些字串須依照 $\mathscr{A}$ 字典序排列。

Given: A permutation of at most 12 symbols defining an ordered alphabet $\mathscr{A}$ and a positive integer n (n≤4).

Return: All strings of length at most n formed from $\mathscr{A}$, ordered lexicographically. (Note: As in “Enumerating k-mers Lexicographically”, alphabet order is based on the order in which the symbols are given.)

(https://rosalind.info/problems/lexv/)

給定字符序列 $\mathscr{A}$，求由這些字符組成且長度為 k 的所有字串。這些字串須依照 $\mathscr{A}$ 字典序排列。

Given: A permutation of at most 12 symbols defining an ordered alphabet $\mathscr{A}$ and a positive integer n (n≤4).

Return: All strings of length at most n formed from $\mathscr{A}$ , ordered lexicographically. (Note: As in “Enumerating k-mers Lexicographically”, alphabet order is based on the order in which the symbols are given.)

(https://rosalind.info/problems/lexv/)

給定一正整數 n，求包含數字 1 到 n 與 -1 到 -n 的所有可能數列與其總數。

A signed permutation of length n is some ordering of the positive integers {1,2,…,n} in which each integer is then provided with either a positive or negative sign (for the sake of simplicity, we omit the positive sign). For example, π=(5,−3,−2,1,4) is a signed permutation of length 5

Given: A positive integer n≤6

Return: The total number of signed permutations of length n, followed by a list of all such permutations (you may list the signed permutations in any order).

給定一正整數 n，求包含數字 1 到 n 的所有可能數列與其總數。

A permutation of length n is an ordering of the positive integers {1,2,…,n} . For example, π=(5,3,2,1,4) is a permutation of length 5.

Given: A positive integer n≤7 .

Return: The total number of permutations of length n , followed by a list of all such permutations (in any order).

(https://rosalind.info/problems/perm/)