JavaScript - Xác định tất cả các cách loại bỏ một nhóm giá trị khỏi một chuỗi

Chúng ta cần viết một hàm JavaScript xác định có bao nhiêu cách khác nhau để loại bỏ một nhóm giá trị khỏi một chuỗi, giữ nguyên thứ tự ban đầu (ổn định), và đảm bảo chỉ loại bỏ một thể hiện của mỗi giá trị từ chuỗi gốc.

Ví dụ – Nếu mảng chuỗi là:

const arr = [1, 2, 1, 3, 1, 4, 4];

Và mảng cần loại bỏ là:

const arr2 = [1, 4, 4];

Thì có ba cách làm điều này mà không làm gián đoạn thứ tự các phần tử:

1 --> [2, 1, 3, 1]
2 --> [1, 2, 3, 1]
3 --> [1, 2, 1, 3]

Do đó, hàm của chúng ta nên xuất ra 3 cho các chuỗi này.

Ví dụ

const arr = [1, 2, 1, 3, 1, 4, 4];
const arr2 = [1, 4, 4];
const possibleRemovalCombinations = (original, part) => {
  const sorter = (a, b) => a - b;
  part.sort(sorter);
  let place = [];
  part.forEach(el => { place[el] = [] });
  original.forEach((el, index) => {
    if(place[el]){ place[el].push(index); }
  });
  let connection = part.map(el => place[el].slice());
  for(let i = 1; i < connection.length; i++){
    if (part[i - 1] != part[i]){ continue; }
    let left = connection[i - 1][0];
    while(connection[i][0] <= left){ connection[i].shift(); }
  }
  for (let i = connection.length - 2; i >= 0; i--) {
    if(part[i] != part[i + 1]){ continue; }
    let right = connection[i + 1][connection[i + 1].length - 1];
    while(connection[i][connection[i].length - 1] >= right){ connection[i].pop(); }
  }
  const combineArray = (step, prev, combination) => {
    for (let i = 0; i < connection[step].length; i++) {
      let curr = connection[step][i];
      if(prev >= curr && original[prev] == original[curr]){ continue; }
      if(step + 1 == connection.length){
        combinations.push(combination.concat([curr]))
      } else {
        combineArray(step + 1, curr, combination.concat([curr]));
      }
    }
  };
  let combinations = [], res = [];
  combineArray(0, -1, []);
  for (let i = 0; i < combinations.length; i++) {
    let copy = original.slice();
    combinations[i].forEach(el => copy[el]);
    res[i] = copy.filter(el => el !== undefined);
  }
  return res.length;
};
console.log(possibleRemovalCombinations(arr, arr2));

Kết quả

Kết quả trong console:

3