JavaScript - หาวิธีการลบกลุ่มค่าออกจากลำดับได้ทั้งหมด

เราต้องเขียนฟังก์ชัน JavaScript ที่กำหนดว่ามีกี่วิธีที่แตกต่างกันที่เราสามารถลบกลุ่มค่าออกจากลำดับได้ โดยคงลำดับเดิมของลำดับ (stable) และลบเพียงหนึ่งอินสแตนซ์ของแต่ละค่าจากลำดับเดิม

ตัวอย่างเช่น ถ้าอาร์เรย์ลำดับคือ

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

และอาร์เรย์ที่จะลบคือ

const arr2 = [1, 4, 4];

แล้วมีสามวิธีที่เป็นไปได้ในการทำเช่นนี้โดยไม่รบกวนลำดับขององค์ประกอบ

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

ดังนั้น ฟังก์ชันของเราควรคืนค่า 3 สำหรับลำดับเหล่านี้ โค้ดสำหรับการทำงานนี้จะเป็นดังนี้

ตัวอย่างโค้ด

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));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็นดังนี้

3