我试图确定有多少种不同的方法可以从序列中删除一组值，使原始序列保持有序（稳定），并确保从原始序列中仅删除一个实例值。例如，如果我有
[1,2,1,3,1,4,4]并且我想删除[1,4,4]我的结果组合将是：
[1,2,1,3,1,4,4] \ [1,4,4] = [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]
或者
[1,2,1,3,1,4,4] \ [1,1] = [ [2,3,1,4,4], [1,2,3,4,4], [2,1,3,4,4] ]
我编写了 javascript 代码来生成所有数组值的组合而无需删除，删除部分似乎应该很容易，但是当需要多次删除多个值时我没有看到算法。
（因为在问题的原始版本中不清楚您是要删除子序列还是无序列表，所以我更新了我的答案以解决这两种情况。）
1.按顺序删除一个子序列
我们得到一个值序列，例如[1,5,1,3,4,2,3,2,1,3,1,2]，以及要从第一个序列中删除的值的子序列，例如[1,3,2,1]。如果我们找到值的每个实例在序列中的位置，我们会得到如下图：
找到可以按顺序从序列中删除值的所有方式，然后意味着找到可以将底部行中的待删除值连接到序列中的实例的所有方式，而没有任何线交叉，例如：
为了避免以不会导致有效解决方案的方式删除值（例如，从删除最右边的值 1 开始，之后没有可以删除的值 3），我们将首先删除图中的所有连接导致这种无效的解决方案。
这将通过对子序列进行两次迭代来完成。首先，我们从左到右执行此操作，对于每个值，我们查看其最左侧的连接，并从其右侧的值中删除任何与该连接相交或交叉的连接；例如，当考虑值 2 的最左侧连接时，其右侧的值 1 的两个连接（以红色表示）被删除，因为它们穿过此连接：
在下一步中，我们从右到左，对于每个值，我们查看其最右侧的连接，并从其左侧的值中删除任何与该连接相遇或交叉的连接；例如，当考虑从右边的值 1 开始的最右边的连接时，从左边的值 2 开始的最右边的连接（用红色表示）被删除，因为它穿过了这个连接：
然后我们最终得到如下所示的简化图。然后通过组合子序列中每个值的每个连接实例来进行组合，使用例如递归：您迭代子序列中第一个值的选项，并且每次递归子序列的其余部分，以便第一个值的选项与其他值的所有选项相结合。
简化图中可以存在交叉连接，但这些不再是问题。在示例中，您将看到即使为值 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>");代码执行以下步骤：
posi[1] = [0,2,8,10], posi[2] = [5,7,11], posi[3] = [3,6,9]}
conn = [[0,2,8,10],[3,6,9],[5,7,11],[0,2,8,10]]
conn = [[0,2,8,10],[3,6,9],[5,7,11],[8,10]]
conn = [[0,2],[3,6],[5,7],[8,10]]
combinations = [[0,3,5,8],[0,3,5,10],[0,3,7,8],[0,3,7,10],
[0,6,7,8],[0,6,7,10],[2,3,5,8],[2,3,5,10],
[2,3,7,8],[2,3,7,10],[2,6,7,8],[2,6,7,10]]
2. 移除一个无序列的值列表
如果要删除的值列表不一定是主序列的子序列，并且可以以任意顺序删除值，则可以使用与上述相同的方法，但放宽交叉连接规则：
从位置列表中删除交叉连接，并在生成组合时避免交叉连接，只需要对相同的值进行。
在此示例中，仅删除了重复值 1 的交叉连接；第一个从左到右：
然后从右到左：
生成此简化图，删除了值 1 的有问题的交叉连接，并保留了值 2 和 3 的交叉连接：
以下是改编自子序列版本的代码示例；如注释所示，仅更改了代码中的几行（我还使用了不同的方法从序列中删除了值）。要删除的值列表在开始时进行排序，以便将相同的值组合在一起，以便于跟踪相同的值。
function removeSubList(seq, sub) {
sub.sort(function(a, b) {return a - b}); /* SORT SUB-LIST FIRST */
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++) {
if (sub[i - 1] != sub[i]) continue; /* SKIP FOR NON-IDENTICAL VALUES */
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--) {
if (sub[i] != sub[i + 1]) continue; /* SKIP FOR NON-IDENTICAL VALUES */
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++) {
var s = seq.slice(); // create copy of seq and delete values
combinations[i].forEach(function(elem) {delete s[elem]});
result[i] = s.filter(function(elem) {return elem != undefined});
}
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 && seq[prev] == seq[curr]) continue; /* SKIP FOR NIV */
if (step + 1 == conn.length) combinations.push(comb.concat([curr]));
else combine(step + 1, curr, comb.concat([curr]));
}
}
}
var result = removeSubList([1,5,1,3,4,2,3,2,1,3,1,2], [1,3,1,2,1]);
for (var i in result) document.write(result[i] + "<br>");这可以通过简单的组合来完成。
为简单起见，假设原始列表中的值为1,2,3,...,n.
设为原始列表中
a[i]出现的次数。让是值删除列表中的出现次数ib[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
这为您提供了线性时间解决方案（假设您可以在进行一些预处理以缓存阶乘值之后在恒定时间内计算 Choose(.,.)。
在您的示例中，您有：
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
（对于有序和无序的多集组合，另请参阅下面我的另外两个答案。）
为了避免递归中的“死胡同”，请从散列索引创建组合。例如，
[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.
needles要确定可以从序列（称为）中删除一组值（我们称之为 group ）的所有方式，haystack请执行以下操作：
needle的次数（我们称之为 count k）。这可以通过单次遍历来确定needles。needle在 中查找要删除的每个位置的所有位置haystack。这可以通过单次遍历来确定haystack。needle k的时间。这是k组合的标准枚举，其时间复杂度是非多项式的。needle的移除可能性组合在一起。这是一个标准的n倍笛卡尔积，它的时间复杂度也是非多项式的。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]))));我认为 Branching and Pruning 是解决这个问题的正统方法，并且具有很大的优化可能性。
但是，如果您只想要一个简单直观的解决方案。这里是。
首先，找到删除列表中的数字。
[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] ....
第三，比较序列。然后，你得到结果。
这是代码..对不起，它是在 C++ 中，我使用了一个简单的组合库。
#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;
}
这是一个使用重复函数逐步减少值的解决方案。如果不是所有需要删除的值都存在于起始数组中，则此函数将不会返回解决方案。
// 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)
}
}
很好的练习，像往常一样，编码需要 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]
应该（恕我直言）产生以下解决方案：
(1 1)
和
[1] \ [2]
应该（恕我直言）产生以下解决方案：
[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)
解决方案：
这不会是最简单的实现，尽管它在逻辑上很清楚。我正在使用术语“子数组”，如下所示：
(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 步：为每个 A（1-origin）在 arg 中建立索引：
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 中创建所有元素组合：
这是通过首先创建两个最右边元素的所有组合来实现的，即。(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 的所有元素都完成（其中“元素”是“子数组”）。
第 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 6 7) 的索引 (1 2 3 4 5 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 步：（可选）答案可能包含元素级别的重复项。只保留唯一的。
您可以在tryapl.org试用此 Dyalog APL单线：
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 服务器的可用处理时间分配，但可以随意使用任何较短的参数进行测试。
（此答案也可在此处获得：如何确定可以从序列中删除子序列的所有可能方式？）
这是有序多集组合的答案，这似乎类似于枚举更大数组中的匹配子序列。
首先，按照与主数组中相同的出现顺序（O(n)带散列的时间）排列要删除的集合，然后继续执行以下算法。
这个问题可以及时解决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'])));如果您想枚举多组元素的无序组合，您可以这样做：
记录多集中元素在数组中的位置；枚举所有的组合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,[]]})
));基本上，这个提议构建了一个带有要删除的想要项目的映射，对它们进行计数，检查相同项目的长度是否与给定的相同，然后将其放入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; }