笛卡尔积与awk找到所有可能的组合

Question

我有这个函数来生成字符串的所有可能组合。从捕获方括号中的内容开始，然后使用正则表达式将其替换为字符串。

我认为我创建嵌套数组的循环存在问题

pairs

，但我坚持使用它。

function delineate(s) {
    tmp=s;
    while (match(tmp, /(\[[^]]*\])/, key)) {
        tmp=substr(tmp, RSTART+RLENGTH);
        value=key[1];
        gsub(/[][]/, "\\\\&", key[1])
        gsub(/[][]/, "", value);
        gsub(/./, "& ", value);
        hash[key[1]]=value;
    }
    solutions=1;
    for (i in hash) {
        n=split(hash[i], a, " ");
        solutions*=entries[++j]=n;
        keys[j]=i;
        for (k=0; k<n; k++) {
            list[i][k]=a[k+1]
        }
    };
# This might be where it causes the error.
    for (i=0; i<solutions; i++) {
        for (j=1; j<=length(entries); j++) {
            pairs[i][j]=keys[j] " " list[keys[j]][i % entries[j]]
        }
    }
    for (i in pairs) {
        tmp=s;
        for (j in pairs[i]) {
            split(pairs[i][j], re, " ");
            gsub(re[1], re[2], tmp);
        };
        res[tmp]
    }
}

BEGIN {delineate("A[BC]T[KM]G"); for (i in res) print i}

假设对于上述输入

A[BC]T[KM]G

，预期输出为：

ABTKG
ABTMG
ACTKG
ACTMG

这等于 2 乘以 2，所以它必须有 4 个解。但我只得到这个输出：

ABTKG
ACTMG

Answer 1

所以我对导致问题的循环是正确的。

function delineate(s) {
    tmp=s;
    while (match(tmp, /(\[[^]]*\])/, key)) {
        tmp=substr(tmp, RSTART+RLENGTH);
        value=key[1];
        gsub(/[][]/, "\\\\&", key[1])
        gsub(/[][]/, "", value);
        gsub(/./, "& ", value);
        hash[key[1]]=value;
    }
    solutions=1;
    for (i in hash) {
        n=split(hash[i], a, " ");
        solutions*=entries[++j]=n;
        keys[j]=i;
        for (k=0; k<n; k++) {
            list[i][k]=a[k+1]
        }
    };
    for (i=1; i<=solutions; i++) {
# Add a variable idx here
        idx=i;
        for (j=1; j<=length(entries); j++) {
            divisor=entries[j];
            pairs[i][j]=keys[j] " " list[keys[j]][idx%divisor];
# Update the idx with integer of idx / entries[j]
# By updating the idx, we will be able to generate all possible combinations
            idx=int(idx/divisor);
        }
    }
    for (i in pairs) {
        tmp=s;
        for (j in pairs[i]) {
            split(pairs[i][j], re, " ");
            gsub(re[1], re[2], tmp);
        };
        res[tmp]
    }
}

BEGIN {delineate("A[BC]T[KM]G"); for (i in res) print i}

欢迎任何改进代码的想法:)。

Answer 2

不是

awk

解决方案，而是因为 GNU

parallel

能够处理笛卡尔积...要使用 GNU

parallel

生成所有这些笛卡尔积：

$ parallel echo A ::: B C ::: T ::: K M ::: G
A B T K G
A B T M G
A C T K G
A C T M G

A ::: B C ::: T ::: K M ::: G

为 GNU

parallel

定义了 5 组输入，其中 2 组包含 2 个输入，其他仅包含一个。 GNU

parallel

使用输入组的所有笛卡尔组合调用

echo

。

如果您想保留输入格式并抑制输出中的空格，您可以添加一些预处理和后处理。具有 9 个产品和多字符单例的示例：

$ parallel echo \
  $(sed -E ':a;s/\[(( [^] ])*)([^] ])/[\1 \3/g;ta;s/[][]/ ::: /g;s/\]/ ::: /g' <<< "AA[BCD]TTT[KMN]GGGG") |
  sed 's/ //g'
AABTTTKGGGG
AABTTTMGGGG
AABTTTNGGGG
AACTTTKGGGG
AACTTTMGGGG
AACTTTNGGGG
AADTTTKGGGG
AADTTTMGGGG
AADTTTNGGGG