DNA computing

Tags:

Description

DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, molecular computing, is a fast developing interdisciplinary area. Research and development in this area concerns theory, experiments and applications of DNA computing. DNA computing is fundamentally similar to parallel computing in that it takes advantage of the many different molecules of DNA to try many different possibilities at once. So, many NP problem can be solved through DNA computing , such as Hamiltonian path problem, SAT problems, and so on.

The core reaction of DNA computing is the specific hybridization, which may results in incorrect or undesirable computations. Therefore, so far much works have focused on designing the DNA sequences to make the molecular computation more reliable.

The DNA encoding problem can be described as follows: the encoding alphabet of  DNA sequence is the set of nucleic acid bases Σ={A, C, G, T},and in the encoding set Z of DNA strands whose length is L, Z=Σ¹={<b₁b₂...b_L>|b_i∈Σ, i=1,2,...,L}, and |Z|=4^L, search the subset W of Z which satisfies (any subset of Z can be treat as a code set):

(1) ∀x_i∈W, the total number of A、C in x_i is L/2;

(2) ∀x_i, x_j∈W, the hamming distance （the Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different）between x_i and x_j is at least D.

In order to simplify the encoding problem, we don’t want you to find such a subset with the biggest size, we only want you to find the best subset satisfying the two conditions. The strategy to compare two subset is as follows:

Suppose W₁, W₂ are two subset satisfying the two conditions. If W_i(i=1, 2) is a subset of W_j (j=2,1), then Wj (j=2,1) is better than W_i (i=1,2). Otherwise,  we firstly order the elements of them independently based on lexicographic. then, we get the first element x₁ from W₁ and the first element y₁ from W₂. We consider W₁ to be better than W₂ if x₁ is in front of y₁ in lexicographic.  on the contrary, we think W₂ is better than W₁ if x₁ is behind y₁. On the other hand, if x₁ is the same as y₁, we then get the second element x₂ from W₁ and the second element y₂ from W₂ , if they are also the same ,we will get the next pairs until we can evaluate them.

For examples :

(1) W₁ = { A, C, G, T}, W₂ = {A, T}

W₁ is better than W₂ because W₂ is a subset of W₁.

(2) W₁={AC, CT, AT}, W₂={AG, AC}

Firstly ,we order them, so W₁={AC, AT, CT}, W₂={AC, AG} 

Then W₂ is better than W₁ because AG is in front of AT.

Now , we will give you the length L and the distance D, can you find the best code set.

Input

There are several cases. Each case contains two integers, L (0<L≤25) and D (0≤D≤L) .

Output

For each case, output several lines, the first line is the size of the code set, then print all the elements of the code set in lexicographic. A element per line.

Samples

Source