Как я могу определить все возможные способы выделения подпоследовательности из последовательности?

Ответ 1

Эта проблема может быть решена в O(n*m + r) времени, где r - общая длина результатов, используя классический алгоритм самый длинный общий подпоследовательность.

После создания таблицы, как в Wikipedia , замените ее на список ячеек с диагональной стрелкой, которые также имеют значение, соответствующее их строке. Теперь пройдите назад от каждой ячейки с диагональю в последней строке, аккумулируя соответствующий индекс в строке и дублируя и разбивая накопление таким образом, чтобы каждая ячейка с диагональной стрелкой имела продолжение для всех ячеек с диагональю в предыдущей строке, которая находятся слева от него (сохраните это количество, а также, когда вы построите матрицу), и один меньше по стоимости. Когда накопление достигает нулевой ячейки, сплайсируйте накопленные индексы из строки и добавьте это в результате.

(Стрелки соответствуют тому, что LCS до сих пор произошло от LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]), см. функцию определение.)

Например:

  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

Код 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'])));

Ответ 2

Вы можете использовать рекурсию. Постройте новую подпоследовательность C, пройдя через A и подталкивая элементы по порядку. Всякий раз, когда вы сталкиваетесь с элементом, который соответствует голове B, вы будете разветвлять рекурсию на два пути: один, в котором вы удаляете (то есть пропускаете) элемент из A и B, а другой, в котором вы игнорируете его, и продолжаете работать как обычно.

Если вы исчерпаете все B (это означает, что вы "удалили" все элементы в B из A), то добавление остальной части A в C приведет к получению правильной подпоследовательности. В противном случае, если вы достигнете конца A без исчерпания всего B, C не является допустимой подпоследовательностью и должен быть отброшен.

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, []));
}

Внутренняя вспомогательная функция может быть сделана несколько более эффективно, заменив использование Array.concat в каждой рекурсивной ветки простой парой push()/pop(), хотя это делает процесс управления немного сложнее.

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();
    }
}

Ответ 3

Эта проблема может быть решена с использованием подхода восходящего динамического программирования с обратным трассированием.

Рассмотрим рекуррентное соотношение f(i1, i2), которое помогает проверить, можно ли удалить хвост последовательности arr2 из хвоста последовательности 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)

Я использую термин tail для обозначения подпоследовательности arr1, которая начинается с индекса i1 и заканчивается до конца arr1 (и то же самое для arr2 - хвоста arr2 начинается с index i2 и заканчивается до конца arr2).

Начните с реализации сверху вниз данного отношения повторения (еще без воспоминаний, чтобы упростить объяснение). Ниже приведен фрагмент кода Java, который печатает все возможные подпоследовательности arr1 после удаления 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 предоставленный фрагмент кода не использует какой-либо метод memoization, а имеет экспоненциальную сложность во время выполнения для всех экземпляров заданной проблемы.

Однако мы можем видеть, что переменная i1 может иметь только значение из интервала [0..length(arr1)], также переменная i2 может иметь только значение из интервала [0..length(arr2)].

Следовательно, можно проверить, можно ли удалить arr2 из arr1 с полиномиальной сложностью выполнения: O(length(arr1) * length(arr2)).

С другой стороны, даже если мы найдем с полиномиальной сложностью выполнения, что arr2 можно удалить из arr1 - все равно может быть экспоненциальное количество возможных способов удаления arr2 из arr1.

Например, рассмотрим экземпляр проблемы: когда нужно удалить arr2 = [1,1,1] из arr1 = [1,1,1,1,1,1,1]. Существует 7!/(3! * 4!) = 35 способ сделать это.

Тем не менее ниже приведено решение динамического программирования снизу вверх с backtracking, которое по-прежнему для многих экземпляров данной проблемы будет иметь более высокую сложность выполнения, чем экспоненциальная:

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 описанного решения

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

Ответ 4

Алгоритм:

• Рекурсивно построить дерево узлов, начиная с первого элемента в B. Каждое значение node представляет собой индекс элемента подпоследовательности, соответствующий его уровню, а его потомки - это индексы следующего элемента - так что для [1,2,1,3,1,4,4], [1,4,4] дерево будет [ [ 0, [5, [6]], [6] ], [ 2, [5, [6]], [6] ], [ 4, [5, [6]], [6] ].
• Пройдите это дерево и создайте подпоследовательности элементов для удаления, т.е. найдите все пути в дереве до тех пор, пока подпоследовательность. Это приведет к списку вроде [ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ].
• Для каждого созданного таким образом списка добавьте список, который получается из элементов при удалении этих индексов: [ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ].

Код для этого, который соответствует всем вашим тестовым случаям:

#!/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]))

Ответ 5

Сначала я бы использовал строку. Легче манипулировать:

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

Я не прокомментировал код, но не стесняйтесь просить разъяснений. Он не тестировался, но идея в нем...

Ответ 6

Моя цель состояла в том, чтобы создавать и вызывать функции как можно меньше. Кажется, это работает. Не могли бы быть очищены. Что-то поиграть с...

function removeSubSeq( seq, sub ) {

    var arr,
        sub_v,
        sub_i = 0,
        seq_i,
        sub_len = sub.length,
        sub_lenm1 = sub_len - 1,
        seq_len = seq.length,
        pos = {},
        pos_len = [],
        c_pos,
        map_i = [],
        len,
        r_pos,
        sols = [],
        sol;

    do {

        map_i[ sub_i ] = 0;
        sub_v = sub[ sub_i ];

        if( pos[ sub_v ] ) {

            pos_len[ sub_i ] = pos_len[ sub_i - 1 ];
            continue;
        
        }

        arr = pos[ sub_v ] = [];

        c_pos = 0;

        seq_i = seq_len;

        while( seq_i-- ) {

            if( seq[ seq_i ] === sub_v ) {
                
                arr[ c_pos++ ] = seq_i;

            }

        }

        pos_len[ sub_i ] = arr.length;

    } while( ++sub_i < sub_len );

    len = pos[ sub[ 0 ] ].length;

    while( map_i[ 0 ] < len ) {

        sub_i = 0;
        arr = [];

        do {

            r_pos = pos[ sub[ sub_i ] ][ map_i[ sub_i ] ];
            
            if( sub_i && r_pos <= arr[ sub_i - 1] ) break;
            
            arr.push( r_pos );
        
        } while( ++sub_i < sub_len );

        if( sub_i === sub_len ) {
            
            sol = seq.slice( 0 );

            while( sub_i-- ) sol.splice( arr[ sub_i ], 1 );

            sols.push( sol );
        
        }

        sub_i = sub_lenm1;

        while( ++map_i[ sub_i ] === pos_len[ sub_i ] ) {
            if( sub_i === 0 ) break;
            map_i[ sub_i-- ] = 0;
        }

    } while( map_i[ 0 ] < len );

    return sols;

}

console.log(JSON.stringify(removeSubSeq([1,2,1,3,1,4,4], [1,4,4])));
console.log(JSON.stringify(removeSubSeq([8,6,4,4], [6,4,8])));
console.log(JSON.stringify(removeSubSeq([1,1,2], [1])));
console.log(JSON.stringify(removeSubSeq(['a','g','b','a','b','c','c'], ['a','b','c'])));