JS数组插入问题，对于一个数组，将一个或多个字母S插入，输出所有长度小于等于6位的新数组，有什么思路吗？

Question

对于数组

Array = ["A","B","C"]

将字母 S 插入生成新的长度不大于6位的数组（不改变ABC整体的顺序）

//输出所有满足条件的新数组 
["S","A","B","C"]
["S","A","S","B","C"]
["S","A","S","B","S","C"]
...

有什么思路，或者简洁的写法吗？

Answer 1

简单的排列组合问题,回溯算法的复杂度比较复杂，用能力的可以自己算一下

const permutation = (data: string[]): string[][] => {
  if (data.length >= 6) return [];

  const used: number[] = [];
  const n = data.length;
  const ans: string[][] = [];
  const Impl = (i: number, remaining: number) => {
    if (i === n || remaining === 0) {
      const cand: string[] = [];
      for (let i = 0; i < n; ++i) {
        if (used[i]) {
          cand.push(
            ...Array.from<string>({ length: used[i] }).fill("S")
          );
        }
        cand.push(data[i]);
      }

      if (cand.length) {
        ans.push(cand);
      }
      if (remaining) {
        for (let k = 1; k <= remaining; ++k) {
          ans.push([...cand, ...Array.from<string>({ length: k }).fill("S")]);
        }
      }

      return;
    }

    for (let k = 0; k <= remaining; ++k) {
      used[i] = k;
      Impl(i + 1, remaining - k);
      used[i] = 0;
    }
  };

  Impl(0, 6 - n);

  return ans;
};

console.log(
  permutation(["A", "B", "C"])
    .sort((a, b) => a.length - b.length)
    .map((v) => v.toString())
);

Answer 2

我算出来有34条

start(arr, res = []) {
      let length = arr.length,
        str = 's',
        max = 6,
        i = 0;
      while (i <= length) {
        let b = JSON.parse(JSON.stringify(arr));
        b.splice(i++, 0, str)
        if (b.length <= max) {
          res.push(b.toString());
          this.start(b, res);
        }
      }
      return res; 
    }
let res = this.start(['A', 'B', 'C'])
console.log([...new Set(res)].sort());

Answer 3

因为是算法题，所以更多的是从算法上考虑：

1. 对于输入数组，判断长度，获得'S'的可能集合。对于[],'S'的可能集合是["S"]、["S", "S"]、["S", "S","S"]、["S","S","S","S""]、["S", "S","S","S","S"]、["S", "S","S","S","S","S"],对于其它输入数值A，则是[1,(6-A.length)]个'S'，且A.length<6
2. 对于输入数组A，在A.length<6 时，可能插入'S'数组位置为 A.length+1个
3. 对于不同的'S'的可能集合，进行再分组（新的组合问题），根据分组数量，从数组A可能插入'S'数组位置中，选择对应数量位置，分别插入。