javascript - 确定从序列中删除一组值的所有可能方法的算法

Question

我正在尝试确定可以从序列中删除一组值，按顺序(稳定)保留原始序列的方式，并确保从原始序列中仅删除一个实例值。例如，如果我有[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代码可生成所有数组值的组合而无需删除，而删除部分似乎应该很容易，但是当需要多次删除多个值时，我看不到算法。

Answer 1

(由于在问题的原始版本中不清楚是要删除子序列还是要删除无序列表，因此我更新了答案以解决这两种情况。)

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]}  

创建一个2D数组，该数组将子序列中的位置链接到序列中的位置:

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.删除值的无序列表

如果要删除的值列表不一定是主序列的子序列，并且可以按任何顺序删除值，则可以使用与上述相同的方法，并放宽交叉连接规则:

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

在此示例中，仅删除了重复值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>");