JS循环嵌套问题？

Question

现有一个函数change，接收两个参数，参数arr为一数组，形如 ["A","T","C","G"] ,该数组元素值只可能为字符串"A","T","C","G"之一，参数count为一int，值小于等于arr的长度。
函数change实现的功能是将数组arr内的count个元素改为除原值以外的ATCG中另外三个，如"A"改为 "T"/"C"/"G" ，然后输出一个新的二维数组outPut，outPut内每个元素都是一个数组，其值为改变后的所有可能性。

---

如：原数组arr=["A","C"]，改变个数count=1，
输出数组

outPut=[
    ["T","C"],["C","C"],["G","C"],["A","A"],["A","T"],["A","G"]
]

---

写了如下函数change，写到一半发现循环嵌套层数问题，不知如何继续，求助~~~

function change(arr,count){
    for(var i = 0; i < arr.length; i ++){
        switch (arr[i]){
            case "A":
            
        }
    }
}

Answer 1

以下是一种递归实现：

const legalVals = ['A', 'C', 'G', 'T'];

function change(arr, count) {
    count = parseInt(count);
    if (!Array.isArray(arr) || count < 0 || count > arr.length) throw `Illegal argument`;
    if (arr.find(e => !legalVals.includes(e))) throw `Illegal member(s)`;
    if (arr.length === 0 || count === 0) return [arr];
    return doChange(arr, count)
}

function doChange(arr, count) {
    const length = arr.length;
    //数组的第一个元素
    const v0 = arr[0];
    //第一个元素可以替换的值
    const diff0 = legalVals.filter(e => e !== v0);

    //边界条件：不替换任何值
    if (count === 0) {
        return [arr];
    }
    //边界条件：长度为1且只替换1个
    if (length === 1) {
        return diff0.map(e => [e]);
    }
    //替换掉第一个元素的结果
    const change1st = unshiftEach(diff0, doChange(arr.slice(1), count - 1));
    //边界条件：如果count === length，那么第一个元素是必须替换的
    if (count === length) {
        return change1st;
    }
    //不替换第一个的结果
    const changeOthers = unshiftEach([v0], doChange(arr.slice(1), count));

    //排除以上边界条件的通常情况，总结果= 替换掉第一个元素的结果 + 不替换第一个的结果
    return change1st.concat(changeOthers);
}

//将arr的每个元素拼接到arr2（二维数组）的每个元素前。（笛卡尔积）
function unshiftEach(arr, arr2) {
    return arr2.flatMap(item =>
        arr.map(e => {
            const result = item.slice();
            result.unshift(e);
            return result;
        })
    )
}

Answer 2

提供一个我认为比较好理解的思路,分为两个步骤来处理

代码实现

const allKey = ['A', 'T', 'C', 'G']

const isArray = Array.isArray

// 聚合多个数组
// [[A,B],[C,D]] => [[A,C],[A,D],[B,C],[B,D]]
function pair(arr1, arr2, ...arrs) {
  if (!arr2) return arr1
  if (!arrs[0]) {
    return arr1.reduce(
      (acc, a1) =>
        acc.concat(arr2.map(a2 => (isArray(a1) ? a1 : [a1]).concat(a2))),
      [],
    )
  }
  return pair(pair(arr1, arr2), ...arrs)
}

function change(arr, count) {
  let group1 = []
  // 根据 count 从 arr 中确定需要改变部分和不变部分的组合
  for (let i = 0; i < arr.length - count + 1; i++) {
    let item = [...arr]
    item.splice(i, count, arr.slice(i, i + count))
    group1.push(item)
  }

  let group2 = []
  // 替换需要改变部分
  for (let i = 0; i < group1.length; i++) {
    const item = group1[i]
    for (let j = 0; j < item.length; j++) {
      const item1 = item[j]
      if (isArray(item1)) {
        const before = item.slice(0, i)
        const dif = item1.map(e => allKey.filter(v => v !== e))
        const after = item.slice(i + 1, item.length)
        group2 = group2.concat(pair(...[[before], ...dif, [after]]))
      }
    }
  }

  return group2
}

Answer 3

从arr中挑选出来需要保存的(arr.length - count)所有可能的组合，然后再从原数组中挑选出来所有可能的(count)补充组合，然后拼在一起去重就行了。

(async ()=>{
    let vari = ['A','T','C','G'];
    function change(arr, count = 1){
        arr = arr.map(a=>vari.indexOf(a)).sort(); // convert to int array, for easier sorting in future

        var prefix = combination(arr, arr.length - count);
        var suffix = combination([0,1,2,3], count);

        var res = prefix.length === 0 ? suffix : prefix.map(p=>suffix.map(s=>[...p, ...s])).reduce((a,b)=>[...a,...b], []);

        var existing = arr.join(",");
        res = res
                .filter(r=>new Set(r).size === r.length) // filter out ones with duplicated items, like ["A","A","C"]
                .map(r=>r.sort()) // order items, so ["C","A"] becomes ["A", "c"]
                .sort() // sort, just make it looks prettier
                .reduce((a,b)=>{ // remove duplicated combinations, keep only one
                    if(a[b.join(",")] === void 0){
                        a.arr.push(b);
                        a[b.join(",")] = 0;
                    }
                    return a;
                }, {arr: []}).arr
                .filter(r=>r.join(",") !== existing);
        return res.map(r=>r.map((i)=>vari[i]));// convert back to letters
    }

    function combination(src, pick){
        if(pick > src.length){
            return [];
        }
        if(pick === 1){
            return src.map(s=>[s]);
        }
        var res = [];
        for(var i=0;i<src.length;i++){
            for(var r of combination(src.slice(i+1), pick - 1)){
                res.push([src[i], ...r]);
            }
        }
        return res;
    }

    console.log(change(["G","A","C"], 2));
})();

output [A,T,C],[A,T,G],[T,C,G]

Answer 4

没看太懂，如果count是2，结果是不是t,gg,g

Answer 5

1. 没说数组成员是否允许重复
2. i最后不是做++操作，而是加count，因为每次替换的是count个，就是循环粒度
3. 每次从arr里取出count个元素，求它们与原始数组的差，也就是除了count个元素以外的元素，将它们循环填入取出元素的位置，然后push到result数组
4. 循环结束后返回result数组
5. 注意处理一些意外情况

Answer 6

是不是应该就是，指定数量搞一个枚举，然后除去原始数据那种排列，就是结果。