Алгоритм для определения всех возможных путей удаления группы значений из последовательности

Ответ 1

(Поскольку в исходной версии вопроса было непонятно, хотите ли вы удалить подпоследовательность или неупорядоченный список, я обновил свой ответ, чтобы ответить на оба случая.)

1. Удаление подпоследовательности в порядке

Мы получаем последовательность значений, например. [1,5,1,3,4,2,3,2,1,3,1,2] и подпоследовательность значений, подлежащих удалению из первой последовательности, например. [1,3,2,1]. Если мы найдем, где каждый экземпляр значений находится в последовательности, мы получим такой график:

Поиск всех способов, в которых значения могут быть удалены из последовательности, по порядку, затем означает поиск всех способов, с помощью которых подлежащие удалению значения в нижней строке могут быть подключены к экземпляру в последовательности без каких-либо пересечения линий, например:

Чтобы избежать удаления значений способом, который не приводит к допустимому решению (например, начиная с удаления самого правого значения 1, после которого нет значения 3, которое можно удалить), мы сначала удалим все соединения на графике, которые приводят к таким недействительным решениям.

Это будет выполнено путем повторения по подпоследовательности дважды. Сначала мы делаем это слева направо, и для каждого значения мы смотрим на его самое левое соединение и удаляем любые соединения из значения в его право, которое соответствует или пересекает это соединение; например при рассмотрении самого левого соединения со значением 2, два соединения из значения 1 справа (обозначены красным) удаляются, поскольку они пересекают это соединение:

В следующем шаге мы переходим справа налево, и для каждого значения мы смотрим его самое правильное соединение и удаляем любые соединения из значения слева от него, которое встречает или пересекает это соединение; например при рассмотрении самого правильного соединения со значением 1 справа справа удаляется самое правое соединение из значения 2 слева (указано красным), поскольку оно пересекает это соединение:

Затем мы заканчиваем упрощенным графиком, показанным ниже. Затем эти комбинации объединяют каждый подключенный экземпляр каждого значения в подпоследовательности, используя, например, recursion: вы перебираете опции для первого значения в подпоследовательности и каждый раз рекурсируете с остальной частью подпоследовательности, чтобы опция для первого значения объединялась со всеми параметрами для других значений.

В упрощенном графике могут быть скрещенные соединения, но они уже не проблематичны. В примере вы увидите, что даже если для значения 3 выбрано правильное соединение, существует соединение для значения 2, которое не пересекает его:

Включение этого в код относительно просто; ниже фрагмента кода вы найдете прогон кода с данными из примера.

function removeSubSeq(seq, sub) {
    var posi = []; // list position of values in seq, then connect to positions in sub
    sub.forEach(function(elem) {posi[elem] = []});
    seq.forEach(function(elem, index) {if (posi[elem]) posi[elem].push(index)});
    var conn = sub.map(function(elem) {return posi[elem].slice()});

    for (var i = 1; i < conn.length; i++) {
        var left = conn[i - 1][0];
        while (conn[i][0] <= left) {
            conn[i].shift();                // remove crossed connection left-to-right
        }
    }
    for (var i = conn.length - 2; i >= 0; i--) {
        var right = conn[i + 1][conn[i + 1].length - 1];
        while (conn[i][conn[i].length - 1] >= right) {
            conn[i].pop();                  // remove crossed connection right-to-left
        }
    }
    var combinations = [], result = [];
    combine(0, -1, []);                     // initiate recursion to find combinations
    for (var i = 0; i < combinations.length; i++) {
        result[i] = seq.slice();            // create copies of seq and remove values
        for (var j = combinations[i].length - 1; j >= 0; j--) {
            result[i].splice(combinations[i][j], 1);
        }
    }
    return result;

    function combine(step, prev, comb) {    // generate combinations using recursion
        for (var i = 0; i < conn[step].length; i++) {
            var curr = conn[step][i];
            if (prev >= curr) continue;     // skip crossed connection
            if (step + 1 == conn.length) combinations.push(comb.concat([curr]));
            else combine(step + 1, curr, comb.concat([curr]));
        }
    }
}
var result = removeSubSeq([1,5,1,3,4,2,3,2,1,3,1,2], [1,3,2,1]);
for (var i in result) document.write(result[i] + "<br>");

Ответ 2

Это можно сделать с помощью простой комбинаторики.

Для простоты, скажем, значения в исходном списке 1,2,3,...,n.
Пусть a[i] - количество событий i в исходном списке.
Пусть b[i] - число событий i в списке изъятий значений

Число вариантов уменьшения i равно Choose(a[i],b[i]) = a[i]!/((a[i]-b[i])!b[i]!)

Поскольку вы объединяете все это в закрытие "AND", общее количество возможностей:

Choose(a[1],b[1]) * Choose(a[2],b[2]) * ... * Choose(a[n], b[n])

Что касается значений, которые не входят в набор редукций, вам не нужно беспокоиться о них. так как их значение в списке b будет равно 0, а Choose(x,0) = 1 для всех x

Это дает вам линейное временное решение (предполагая, что вы можете рассчитывать Select (.,.) в постоянное время после выполнения некоторой предварительной обработки для кеширования факториалов.

В вашем примере у вас есть:

a = [3, 1, 1, 2]
b = [1, 0, 0, 2]
Choose(3,1) = 3
Choose(1,0) = 1
Choose(1,0) = 1
Choose(2,2) = 1
#number_possibilities = 3 * 1 * 1 * 1 = 3

Ответ 3

(Также см. мои два других ответа ниже, как для упорядоченных, так и для неупорядоченных комбинаций с несколькими наборами.)

Чтобы избежать "мертвых концов" в рекурсии, создайте комбинации из хешированных индексов. Например,

[1,2,1,3,1,4,4] / [1,3] 

Hash = {1: [0,2,4], 3: [3]} // for repeated elements in the to-be-removed array,
                            // you could reserve the first element of the index array


Use the multi-set combination algorithm of your choice to make combinations from the 
hashed indexes, like [0,3], [2,3], etc.; and accumulate results without the corresponding elements.

Ответ 4

Чтобы определить все способы, с которыми группа значений (позвольте назвать эту группу needles) можно удалить из последовательности (называемой haystack), выполните следующие действия:

• Укажите, сколько раз вам нужно удалить каждый needle (позвольте этому счету k). Это может быть определено одним проходом над needles.
• Найти все местоположения каждого needle, которые нужно удалить в haystack. Это может быть определено одним проходом над haystack.
• Создайте все возможные способы удаления каждого из needle k времени из найденных мест. Это стандартная перечисление k-комбинаций, а ее временная сложность не многочлена.
• Сгенерировать все возможные способы объединения всех возможностей удаления needle. Это стандартный n-fold декартово произведение, а его временная сложность также не многочлена.
• Для каждого найденного пути отфильтруйте соответствующие элементы из haystack.

Ниже приведена реализация этого подхода ECMAScript 2016:

function* removalCombinations(haystack, needles) {
  // Comments walk through sample input of haystack = [1,2,1,3,1,4,4] and needles = [1,4,4]

  // How many of each needle there are, e.g.,
  // needleCounts = { 1 => 1, 4 => 2 }
  let needleCounts = elementCounts(needles);

  // Where each needle is located, e.g.,
  // needleIndexes = { 1 => [ 0, 2, 4 ], 4 => [ 5, 6 ] }
  let needleIndexes = findIndices(needleCounts.keys(), haystack.entries());

  // The possible indices to be removed for a particular needle, e.g.,
  // indexCombinations = [ [ [ 0 ], [ 2 ], [ 4 ] ], [ [ 5, 6 ] ] ]
  var indexCombinations = [];
  for (let [needle, indexes] of needleIndexes) {
    indexCombinations.push(Array.from(generateCombinations(indexes, needleCounts.get(needle))));
  }

  // All the ways that the possible index removals can be fully combined together, e.g.,
  // fullRemovalCombinations = [ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ]
  let fullRemovalCombinations = cartesianProductOf(indexCombinations);

  // For every possible index removal combination,
  // filter those indices from the original haystack, e.g.,
  // yielded values = [ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ]
  for (let indicesToFilter of fullRemovalCombinations) {
    indicesToFilter = new Set(indicesToFilter);
    yield haystack.filter((_, index) => !indicesToFilter.has(index))
  }

  // Calculates how many there are of each element.
  function elementCounts(iterable) {
    let counts = new Map();
    for (let el of iterable) {
      counts.set(el, counts.get(el) + 1 || 1);
    }
    return counts;
  }

  // Finds the indices of where each target occurs within iterable.
  function findIndices(targets, entries) {
    let indices = new Map();
    for (let el of targets) {
      indices.set(el, []);
    }
    for (let [index, value] of entries) {
      if (indices.has(value)) {
        indices.get(value).push(index);
      }
    }
    return indices;
  }

  // Generates all possible combinations of choosing k elements from arr.
  function* generateCombinations(arr, k) {
    function* doGenerateCombinations(offset, combo) {
      if (combo.length == k) {
        yield combo;
      } else {
        let len = arr.length;
        for (let i = offset; i < len; i++) {
          yield * doGenerateCombinations(i + 1, combo.concat(arr[i]));
        }
      }
    }

    yield* doGenerateCombinations(0, []);
  }

  // Given an array of arrays, generates all ways the elements can be combined together,
  // when taking a single element from each array.
  function* cartesianProductOf(arrays) {
    function* doCartesianProductOf(i, prod) {
      if (i == arrays.length) {
        yield prod;
      } else {
        for (let j = 0; j < arrays[i].length; j++) {
          yield* doCartesianProductOf(i + 1, prod.concat(arrays[i][j]));
        }
      }
    }

    yield* doCartesianProductOf(0, []);
  }
}

console.log(JSON.stringify(Array.from(removalCombinations([1, 2, 1, 3, 1, 4, 4], [1, 4, 4]))));
console.log(JSON.stringify(Array.from(removalCombinations([8, 6, 4, 4], [6, 4, 8]))));

Ответ 5

Я думаю, что ветвление и обрезка - это ортодоксальный способ решения этой проблемы и с большой возможностью оптимизации.
Но, если вы просто хотите простое и интуитивно понятное решение. Вот оно.

Сначала найдите числа, которые находятся в списке удаления.
[1,2,1,3,1,4,4] [1,4,4]
отсюда получаем [1,1,1,4,4]
Во-вторых, выберите так же, как элементы списка удаления с первого шага, который представляет собой комбинацию 5C3.
из этого получаем [1,1,1] [1,1,4] [1,4,4]....
В-третьих, сравните последовательность. тогда вы получите результат.
Вот код.. Извините, что он находится на С++, и я использовал простую библиотеку комбинаций.

#include<vector>
#include<algorithm>
#include<iostream>
#include"combi.h"
using namespace std;

int main()
{
    vector<int> list {1,2,1,3,1,4,4};
    vector<int> to_remove {1,4,4};
    vector<int> index;
    for(int i=0; i<list.size(); i++) {
        if(find(to_remove.begin(), to_remove.end(), list[i]) != to_remove.end())
            index.push_back(i);//insert index
    }
    bool sequence;
    nCr ncr(index.size(), to_remove.size());
    while(ncr.next()) {
        sequence = true;
        for(int i=0; i<ncr.size(); i++) 
            if(list[index[ncr[i]-1]] != to_remove[i]) sequence = false;
        if(sequence) {
            for(int i=0, j=0; i<list.size(); i++) {
                if(i == index[ncr[j]-1]) j++;
                else cout << list[i] << ' ';
            }
            cout << endl;
        }
    }
}

Вот библиотека комбинаций.

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
};

Combination::Combination(int n, int r)
{
    ar = new int[r];
    this->n = n;
    this->r = r;
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if(r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

bool nCr::next()
{
    if(r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

Ответ 6

Хорошее упражнение, как обычно, требуется 1 секунда для кода и 10 для ввода:-). Я не могу удовлетворить языковые ограничения, так как я использую еще не названный язык, поэтому я могу быть вне конкуренции. Но я брошу вызов всем, кто предоставил решение с проверкой правильности . Извините за пропуски запятых. Пожалуйста, проверьте эти аргументы:

[1 2 1 3 1 4 4] \ [1 4 4 1]

должны быть выполнены следующие решения:

(2 3 1)(2 1 3)(1 2 3) 

и

[1 2 1 3 1 4 4] \ [1 4 4 1 1]

должно вывести следующее решение:

(2 3)

и

[1 1 1 1 1] \ [1 1 1]

следует (imho) выработать следующее решение:

(1 1)

И

[1] \ [2]

следует (imho) выработать следующее решение:

[zero-length array]

И

[1 2 1 1 4 4 3 8 6 4 1 1 4 3 2 1] \ [1 1 4 1 1 1 3 4 8 6 2 2 4]

должны быть выполнены следующие решения:

(4 3 1)(3 4 1)(1 4 3)(3 1 4)(4 1 3)(1 3 4) 

РЕШЕНИЕ:

Это не самая простая вещь для реализации, хотя она довольно понятна логически. Я использую термин "sub-array", например:

(1 2 3)(4 5 6)(7 8 9 10) <- Array with 3 "sub-arrays", 3 "elements"

Шаг 1. Назначьте аргументы (следуя исходному примеру)

arg = 1,2,1,3,1,4,4   
vec = 1,4,4   

Шаг 2. Проверьте уникальность в vec и сколько их есть.

A = 1,4 // The uniques in vec
B = 1,2 // Occurances of them

Шаг 3. Создайте индексы в arg для каждого из A (1-origin):

C = (1 3 5)(6 7) // 1 appears at indexes 1,3,5 in arg, 4 appears at indexes 6,7

Шаг 4. Возьмите каждый элемент C каждого элемента из B раз:

D = (1 3 5)(6 7)(6 7) // B is (1,2) so we take (1 3 5) once and (6 7) twice.

Шаг 5: (сложный шаг) Создайте все комбинации элементов в D, используя внешнее соединение:

Это происходит, сначала создавая все комбинации из двух rightmost элементов, т.е. (6 7) и (6 7):

(6 6)(6 7)(7 6)(7 7) // (6 7) combined with (6 7) all possible ways

Затем объедините это с следующей D (в сторону слева):

E = (1 6 6)(1 6 7)(1 7 6)(1 7 7)(3 6 6)(3 6 7)(3 7 6)(3 7 7)(5 6 6)(5 6 7)(5 7 6)(5 7 7) // (1 3 5) combined with (6 6)(6 7)(7 6)(7 7) all possible ways

Если в D было больше элементов, мы бы взяли их один за другим (влево) и в сочетании с достигнутыми комбинациями до сих пор. Пока не будут выполнены все элементы D (где "element" является "подматрицей" ).

Шаг 6. Удалите из E такие элементы, которые содержат повторяющиеся числа "внутри" (например, элемент (1 6 6)):

F = (1 6 7)(1 7 6)(3 6 7)(3 7 6)(5 6 7)(5 7 6) // What is left from E

Шаг 7: удалить из F, когда под-массивы отсортированы внутри, такие элементы, которые дублируются:

(1 6 7)(1 6 7)(3 6 7)(3 6 7)(5 6 7)(5 6 7) // F with sub-arrays sorted internally
G = (1 6 7)(3 6 7)(5 6 7)                  // Duplicate sub-arrays removed

Шаг 8: почти готов! Теперь у нас есть "неиндексы" в arg - те индексы, которые должны быть исключены.

arg имеет 7 элементов, поэтому все индексы в нем (1,2,3,4,5,6,7).

Выбор первого элемента из G выше (1 6 7) означает, что первым ответом являются индексы (1 2 3 4 5 6 7) без (1 6 7). Все ответы/индексы:

(1 2 3 4 5 6 7) without (1 6 7) -> (2 3 4 5). arg[2 3 4 5] is (2 1 3 1)
(1 2 3 4 5 6 7) without (3 6 7) -> (1 2 4 5). arg[1 2 4 5] is (1 2 3 1)
(1 2 3 4 5 6 7) without (5 6 7) -> (1 2 3 4). arg[1 2 3 4] is (1 2 1 3)

Следовательно, ответы

(2 1 3 1)(1 2 3 1)(1 2 1 3) 

Шаг 9: (Необязательно) Ответ может содержать дубликаты на уровне элемента. Сохраняйте только уникальность.

Вы можете попробовать этот однослойный слот Dyalog APL на tryapl.org:

1 2 1 3 1 4 4 {↑∪{c[b~⍵]}¨{(∊⍵≡¨∪¨⍵)/⍵},⊃∘.,/(+/¨a=¨⊂⍵)/((a←∪⍵)=¨⊂⍺)/¨⊂b←⍳⍴c←⍺} 1 4 4

Вставьте и нажмите [enter], вы получите:

2 1 3 1
1 2 3 1
1 2 1 3

Вы не сможете протестировать самый длинный опробованный образец выше, так как он превышает доступное время обработки времени на сервере tryapl, но не стесняйтесь тестировать с более короткими аргументами.

Ответ 7

Вот решение, которое использует повторную функцию для уменьшения значений в шагах. Эта функция не вернет решения, если не все значения значений, которые необходимо удалить, присутствуют в стартовом массиве.

// Algorithm to strip values from an array
// Note, if not all elements of the stripValues array are found this function will return no solutions

function stripValues(startingValues, stripValues) {
    let solutions = []

    searchForSolutions(startingValues, stripValues, solutions, [])

    return solutions
}

function searchForSolutions(startingValues, stripValues, solvedSolutions, possibleSolution) {
    // If there are values to remove
    if(stripValues.length > 0) {
        // Copy the values of any possible solution to avoid tampering
        let newPossibleSolution = []
        possibleSolution.forEach((value) => {
            newPossibleSolution.push(value)
        })

        // Loop through the starting values looking for an instance of the first remaining value to strip
        for(i = 0; i < startingValues.length; i++) {
            if(startingValues[i] == stripValues[0]) {
                // The value was found, so reduce the arrays and look for the next element to remove
                let remainingStripValues = []
                stripValues.forEach((value, index) => {
                    if(index > 0) {
                        remainingStripValues.push(value)
                    }
                })

                let remainingValues = []
                for(j = i + 1; j< startingValues.length; j++) {
                    remainingValues.push(startingValues[j])
                }

                // Reiterate the search
                searchForSolutions(remainingValues, remainingStripValues, solvedSolutions, newPossibleSolution)
            }

            // Whether or not the value was found we want to continue finding permutations 
            newPossibleSolution.push(startingValues[i])
        }
    } else {
        //There are no remaining values to search for, so we have found a solution
        for(i = 0; i < startingValues.length; i++) {
            newPossibleSolution.push(startingValues[i]);
        }

        solvedSolutions.push(newPossibleSolution)
    }
}

Ответ 8

(Этот ответ также доступен здесь: Как я могу определить все возможные способы удаления подпоследовательности из последовательности?)

Это ответ для упорядоченных комбинаций с множеством множеств, которые кажутся похожими на перечисление соответствующих подпоследовательностей в большем массиве.

Сначала закажите свой набор для удаления в том же порядке внешнего вида, что и в основном массиве (O(n) time with hash), а затем выполните приведенный ниже алгоритм.

Эта проблема может быть решена в O(n*m + r) времени, где r - общая длина результатов, используя классическую самую длинную общую подпоследовательность.

Как только таблица сделана, как в Wikipedia пример, замените ее на список ячеек с диагональной стрелкой, которые также имеют значение, соответствующее их строке. Теперь пройдите назад от каждой ячейки с диагональю в последней строке, аккумулируя соответствующий индекс в строке и дублируя и разбивая накопление таким образом, чтобы каждая ячейка с диагональной стрелкой имела продолжение для всех ячеек с диагональю в предыдущей строке, которая находятся слева от него (сохраните это количество, а также, когда вы построите матрицу), и один меньше по стоимости. Когда накопление достигает нулевой ячейки, сплайсируйте накопленные индексы из строки и добавьте это в результате.

(Стрелки соответствуют тому, что LCS до сих пор произошло от LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]), см. функцию определение.)

Например:

  0  a  g  b  a  b  c  c
0 0  0  0  0  0  0  0  0
a 0 ↖1  1  1 ↖1  1  1  1
b 0  1  1 ↖2  2 ↖2  2  2
c 0  1  1  2  2  2 ↖3 ↖3

Код JavaScript:

function remove(arr,sub){
  var _arr = [];
  arr.forEach(function(v,i){ if (!sub.has(i)) _arr.push(arr[i]); });
  return _arr;
}

function f(arr,sub){
  var res = [],
      lcs = new Array(sub.length + 1),
      nodes = new Array(sub.length + 1);
     
  for (var i=0; i<sub.length+1;i++){
    nodes[i] = [];
    lcs[i] = [];
   
    for (var j=0; j<(i==0?arr.length+1:1); j++){
      // store lcs and node count on the left
      lcs[i][j] = [0,0];
    }
  }
 
  for (var i=1; i<sub.length+1;i++){ 
    for (var j=1; j<arr.length+1; j++){
      if (sub[i-1] == arr[j-1]){
        lcs[i][j] = [1 + lcs[i-1][j-1][0],lcs[i][j-1][1]];
       
        if (lcs[i][j][0] == i){
                  // [arr index, left node count above]
          nodes[i].push([j - 1,lcs[i-1][j-1][1]]);
       
          lcs[i][j][1] += 1;
        }
       
      } else {
        lcs[i][j] = [Math.max(lcs[i-1][j][0],lcs[i][j-1][0]),lcs[i][j-1][1]];
      }
    }
  }
   
  function enumerate(node,i,accum){
    if (i == 0){
      res.push(remove(arr,new Set(accum)));
      return;
    }
    
    for (var j=0; j<node[1]; j++){
      var _accum = accum.slice();
      _accum.push(nodes[i][j][0]);
      
      enumerate(nodes[i][j],i - 1,_accum);
    }
  }
  
  nodes[sub.length].forEach(function(v,i){ 
    enumerate(nodes[sub.length][i],sub.length - 1,[nodes[sub.length][i][0]]); 
  });

  return res;
}

console.log(JSON.stringify(f([1,2,1,3,1,4,4], [1,4,4])));
console.log(JSON.stringify(f([8,6,4,4], [6,4,8])));
console.log(JSON.stringify(f([1,1,2], [1])));
console.log(JSON.stringify(f(['a','g','b','a','b','c','c'], ['a','b','c'])));

Ответ 9

Если вы хотите перечислить неупорядоченные комбинации множества наборов элементов, вы можете сделать именно это:

Записать позиции в массиве элементов в мультисети; перечислите все комбинации choose(indexes,multiplicity).

Код JavaScript:

// straighforward choose(n,r) combinations
function choose(ns,r){
  if (r > ns.length) return [];
    
  var res = [];

  function _choose(i,_res){
    if (_res.length == r){
      res.push(_res);
      return;

    } else if (_res.length + ns.length - i == r){
      _res = _res.concat(ns.slice(i));
      res.push(_res);
      return
    }

    var temp = _res.slice();
    temp.push(ns[i]);

    _choose(i + 1,temp);
    _choose(i + 1,_res);
  }

  _choose(0,[]);
  return res;
}

// function to collect an array without specified indexes
function remove(arr,indexSet){
  var _arr = [];
  arr.forEach(function(v,i){ if (!indexSet.has(i)) _arr.push(arr[i]); });
  return _arr;
}

// main function
// the multiset is formatted as {element: [multiplicity,indexes]}
function removeAllCombs(arr,multiset){
  var res = [];
  
  // record the positions of multiset elements in the array
  arr.forEach(function(v,i){
    if (multiset[v]) multiset[v][1].push(i);
  });
  
  var keys = Object.keys(multiset);
  
  function enumerate(i,accum){
    if (i == keys.length){
      res.push(remove(arr,new Set(accum)));
      return;
    }
    
    var combs = choose(multiset[keys[i]][1],multiset[keys[i]][0]);

    for (let j in combs){
      var _accum = accum.slice();
      _accum = _accum.concat(combs[j]);
      
      enumerate(i + 1,_accum);
    }
  }
  
  enumerate(0,[]);
  return res;
}

console.log(JSON.stringify(
  removeAllCombs([1,2,1,3,1,4,4],{1: [1,[]], 4: [2,[]]})
));

Ответ 10

В основном это предложение создает карту с нужными элементами для удаления, подсчитывает их, проверяет, совпадает ли длина этих элементов с данными, а затем помещает их в массив common. Все остальные используются для создания комбинации, а затем для создания перекрестного продукта.

В конце все значения, найденные в перекрестном продукте или в общем, отфильтровываются.

function remove(sequence, sub) {
    var count = new Map,
        distribute = [],
        common = [];

    sub.forEach((a, i) => {
        var o = count.get(a)
        if (!o) {
            o = { sub: 0, pos: [] };
            count.set(a, o);
        }
        o.sub++;
    });

    sequence.forEach((a, i) => {
        var o = count.get(a);
        o && o.pos.push(i);
    });

    count.forEach((v, k) => {
        if (v.pos.length > v.sub) {
            distribute.push({ value: k, pos: v.pos, count: v.sub });
        } else {
            common.push(k);
        }
    });

    return crossProduct(distribute.map(a => combination(a.pos, a.count))).
        map(a =>
            sequence.filter((b, i) => a.indexOf(i) === -1 && common.indexOf(b) === -1));
}

console.log(remove([1, 2, 1, 3, 1, 4, 4], [1, 4, 4])); // [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]
console.log(remove([1, 2, 1, 3, 1, 4, 4], [1, 1]));    // [ [2,3,1,4,4], [1,2,3,4,4], [2,1,3,4,4] ]
console.log(remove([1, 2, , 5, 1, 3, 5, 1, 4, 4, 5], [1, 4, 4, 5]));

function crossProduct(array) {
    function c(part, index) {
        array[index].forEach(a => {
            var p = part.concat(a);
            if (p.length === array.length) {
                result.push(p);
                return;
            }
            c(p, index + 1);
        });
    }

    var result = [];
    if (array.length === 1) { return array[0]; }
    c([], 0);
    return result;
}

function combination(array, size) {

    function c(part, start) {
        var i, l, p;
        for (i = start, l = array.length + part.length + 1 - size; i < l; i++) {
            p = part.slice();
            p.push(array[i]);
            p.length < size ? c(p, i + 1) : result.push(p);
        }
    }

    var result = [];
    c([], 0);
    return result;
}

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