创建给定变量集的所有可能排列

Question

我有一个与反向翻译相关的问题。
问题本身可以表述为：给定 20 个唯一字母表的字符集（对应 20 个氨基酸），每个字母表由 3 个字符 [A,T,G,C 中的任意 3 个] 组成的代码生成。生成编码给定氨基酸的所有可能的核苷酸序列 sequence/strings.
20 种氨基酸有 64 种可能的核苷酸 [ATGC] 组合。对于用字母K表示的example:Lysine，由两个三联体（=密码子）AAA和GAA编码。

正向翻译很好，因为我可以将三联体映射到氨基酸代码，但问题在于反向翻译，其中三联体的各种组合是可能的，因为大多数氨基酸可以由多个密码子编码。

这是我程序的基本框架：

 //Map all Amino Acids with their corresponding codons.
std::map<std::string, string, std::less<std::string> >  somevar;
somevar["K"]="AAA|GAA";......so on.

//Take input in string of Amino Acid single letter codes.
//Split each Amino acid into corresponding codons using stringstream
while(std::getline(ss, token, '|')){}

//Store the values in vector.

第一个问题：因为我不知道输入字符串的大小，所以我需要动态向量数组或向量向量。（简单地说，如果它发生像 KK 这样的事情，将有两个数组类型变量存储 KK 的所有三元组。）有没有办法消除这种冗余（直接查看一些 table）？

//Pass the arrays to a function which will return all possible permutations.

第二题：在解决了第一题后，我想创建所有可能的核苷酸序列组合与给定的氨基酸字符串。（即，从每个新创建的数组（集合）派生的所有可能组合）。
KK 将导致：AAAGAA、AAAAAA、GAAAAA、GAAGAA。

唯一的限制是复杂度应该是 ~O(n^2)，我想知道我是否可以递归地做，或者 c++ 中是否有一些内置的 function/library 可以提供帮助我从给定的（可变）数据集生成所有可能的排列。

编辑：另一个例子假设随机字母 A 有 3 个密码子，字母 Y 有 5 个密码子，那么组合总数将为 3*5。

如果M=AAT,ATA，N=GTT,AGT,TGT，则结果为1)AATGTT,2)ATAGTT,3)AATAGT,4)AATTGT,5)ATAAGT,6)ATATGT

Answer 1

您真的想要获得所有排列（所有可能的密码子顺序），或所有可能的字母翻译成密码子（更像是谐音替换）吗？

如果是后者，对于你的问题2，如果所有字母都有2个可能的密码子（远远超过O(n^2)），输出字符串的数量将是O(2^n)。

您仍然可以使用递归函数使其相对简单（或者不使用，就像@Jarod42 那样）。

对于您的问题 1，我认为您的过程的输入实际上是一种存储输出的紧凑方式... 对于一个输入字符串，您的 return 类型可以是 std::vector<std::string>，所以您可以为所有输出字符串选择 std::vector<std::vector<std::string> >？

Answer 2

以下内容可能会有所帮助：

std::vector<std::string> translate(const std::vector<std::string>& v,
                                const std::map<std::string, std::vector<std::string>>& mapping)
{
    if (v.empty()) {
        return {};
    }
    std::vector<std::string> res = {""};

    for (const auto& s : v) {
        std::vector<std::string> tmp;

        for (const auto& seq : mapping.at(s)) {
            for (const auto& old: res) {
                tmp.push_back(old + seq);
            }
        }
        res = std::move(tmp);
    }
    return res;
}

与：

v 要翻译的序列
mapping "K" 和 {"AAA", "GAA"}

Live example

创建给定变量集的所有可能排列

Create all possible permutations of given variable set

c++

arrays

algorithm

bioinformatics

set