我正试图确定从序列中删除一组值的不同方式，使原始序列保持有序（稳定），并确保仅从原始序列中每个实例值中删除1个。例如，如果我有[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,5,1,3,4,2,3,2,1,3,1,2]，还有一个要从第一组序列中删除的值的子序列，例如[1,3,2,1]。 如果我们找到每个值实例在序列中所处的位置，则可以得到以下图表:
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的交叉连接；首先从左到右：
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>");first和last索引/指针而不是每次更改数组。 - m69 ''snarky and unwelcoming''1,2,3,...,n。
a[i]是原始列表中 i 出现的次数。
b[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，并且对于所有x，Choose(x,0) = 1
这将为您留下线性时间解决方案（假设您可以在进行一些预处理以缓存阶乘值后，在恒定时间内计算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.
haystack）中删除一组值（我们将这组值称为needles），请执行以下操作：
needle的次数（我们将其称为计数k）。这可以通过对needles进行单次遍历来确定。haystack中需要移除的每个needle的所有位置。这可以通过对haystack进行单次遍历来确定。needlek次。这是一个标准的k组合枚举，其时间复杂度是非多项式的。needle的去除可能性组合在一起。这是一个标准的n重笛卡尔积，其时间复杂度也是非多项式的。haystack中过滤出相关元素。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]))));我认为分支和修剪是解决这个问题的正统方法，也有很多优化的可能性。
但是，如果你只想要一个简单直观的解决方案。这里就是。
首先，找到在删除列表中的数字。
[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;
}
[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"
arg = 1,2,1,3,1,4,4
vec = 1,4,4
A = 1,4 // The uniques in vec
B = 1,2 // Occurances of them
C = (1 3 5)(6 7) // 1 appears at indexes 1,3,5 in arg, 4 appears at indexes 6,7
D = (1 3 5)(6 7)(6 7) // B is (1,2) so we take (1 3 5) once and (6 7) twice.
(6 6)(6 7)(7 6)(7 7) // (6 7) combined with (6 7) all possible ways
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
F = (1 6 7)(1 7 6)(3 6 7)(3 7 6)(5 6 7)(5 7 6) // What is left from E
(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
(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)
1 2 1 3 1 4 4 {↑∪{c[b~⍵]}¨{(∊⍵≡¨∪¨⍵)/⍵},⊃∘.,/(+/¨a=¨⊂⍵)/((a←∪⍵)=¨⊂⍺)/¨⊂b←⍳⍴c←⍺} 1 4 4
2 1 3 1
1 2 3 1
1 2 1 3
以下是一种解决方案，它使用迭代函数逐步减少值。如果需要删除的所有值在起始数组中不存在，则此函数将不返回解决方案。
// 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)
}
}
（此答案也可以在这里找到：如何确定从序列中删除子序列的所有可能方式？）
这是关于有序多集组合的答案，似乎类似于枚举较大数组中匹配子序列。
首先，以与主数组中出现顺序相同的顺序对要删除的集进行排序（使用哈希的O(n)时间），然后按照下面的算法继续。
使用经典的最长公共子序列算法，可以在O(n*m + r)时间内解决此问题，其中r是结果的总长度。
（箭头对应于 LCS 到目前为止是否来自LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1])，请参见函数definition。）
例如：
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)的组合。// 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; }