Comment puis-je déterminer toutes les façons possibles d'une sous-suite peut être retiré à partir d'une séquence?

Question

Étant donné deux séquences A et B, comment puis-je générer une liste de toutes les manières possibles que B peut être retiré à partir d' Un?

Par exemple, En JavaScript, si j'avais une fonction removeSubSeq prend deux arguments de type tableau qui fait ce que je veux, il travail comme suit:

removeSubSeq([1,2,1,3,1,4,4], [1,4,4]) reviendrait [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ] parce que le 4s à la fin du match, et il y a trois endroits possibles pour la 1 pour correspondre à

removeSubSeq([8,6,4,4], [6,4,8]) reviendrait [] parce que le deuxième argument n'est pas réellement une sous-suite

removeSubSeq([1,1,2], [1]) reviendrait [ [1,2], [1,2] ] car il y a deux façons de le 1 peut être retiré, même si elle entraîne des doublons

Answer 1

Ce problème peut être résolu en O(n*m + r) du temps, où l' r est la longueur totale des résultats, à l'aide de la classique de la plus longue sous-suite commune de l'algorithme.

Une fois que la table est faite, comme dans Wikipédia exemple, la remplacer par une liste de cellules avec une flèche diagonale qui ont aussi une valeur correspondant à leur rang. Maintenant parcourir à rebours à partir de chaque cellule avec une diagonale dans la dernière ligne, l'accumulation de l'indice pertinent dans la chaîne et de la duplication et le fractionnement de l'accumulation, de sorte que chaque cellule avec une flèche diagonale aura une suite à toutes les cellules avec une diagonale de la ligne précédente qui sont à la gauche de celui-ci (le magasin de comptage ainsi, à mesure que vous construisez la matrice) et une moins-value. Quand une accumulation atteint un zéro de la cellule, splice le cumul des indices à partir de la chaîne et d'ajouter qu'en tant que résultat.

(Les flèches correspondent à savoir si le LCS jusqu'à présent venu de LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]), voir la fonction de définition.)

Par exemple:

  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

Le code 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'])));

Answer 2

Vous pouvez utiliser la récursivité. Construire une nouvelle sous-suite C en se promenant dans Un et de pousser des éléments dans l'ordre. Chaque fois que vous rencontrez un élément qui correspond à la tête de B, vous aurez la fourche de la récursion dans les deux chemins: l'un dans lequel vous retirer (c'est à dire ignorer) l'élément de A et B, et un autre dans lequel vous ignorer et continuer comme d'habitude.

Si vous avez épuisé toutes de B (ce qui signifie que vous avez supprimé tous les éléments de B à partir de A), puis en ajoutant le reste de A à C, va produire un valide sous-suite. Sinon, si vous atteignez la fin d'Un sans l'épuiser tous B, C n'est pas une sous-suite et doit être jeté.

function removeSubSeq(a, b) {
    function* remove(i, j, c) {
        if (j >= b.length) {
            yield c.concat(a.slice(i));
        } else if (i >= a.length) {
            return;
        } else if (a[i] === b[j]) {
            yield* remove(i + 1, j + 1, c);
            yield* remove(i + 1, j, c.concat(a.slice(i, i + 1)));
        } else {
            yield* remove(i + 1, j, c.concat(a.slice(i, i + 1)));
        }
    }

    if (a.length < b.length) {
        return [];   
    }

    return Array.from(remove(0, 0, []));
}

L'intérieure de la fonction d'aide peut être rendu légèrement plus efficace par le remplacement de l'utilisation de Array.concat dans chaque récursive de la direction, avec un simple push()/pop() de la paire, bien qu', ce qui rend le flux de contrôle un peu plus difficile à analyser.

function* remove(i, j, c) {
    if (j >= b.length) {
        yield c.concat(a.slice(i));
    } else if (i >= a.length) {
        return;
    } else {
        if (a[i] === b[j]) {
            yield* remove(i + 1, j + 1, c);
        }

        c.push(a[i]);
        yield* remove(i + 1, j, c);
        c.pop();
    }
}

Answer 3

Ce problème peut être résolu à l'aide du bottom-up Dynamique de l'approche de la Programmation avec des retours en arrière.

Considérons une relation de récurrence f(i1, i2), ce qui permet de vérifier si la queue de la séquence de arr2 peut être supprimé de la queue de la séquence de arr1:

f(i1, i2) = true, if(i1 == length(arr1) AND i2 == length(arr2))
f(i1, i2) = f(i1 + 1, i2) OR f(i1 + 1, i2 + 1), if(arr1[i1] == arr2[i2])
f(i1, i2) = f(i1 + 1, i2), if(arr1[i1] != arr2[i2])

solution  = f(0, 0)

J'utilise le terme de queue pour désigner la sous-suite d' arr1 qui commence à l'indice i1 et s'étend jusqu'à la fin de l' arr1 (et de même pour arr2 - queue de arr2 commence à l'indice i2 et s'étend jusqu'à la fin de l' arr2).

Commençons avec top-down de la mise en œuvre de la relation de récurrence (encore sans memoization, afin de conserver la explication simple). Ci-dessous l'extrait de code Java, qui imprime tous les possible de sous-séquences d' arr1 , après le retrait de arr2:

void remove(int[] arr1, int[] arr2) {
    boolean canBeRemoved = remove(arr1, arr2, 0, 0, new Stack<>());
    System.out.println(canBeRemoved);
}

boolean remove(int[] arr1, int[] arr2, int i1, int i2, Stack<Integer> stack) {

    if (i1 == arr1.length) {
        if (i2 == arr2.length) {
            // print yet another version of arr1, after removal of arr2
            System.out.println(stack);
            return true;
        }
        return false;
    }

    boolean canBeRemoved = false;
    if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) {
        // current item can be removed
        canBeRemoved |= remove(arr1, arr2, i1 + 1, i2 + 1, stack);
    }

    stack.push(arr1[i1]);
    canBeRemoved |= remove(arr1, arr2, i1 + 1, i2, stack);
    stack.pop();

    return canBeRemoved;
}

Th fourni extrait de code n'utilise pas de memoization technique, et a l'exponentielle d'exécution de la complexité pour toutes les instances d'un problème donné.

Cependant, nous pouvons voir que la variable i1 ne peut avoir la valeur de l'intervalle [0..length(arr1)], aussi la variable i2 ne peut avoir la valeur de l'intervalle [0..length(arr2)].

Par conséquent, il est possible de vérifier, si arr2 peut être retiré de l' arr1 avec le polynôme d'exécution de la complexité: O(length(arr1) * length(arr2)).

D'autre part, même si l'on retrouve avec un polynôme d'exécution de la complexité qu' arr2 peut être retiré de l' arr1 - il y a encore peut-être une exponentielle de la quantité de façons d'enlever arr2 de arr1.

Par exemple, prenons l'exemple du problème: lorsqu'il est nécessaire de supprimer arr2 = [1,1,1] de arr1 = [1,1,1,1,1,1,1]. Il y a 7!/(3! * 4!) = 35 façons de le faire.

Néanmoins, ci-dessous est le bottom-up de la Programmation Dynamique la solution avec le recul, ce qui est tout de même pour de nombreux cas de problème aura une meilleure exécution de la complexité de l'exponentielle:

void remove_bottom_up(int[] arr1, int[] arr2) {
    boolean[][] memoized = calculate_memoization_table(arr1, arr2);
    backtrack(arr1, arr2, 0, 0, memoized, new Stack<>());
}

/**
 * Has a polynomial runtime complexity: O(length(arr1) * length(arr2))
 */
boolean[][] calculate_memoization_table(int[] arr1, int[] arr2) {

    boolean[][] memoized = new boolean[arr1.length + 1][arr2.length + 1];
    memoized[arr1.length][arr2.length] = true;

    for (int i1 = arr1.length - 1; i1 >= 0; i1--) {
        for (int i2 = arr2.length; i2 >= 0; i2--) {

            if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) {
                memoized[i1][i2] = memoized[i1 + 1][i2 + 1];
            }
            memoized[i1][i2] |= memoized[i1 + 1][i2];
        }
    }
    return memoized;
}

/**
 * Might have exponential runtime complexity.
 *
 * E.g. consider the instance of the problem, when it is needed to remove
 * arr2 = [1,1,1] from arr1 = [1,1,1,1,1,1,1].
 *
 * There are 7!/(3! * 4!) = 35 ways to do it.
 */
void backtrack(int[] arr1, int[] arr2, int i1, int i2, boolean[][] memoized, Stack<Integer> stack) {

    if (!memoized[i1][i2]) {
        // arr2 can't be removed from arr1
        return;
    }

    if (i1 == arr1.length) {
        // at this point, instead of printing the variant of arr1 after removing of arr2
        // we can just collect this variant into some other container
        // e.g. allVariants.add(stack.clone())
        System.out.println(stack);
        return;
    }

    if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) {
        backtrack(arr1, arr2, i1 + 1, i2 + 1, memoized, stack);
    }

    stack.push(arr1[i1]);
    backtrack(arr1, arr2, i1 + 1, i2, memoized, stack);
    stack.pop();
}

JavaScript mise en Œuvre de la solution décrite

function remove_bottom_up(base_arr, removed_arr) {

    // Initialize memoization table
    var memoized = new Array(base_arr.length + 1);
    for (var i = 0; i < base_arr.length + 1; i++) {
        memoized[i] = new Array(removed_arr.length + 1);
    }
    memoized[base_arr.length][removed_arr.length] = true;

    // Calculate memoization table 
    for (var i1 = base_arr.length - 1; i1 >= 0; i1--) {
        for (var i2 = removed_arr.length; i2 >= 0; i2--) {
            if ((i2 < removed_arr.length) && (base_arr[i1] == removed_arr[i2])) {
                memoized[i1][i2] = memoized[i1 + 1][i2 + 1];
            }
            memoized[i1][i2] |= memoized[i1 + 1][i2];
        }
    }

    // Collect all variants
    var all_variants = [];
    backtrack(base_arr, removed_arr, 0, 0, memoized, [], all_variants);
    return all_variants;
}

function backtrack(base_arr, removed_arr, i1, i2, memoized, stack, all_variants) {

    if (!memoized[i1][i2]) {
        // arr2 can't be removed from arr1
        return;
    }

    if (i1 == base_arr.length) {
        all_variants.push(stack.slice(0));
        return;
    }

    if ((i2 < removed_arr.length) && (base_arr[i1] == removed_arr[i2])) {
        backtrack(base_arr, removed_arr, i1 + 1, i2 + 1, memoized, stack, all_variants);
    }

    stack.push(base_arr[i1]);
    backtrack(base_arr, removed_arr, i1 + 1, i2, memoized, stack, all_variants);
    stack.pop();
}

console.log(JSON.stringify(remove_bottom_up([1, 2, 1, 3, 1, 4, 4], [1, 4, 4])));
console.log(JSON.stringify(remove_bottom_up([8, 6, 4, 4], [6, 4, 8])));
console.log(JSON.stringify(remove_bottom_up([1, 1, 2], [1])));
console.log(JSON.stringify(remove_bottom_up([1, 1, 1, 1, 1, 1, 1], [1, 1, 1])));

Answer 4

L'algorithme:

1. De manière récursive créer une arborescence de nœuds, en commençant par le premier élément de B. de Chaque nœud de la valeur est l'indice de la sous-suite article correspondant à son niveau et à ses descendants sont les indices de l'élément suivant-donc pour [1,2,1,3,1,4,4], [1,4,4] l'arbre serait [ [ 0, [5, [6]], [6] ], [ 2, [5, [6]], [6] ], [ 4, [5, [6]], [6] ].
2. Pied de cet arbre et de construire des séquences d'éléments à supprimer, c'est à dire trouver tous les chemins dans l'arbre qui sont aussi longues que le sous-suite. Cette liste comporterait comme [ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ].
3. Pour chaque liste, ainsi développé, ajouter à la liste de résultats à partir des éléments à ces indices étant supprimés: [ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ].

Le code pour faire cela, qui correspond à tous vos cas de test:

---

#!/usr/bin/env node

var _findSubSeqs = function(outer, inner, current) {

    var results = [];
    for (var oi = current; oi < outer.length; oi++) {
        if (outer[oi] == inner[0]) {
            var node = {
                value: oi,
                children: _findSubSeqs(outer, inner.slice(1), oi+1)
            };
            results.push(node);
            }
    }
    return results;
}

var findSubSeqs = function(outer, inner) {
    var results = _findSubSeqs(outer, inner, 0);
    return walkTree(results).filter(function(a) {return (a.length == inner.length)});
}

var _walkTree = function(node) {
    var results = [];
    if (node.children.length) {
        for (var n = 0; n < node.children.length; n++) {
            var res = _walkTree(node.children[n])
            for (r of res) {
                results.push([node.value].concat(r))
            }
        }
    } else {
        return [[node.value]]
    }
    return results
}

var walkTree = function(nds) {
    var results = [];
    for (var i = 0; i < nds.length; i++) {
        results = results.concat(_walkTree(nds[i]))
    }
    return results
}

var removeSubSeq = function(outer, inner) {
    var res = findSubSeqs(outer, inner);
    var subs = [];
    for (r of res) {
        var s = [];
        var k = 0;
        for (var i = 0; i < outer.length; i++) {
            if (i == r[k]) {
                k++;
            } else {
                s.push(outer[i]);
            }
        }
        subs.push(s);
    }
    return subs
}

console.log(removeSubSeq([1,2,1,3,1,4,4], [1,4,4]))
console.log(removeSubSeq([8,6,4,4], [6,4,8]) )
console.log(removeSubSeq([1,1,2], [1]))

Answer 5

Je souhaite tout d'abord utiliser des chaînes de caractères. Il est plus facile à manipuler:

var results = [];

function permute(arr) {
    var cur, memo = [];

    for (var i = 0; i < arr.length; i++) {
        cur = arr.splice(i, 1);
        if (arr.length === 0) {
            results.push(memo.concat(cur));
        }
        permute(arr.slice(), memo.concat(cur));
        arr.splice(i, 0, cur[0]);
    }
    return results;
}

function removeSub(arr, sub) {
    strArray = arr.join(' ');
    if(strArray.includes(sub)){
        return strArray.replace(sub.join(' ')).split(' ');
    }
    return [];
}

function removeSubSeq(arr, sub) {
    return permute(removeSub(arr, sub));
}

Je n'ai pas commenté le code, mais n'hésitez pas à demander des éclaircissements. Ce n'est pas testé, mais l'idée est en elle...