(Comme il n'était pas clair dans la version originale de la question si vous vouliez supprimer une sous-séquence ou une liste non ordonnée, j'ai mis à jour ma réponse pour traiter les deux cas).
1. Suppression d'une sous-séquence dans l'ordre
Nous obtenons une séquence de valeurs, par exemple [1,5,1,3,4,2,3,2,1,3,1,2] et d'une sous-séquence de valeurs à supprimer de la première séquence, par ex. [1,3,2,1] . Si nous trouvons où chaque instance des valeurs se situe dans la séquence, nous obtenons un graphique comme celui-ci :
![all connections]()
Trouver toutes les façons dont les valeurs peuvent être retirées de la séquence, dans l'ordre, signifie alors trouver toutes les façons dont les valeurs à retirer de la ligne inférieure peuvent être reliées à une instance de la séquence, sans qu'aucune ligne ne se croise, par exemple :
![example solution]()
Pour éviter de supprimer des valeurs d'une manière qui ne mène pas à une solution valide (par exemple, en commençant par supprimer la valeur 1 la plus à droite, après quoi il n'y a pas de valeur 3 qui puisse être supprimée), nous allons d'abord supprimer toutes les connexions dans le graphe qui mènent à de telles solutions invalides.
Cela se fera en itérant deux fois sur la sous-séquence. Tout d'abord, nous procédons de gauche à droite, et pour chaque valeur, nous examinons sa connexion la plus à gauche, et supprimons toutes les connexions de la valeur à sa droite qui rencontrent ou croisent cette connexion ; par exemple, en considérant la connexion la plus à gauche de la valeur 2, deux connexions de la valeur 1 à sa droite (indiquées en rouge) sont supprimées car elles croisent cette connexion :
![removing crossed connections ltr]()
Dans l'étape suivante, nous allons de droite à gauche, et pour chaque valeur, nous regardons sa connexion la plus à droite, et supprimons toutes les connexions de la valeur sur sa gauche qui rencontrent ou croisent cette connexion ; par exemple, lorsque nous considérons la connexion la plus à droite de la valeur 1 sur la droite, la connexion la plus à droite de la valeur 2 sur sa gauche (indiquée en rouge) est supprimée car elle croise cette connexion :
![removing crossed connections rtl]()
Nous obtenons alors le graphique simplifié ci-dessous. Les combinaisons sont ensuite réalisées en combinant chaque instance connectée de chaque valeur de la sous-séquence, en utilisant, par exemple, la récursion : on itère sur les options de la première valeur de la sous-séquence, et à chaque fois on récure avec le reste de la sous-séquence, de sorte que l'option de la première valeur soit combinée avec toutes les options des autres valeurs.
![simplified graph]()
Il peut y avoir des connexions croisées dans le graphique simplifié, mais elles ne posent plus de problème. Dans l'exemple, vous verrez que même si la bonne connexion est choisie pour la valeur 3, il existe une connexion pour la valeur 2 qui ne se croise pas avec elle :
![example solution in simplified graph]()
La transposition en code est relativement simple ; vous trouverez, sous l'extrait de code, un exemple d'exécution du code avec les données de l'exemple.
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>");
Le code effectue les étapes suivantes :
-
Créer un tableau associatif de la position des instances de chaque valeur présente dans sub :
posi[1] = [0,2,8,10], posi[2] = [5,7,11], posi[3] = [3,6,9]}
-
Créez un tableau 2D qui relie les positions de la sous-séquence à celles de la séquence :
conn = [[0,2,8,10],[3,6,9],[5,7,11],[0,2,8,10]]
-
Passez en revue le tableau de gauche à droite et supprimez les connexions croisées :
conn = [[0,2,8,10],[3,6,9],[5,7,11],[8,10]]
-
Passez en revue le tableau de droite à gauche et supprimez les connexions croisées :
conn = [[0,2],[3,6],[5,7],[8,10]]
-
Générer toutes les combinaisons des positions en utilisant la récursion :
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]]
-
Utilisez les combinaisons pour supprimer les valeurs des copies de la séquence (voir l'extrait de code).
2. Suppression d'une liste non ordonnée de valeurs
Si la liste des valeurs à retirer n'est pas nécessairement une sous-séquence de la séquence principale, et que les valeurs peuvent être retirées dans n'importe quel ordre, la même méthode que ci-dessus peut être utilisée, avec un assouplissement des règles de connexion croisée :
La suppression des connexions croisées de la liste des positions, et l'évitement des connexions croisées lors de la génération des combinaisons, ne doit être effectuée que pour des valeurs identiques.
Dans cet exemple, seules les connexions croisées pour les valeurs dupliquées 1 sont supprimées ; d'abord de gauche à droite :
![removing crossed connections ltr]()
et ensuite de droite à gauche :
![removing crossed connections rtl]()
Le résultat est ce graphique simplifié, avec les connexions croisées problématiques pour la valeur 1 supprimées, et les connexions croisées pour les valeurs 2 et 3 restantes :
![simplified graph]()
Vous trouverez ci-dessous un exemple de code adapté de la version pour les sous-séquences ; seules quelques lignes du code sont modifiées, comme indiqué par des commentaires (et j'ai également utilisé une méthode différente pour supprimer les valeurs de la séquence). La liste des valeurs à supprimer est triée au départ, de sorte que les valeurs identiques sont regroupées, pour faciliter le suivi des valeurs identiques.
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>");
