Lua：给定符号列表，迭代每个可能的k长度字符串

2014-3-24 0:17:12
收藏：0
阅读：88
评论：2

我想通过给定符号列表来迭代每个可能的k长度字符串（称为_k-mer_）。例如，如果 k = 3 和 symbols = {A, C, G, T}，那么：

AAA
AAC
AAG
...
TTG
TTT

以下是生成字符串的代码：

local k = 3
local bases = {'A', 'C', 'T', 'G'}

-- 生成字符串（AAA...AAA）
local kmer_gen = {}
for i = 1,k do kmer_gen[i] = "A" end
local kmer = table.concat(kmer_gen)

这个代码可以工作，但看起来并不好看。有更优雅的方法吗？

现在，我不确定如何迭代可能的k-mer。一种解决方案是保持替换每个字符，但这似乎不是很有效。另一种方法是从二进制解码（每2位表示一个基），但实现是令人困惑的，并需要位运算。还有其他想法吗？

点赞
用户204011
用户204011

以下是我可能会使用的一个比较简单的尾递归解决方案：

local bases = {'A', 'C', 'T', 'G'}

local function kmers(n, prev)
  prev = prev or {''}
  if n <= 0 then return prev end
  local k,r = 1,{}
  for i=1,#prev do
    for j=1,#bases do
      r[k] = prev[i] .. bases[j]
      k = k+1
    end
  end
  return kmers(n-1, r)
end

_3mers = kmers(3) -- 使用示例

注：你可以写成 r[#r+1] 而不是手动管理 k，但在这种情况下这样做并不复杂，并且速度更快（# 运算符是 O(log n)）。

2013-11-06 09:25:15
用户107090
用户107090

下面是一种使用迭代器的解决方案。这是Lua中值得学习的协同技术的良好示例。请参见http://www.lua.org/pil/9.3.html。

local bases = {'A', 'C', 'T', 'G'}

local function allstrings(n,t,k,s)
    k=k or 1
    s=s or {}
    if k>n then
        coroutine.yield(table.concat(s))
    else
        for i=1,#t do
            s[k]=t[i]
            allstrings(n,t,k+1,s)
        end
    end
end

local function kmer(n,t)
    return coroutine.wrap(allstrings),n,t
end

for w in kmer(3,bases) do
    print(w)
end
2013-11-06 10:44:54

作者:

用户604734

用户604734
推荐文章