用于确定可以从序列中移除一组值的所有可能方式的算法

Question

我试图确定有多少种不同的方法可以从序列中删除一组值,保留原始序列的顺序(稳定),并确保从原始序列中只删除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代码我写的所有数组值的组合没有删除和删除部分似乎应该很容易但我没有看到算法需要多次可能删除多个值.

Answer 1

(因为它是在这个问题你是否打算删除子或无序列表的原始版本不清楚,我已经更新了我的答案来解决这两种情况下.)

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

代码执行以下步骤:

• 创建sub中存在的每个值的实例位置的关联数组:

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

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

从位置列表中删除交叉连接,并在生成组合时避免交叉连接,只需对相同的值进行.

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

Answer 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

这将为您提供线性时间解决方案(假设您可以在执行一些预处理以缓存因子值后,在恒定时间内计算选择(.,.).

在您的示例中,您有:

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

Answer 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.

Answer 4

要确定needles可以从序列(被调用haystack)中删除一组值(让我们调用此组)的所有方法,请执行以下操作:

1. 计算每次删除的次数needle(让我们称之为计数k).这可以通过一次通过确定needles.
2. 找到needle要删除的每个位置haystack.这可以通过一次通过确定haystack.
3. 生成所有可能的方法,您可以needle k从找到的位置删除每个单独的时间.这是k- combinations的标准枚举,其时间复杂度是非多项式的.
4. 生成所有可能的方法,您可以将每个人needle的移除可能性结合在一起.这是标准的n倍笛卡尔积,其时间复杂度也是非多项式.
5. 对于找到的每种方式,过滤掉相关的元素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]))));