在 JS 中查找与给定模式匹配的所有可能的字符串组合

Question

所以我有一个字典，其中每个键都映射到一个字母数组：

tCategories = { "T": ["t","d","th"],
                "P": ["p","t","k","q"],
                "N": ["m","n"] };

还有一个输入字符串，其中包含一些以逗号分隔的模式，例如"aT,Ps,eNe,NP"，其中作为 tCategories 的有效键的子字符串充当 tCategories[key].

中任何字母的替代

我想弄清楚的是如何找到输入字符串中列出的每个模式的每个组合并将它们全部放入一个数组中。所以例如foo("aT,Ps,eNe,NP") 的预期输出为 ["at","ad","ath","ps","ts","ks","qs","eme","ene","mp","mt","mk","mq","np","nt","nk","nq"].

我的第一直觉是在输入字符串上调用 String.split(",") 来分别处理每个子字符串，或者通过 for (var key in tCategories) { input.replace(new RegExp(key, "g"), "["+tCategories[key].join("|")+"]" } 或其他方式进行迭代......但我就是做不到似乎在这些和预期输出之间找到了一条有用的途径。这将涉及...什么，基本上实现分配属性但对于字母而不是数字？我该怎么做？

Answer 1

原答案见下文。

更新答案

此答案适用于递归并收集组，例如

a[Ps,T]

通过替换括号和逗号创建一个新类别 (Ps-T) 并采用

的结果

Ps,T
ps ts ks qs t d th

这也适用于嵌套括号。替换顺序从内到外括号。

随着这一变化，有必要接受比一个字符更长的密钥。现在它搜索最长的密钥到最小的密钥。如果不存在键，则需要单个字母进行笛卡尔准备。

function convert(string, tCategories) {
    const cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []);

    let change;

    do {
        change = false;
        string = string.replace(/\[([^\[\]]+)\]/g, (_, p) => {
            const key = `(${p.replace(/,/g, '-')})`;
            tCategories[key] = convert(p, tCategories);
            change = true;
            return key;
        });
    } while (change);

    return string
        .split(/,/)
        .map(s => {
            const
                keys = Object.keys(tCategories).sort((a, b) => b.length - a.length),
                result = [];

            while (s.length) {
                const sub = keys.find(k => s.startsWith(k));
                if (sub) {
                    result.push(tCategories[sub]);
                    s = s.slice(sub.length);
                } else {
                    result.push([s[0]]);
                    s = s.slice(1);
                }
            }
            while (result.length < 2) result.push(['']);
            return result;
        })
        .map(a => a.reduce(cartesian).map(a => a.join('')))
        .flat();
}

const
    tCategories = { T: ["t", "d", "th"], P: ["p", "t", "k", "q"], N: ["m", "n"], Approx: ["j", "w"] };

console.log(convert('Ps,T', { ...tCategories }));
console.log(convert('a[Ps,T]', { ...tCategories }));
console.log(convert('a[Ps,T[aPbcApprox]],eNe,NP', { ...tCategories }));
console.log(convert("V,eNe,a[Ps,T],,ApproxT", { ...tCategories }));

.as-console-wrapper { max-height: 100% !important; top: 0; }

原答案

您可以用逗号分隔字符串，用数组替换组，用数组中的字符替换单个字符，获取笛卡尔积，连接内部数组并获取包含结果的数组。

最后把阵列放平。

const 
    cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []),
    foo = string => string
        .split(',')
        .map(s => Array.from(s, c => tCategories[c] || [c]))
        .map(a => a.reduce(cartesian).map(a => a.join('')))
        .flat(),
    tCategories = { T: ["t", "d", "th"], P: ["p", "t", "k", "q"], N: ["m", "n"] };

console.log(...foo("aT,Ps,eNe,NP"));

Answer 2

这是关于@Arcaeca 的赏金更新，他要求 3 件事：

1- 当 key.length > 1 时，行 .map(s => Array.from(s, c => tCategories[c] || [c])) 不会用对应的值替换 tCategories 的键。

2- 传递带有空子模式的输入字符串（即由“,”分隔的子字符串），例如"aT,Ps,eNe,,NP"，导致函数抛出：TypeError.

3- 这是一个新功能，我试图添加的是通过将它们括在方括号 [ ] 中来当场定义“nonce”类别的能力，例如输入字符串 "a[Ps,T]" 应产生与 "aPs,aT"

相同的输出

我的回答（来自@Nina Scholz 的回答）

我将从第三个要求开始，因为它是全新的，所以为了简单起见，我将创建另一个函数来解析给定的字符串并检查它是否有方括号乘法，然后解析它，例如输入 "a[Ps,T]"，输出将是 "aPs,aT" 例如输入 "a[T, X]d"，输出将是 "aTd, aXd" 我将其称为 clean()。您可以根据需要增强此功能。

const clean = string => {
    while (true) {
        const patterns = [
            /(\w+)\[([\w+\,]*)\](\w+)*/,
            /(\w+)*\[([\w+\,]*)\](\w+)/
        ]
        let match = null
        for (const i in patterns) {
            match = patterns[i].exec(string)
            if (match) {
                break;
            }
        }
        if (!match) {
            break
        }
        const newString = [match[1] ? [match[1]] : [''], match[2].split(',').map(v => v.replace(',', '')), match[3] ? [match[3]] : ['']].reduce(cartesian).map(a => a.join('')).join(',')
        string = string.replace(match[0], newString)
    }
    return string
};

针对前两个需求，我做了这个修改

const foo = string => Object.keys(tCategories)
    .reduce((a, b) => a.replaceAll(b, `?${b}?`), string)
    .split(',')
    .map(v => v.split('?').map(t => tCategories[t] || [[t]]))
    .map(a => a.reduce(cartesian).map(a => a.join('')))
    .flat()

我所做的是，我遍历了 tCategories 的每个键，然后检查我的字符串是否包含该键，如果是，则在它周围放置一个占位符以便于识别它，在我的示例中，我选择了 ?，并摆脱了 Array.from 方法。现在我们的函数支持长度 > 1 的键，以及空子模式。

完整示例

let tCategories = { T: ["t", "d", "th"], P: ["p", "t", "k", "q"], N: ["m", "n"], KK: ['a', 'b'] };

const cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []);

const clean = string => {
    while (true) {
        const patterns = [
            /(\w+)\[([\w+\,]*)\](\w+)*/,
            /(\w+)*\[([\w+\,]*)\](\w+)/
        ]
        let match = null
        for (const i in patterns) {
            match = patterns[i].exec(string)
            if (match) {
                break;
            }
        }
        if (!match) {
            break
        }
        const newString = [match[1] ? [match[1]] : [''], match[2].split(',').map(v => v.replace(',', '')), match[3] ? [match[3]] : ['']].reduce(cartesian).map(a => a.join('')).join(',')
        string = string.replace(match[0], newString)
    }
    return string
};

const foo = string => Object.keys(tCategories)
    .reduce((a, b) => a.replaceAll(b, `?${b}?`), string)
    .split(',')
    .map(v => v.split('?').map(t => tCategories[t] || [[t]]))
    .map(a => a.reduce(cartesian).map(a => a.join('')))
    .flat()

console.log(...foo(clean('aT,Ps,eNe,NP,,KK[z,c,f]')))

Answer 3

原题：

   const tCategories = {
      "T": ["t","d","th"],
      "P": ["p","t","k","q"],
      "N": ["m","n"],
    };
    
    // Think matrix like multiplication
    function multiply(twoDArray1, twoDArray2) {
      const product = [];
      for (let i = 0; i < twoDArray1.length; i++) {
        for (let j = 0; j < twoDArray2.length; j++) {
          product.push([...twoDArray1[i], twoDArray2[j]]);
        }
      }
      return product;
    }
    
    function stringHasCategories(inputString) {
      for (let i = 0, ch = inputString.charAt(0); i < inputString.length; i++, ch = inputString.charAt(i)) {
        if (tCategories[ch]) {
          return true;
        }
      }
      return false;
    }
                        
    function expandCategories(inputString) {
      if (!stringHasCategories(inputString)) {
        return inputString;
      }
      let output = [[]];
      for (let i = 0, ch = inputString.charAt(0); i < inputString.length; i++, ch = inputString.charAt(i)) {
         if (tCategories[ch]) {
           output = multiply(output, tCategories[ch]);
         } 
         else {
           output.forEach((op) => op.push(ch));
         }
      }
      output.forEach((op, i) => { output[i] = op.join(''); });
      return output;
    }
                        
    function foo(inputString = "aT,Ps,eNe,NP") {
      return inputString
        .split(',')
        .map(expandCategories)
        .flat();
    }
    
    console.log(foo());

更新问题：

https://gist.github.com/EarthyOrange/1f9ca9ae606b61d435fef484bbf96945

在 JS 中查找与给定模式匹配的所有可能的字符串组合

Find all possible combinations of strings that match a given pattern in JS

javascript

arrays

string

pattern-matching

cartesian-product

更新答案

原答案