我正在尝试确定可以从序列中删除一组值，按顺序(稳定)保留原始序列的方式，并确保从原始序列中仅删除一个实例值。例如，如果我有[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的最左边的连接时，将删除值2右边的两个连接(用红色表示)，因为它们交叉了此连接:



在下一步中，我们从右到左，对于每个值，我们查看其最右边的连接，并从其左侧的值中删除符合或交叉该连接的所有连接；例如在考虑右侧值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]]

Removing crossed connections from the position list, and avoiding crossed connections when generating the combinations, only has to be done for identical values.

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

关于javascript - 确定从序列中删除一组值的所有可能方法的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38923072/