Рекурсия: отслеживание переменной во всех путях рекурсии, когда возможно несколько подпутей - PullRequest
Новая
       29

Рекурсия: отслеживание переменной во всех путях рекурсии, когда возможно несколько подпутей

0 голосов
/ 19 июня 2019

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

С помощью рекурсивных вызовов считать легко. 

function count(str, pattern, strInd, patternInd) {
    if (patternInd === 0) {
      return 1;
    }

    if (strInd === 0) {
      return 0;
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
      const count1 = count(str, pattern, strInd - 1, patternInd - 1);
      const count2 = count(str, pattern, strInd - 1, patternInd);
      return count1 + count2;
    } else {
      return count(str, pattern, strInd - 1, patternInd);
    }
  }

Для сохранения индексов, у меня есть логика, чтобы поместить текущий индекс str в «массив локальных индексов» внутри рекурсивного вызова, когда символ шаблона совпадает со строковым символом, и как только шаблон закончен, нажмите «local индексы "к" глобальным индексам "и сбрасывают" локальные индексы "для следующего пути рекурсии.

Сброс локальных индексов - вот где я сталкиваюсь с проблемами: 

function count(str, pattern, strInd, patternInd) {
    if (patternInd === 0) {
      // when this path ends, add to list the indices found on this path
      globalIndices.push(localIndices);
      // reset the local indices
      localIndices = [];
      console.log("found");
      return 1;
    }

    if (strInd === 0) {
      return 0;
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
      localIndices.push(strInd);
      const count1 = count(str, pattern, strInd - 1, patternInd - 1);
      const count2 = count(str, pattern, strInd - 1, patternInd);
      return count1 + count2;
    } else {
      return count(str, pattern, strInd - 1, patternInd);
    }
  }

Таким образом, он теряет информацию о предыдущем пути после каждой бифуркации, поскольку после использования соответствующего подпути он удаляется из localIndices, и localIndices начинает отслеживать совпадения после того, как произошла бифуркация.

так, например, str это "abab", а pattern это "ab" тогда я хотел бы globalIndices = [[4,3], [4,1], [2,1]] но вместо этого я бы получил [[4,3], [1], [2,1]]

Я бы хотел сбросить "локальные индексы" на предыдущую бифуркацию.

Двигаюсь ли я в правильном направлении, или же для такого рода проблем нужна совсем другая реализация?

1 Ответ

1 голос
/ 19 июня 2019

Во-первых, когда вы собираете индексы, вам не нужно вести подсчет, так как длина конечного массива будет равна счетчику: каждый элемент массива будет соответствовать совпадению и будет списком соответствующих индексов..

Вы можете сделать возвращаемое значение функции, для которой совпадает массив (частичный), и расширить каждый массив дополнительным индексом (для случая, когда этот символ берется в совпадении) при возврате: 

function count(str, pattern, strInd = str.length, patternInd = pattern.length) {
    if (patternInd === 0) {
        return [[]]; // A match. Provide an array with an empty array for that match
    }

    if (strInd === 0) {
        return []; // No match. Provide empty array.
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
        const matches1 = count(str, pattern, strInd - 1, patternInd - 1);
        const matches2 = count(str, pattern, strInd - 1, patternInd);
        // For the first case, add the current string index to the partial matches:
        return [...matches1.map(indices => [...indices, strInd-1]), ...matches2];
    } else {
        return count(str, pattern, strInd - 1, patternInd);
    }
}

console.log(count("abab", "ab"));

Обратите внимание, что индексы начинаются с нуля, поэтому они на единицу меньше ожидаемого результата.Кроме того, индексы располагаются слева направо, что представляется более полезным.

Общая идея

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

Возвращаемые значения могут быть сложными: когда вам нужно вернуть больше, чем «одно», выможно просто поместить разные части в объект или массив и вернуть его.Затем вызывающий абонент может снова распаковать его в отдельные части.Например, если бы мы также вернули счет в приведенном выше коде, мы бы сделали: 

function count(str, pattern, strInd = str.length, patternInd = pattern.length) {
    if (patternInd === 0) {
        return { count: 1, matches: [[]] };
    }

    if (strInd === 0) {
        return { count: 0, matches: [] };
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
        const { count: count1, matches: matches1 }  = 
             count(str, pattern, strInd - 1, patternInd - 1);
        const { count: count2, matches: matches2 } = 
             count(str, pattern, strInd - 1, patternInd);
        // For the first case, add the current string index to the partial matches:
        return {
            count: count1 + count2,
            matches: [...matches1.map(indices => [...indices, strInd-1]), ...matches2]
        };
    } else {
        return count(str, pattern, strInd - 1, patternInd);
    }
}

Всегда должно быть возможно решить проблему рекурсии, подобную этой, но в случае, если она окажется слишком сложнойв качестве альтернативы вы можете передать дополнительную объектную переменную (или массив), к которой рекурсивный вызов добавит свои результаты: он подобен коллектору, который постепенно увеличивается до конечного решения.Недостатком является то, что лучше не допускать, чтобы функции имели побочные эффекты, и, во-вторых, вызывающая функция должна уже подготовить пустой объект и передать его для получения результатов.

Наконец, не делайте 'не должно быть соблазна использовать глобальные переменные для такого сбора данных.Было бы немного лучше, если бы такие «глобальные» переменные были фактически локальными переменными в замыкании.Но все же, другой вариант должен быть предпочтительным.

...