Привет, друзья!

В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это шестая часть серии, в которой мы начинаем разбирать алгоритмы.

Сегодня мы поговорим об алгоритмах для работы с множествами.

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

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

Интересно? Тогда прошу под кат.

• Первая часть
• Вторая часть
• Третья часть
• Четвертая часть
• Пятая часть

Множества

Прямое произведение

Описание

• Википедия

В теории множеств прямое (декартово) произведение (Cartesian product) — это математическая операция, которая возвращает множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств. Таким образом, для множеств A и B прямое произведение — это множество упорядоченных пар (a, b), где a ∈ A и b ∈ B.

Прямое произведение A x B множеств A={ x, y, z } и B={ 1, 2, 3 }:

Реализация

// algorithms/sets/cartesian-product.js export default function cartesianProduct(a, b) {   if (!a?.length || !b?.length) return null    return a.map((x) => b.map((y) => [x, y])).reduce((a, b) => a.concat(b), []) }

Тестирование

// algorithms/sets/__tests__/cartesian-product.test.js import cartesianProduct from '../cartesian-product'  describe('cartesianProduct', () => {   it('должен вернуть `null` при отсутствии одного из множеств', () => {     const product1 = cartesianProduct([1], null)     const product2 = cartesianProduct([], null)      expect(product1).toBeNull()     expect(product2).toBeNull()   })    it('должен вычислить произведение двух множеств', () => {     const product1 = cartesianProduct([1], [1])     const product2 = cartesianProduct([1, 2], [3, 5])      expect(product1).toEqual([[1, 1]])     expect(product2).toEqual([       [1, 3],       [1, 5],       [2, 3],       [2, 5],     ])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/__tests__/cartesian-product

Результат:

Тасование Фишера-Йетса

Описание

• Википедия

Тасование Фишера-Йетса — это алгоритм создания произвольных перестановок конечного множества, проще говоря, для произвольного тасования множества. Правильно реализованный алгоритм несмещенный, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, а также не требует дополнительной памяти.

Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещенный результат.

Реализация

// algorithms/sets/fisher-yates.js export default function fisherYates(arr) {   // Эффективно создаем глубокую копию массива   // https://developer.mozilla.org/en-US/docs/Web/API/structuredClone   const arrCopy = structuredClone(arr)    for (let i = arrCopy.length - 1; i > 0; i--) {     const j = Math.floor(Math.random() * (i + 1))     ;[arrCopy[i], arrCopy[j]] = [arrCopy[j], arrCopy[i]]   }    return arrCopy }

Тестирование

// algorithms/sets/__tests__/fisher-yates.test.js import fisherYates from '../fisher-yates'  const sortedArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  describe('fisherYates', () => {   it('должен тасовать маленькие массивы', () => {     expect(fisherYates([])).toEqual([])     expect(fisherYates([1])).toEqual([1])   })    it('должен произвольно перетасовать элементы массива', () => {     const shuffledArray = fisherYates(sortedArr)      expect(shuffledArray.length).toBe(sortedArr.length)     expect(shuffledArray).not.toEqual(sortedArr)     expect(shuffledArray.sort()).toEqual(sortedArr)   }) })

Запускаем тесты:

npm run test ./algorithms/sets/__tests__/fisher-yates

Результат:

Множество всех подмножеств

Описание

• Википедия

Множество всех подмножеств (булеан, показательное множество) (power set) — множество, состоящее из всех подмножеств данного множества
S (включая пустое множество и само множество S); обозначается
P(S) или 2^S (так как оно соответствует множеству отображений из S в {0, 1}).

Например, множеством всех подмножеств множества { x, y, z } будет:

{   {}, // (также обозначается как ∅ или нулевое подмножество)   {x},   {y},   {z},   {x, y},   {x, z},   {y, z},   {x, y, z} }

Иллюстрация элементов этого множества, упорядоченных по порядку включения:

Количество подмножеств

Если S — это конечное множество, содержащее |S| = n элементов, то количество подмножеств S равняется |P(S)| = 2^n.

Алгоритмы

Двоичный подход

Биты каждого числа двоичного представления в диапазоне от 0 до 2^n показывают, следует ли включать соответствующий элемент множества в подмножество (1 — включать, 0 — не включать). Например, для множества { 1, 2, 3 } бинарное число 0b010 означает, что в подмножество включается только второй элемент множества, т.е. 2.

Реализация

// algorithms/sets/power-set/bitwise.js export default function bitwise(set) {   const subsets = []    // Количество подмножеств - `2^n`, где `n` - количество элементов в `set`.   // Это обусловлено тем, что для каждого элемента `set` мы будем решать,   // включать его в подмножество или нет (2 варианта на каждый элемент)   const numberOfCombinations = 2 ** set.length    for (let i = 0; i < numberOfCombinations; i++) {     const subset = []      for (let j = 0; j < set.length; j++) {       // Решаем, включать текущий элемента в подмножество или нет       if (i & (1 << j)) {         subset.push(set[j])       }     }      subsets.push(subset)   }    return subsets }

Тестирование

// algorithms/sets/power-set/__tests__/bitwise.test.js import bitwise from '../bitwise'  describe('bitwise', () => {   it('должен вычислить множества всех подмножеств с помощью бинарного подхода', () => {     expect(bitwise([1])).toEqual([[], [1]])      expect(bitwise([1, 2, 3])).toEqual([       [],       [1],       [2],       [1, 2],       [3],       [1, 3],       [2, 3],       [1, 2, 3],     ])   }) })

Рекурсивный подход

При таком подходе мы рекурсивно пытаемся добавить следующий элемент множества в подмножество, запоминаем подмножество, затем удаляем текущий элемент и берем следующий.

Реализация

// algorithms/sets/power-set/backtracking.js export default function backtracking(   set,   allSubsets = [[]],   currentSubset = [],   start = 0, ) {   // Перебираем элементы множества, которые могут быть добавлены в подмножество   // без дублирования (это обеспечивается значением `start`)   for (let i = start; i < set.length; i++) {     // Добавляем текущий элемент в подмножество     currentSubset.push(set[i])      // Текущее подмножество является валидным, запоминаем его.     // `structuredClone()` создает копию `currentSubset`.     // Это необходимо, поскольку `currentSubset` будет модифицирован     // в дальнейших рекурсивных вызовах     allSubsets.push(structuredClone(currentSubset))      // Генерируем другие подмножества для текущего подмножества.     // В качестве значения `start` передаем `i + 1` во избежание дублирования     backtracking(set, allSubsets, currentSubset, i + 1)      // Удаляем последний элемент и берем следующий     currentSubset.pop()   }    return allSubsets }

Тестирование

// algorithms/sets/power-set/__tests__/backtracking.test.js import backtracking from '../backtracking'  describe('backtracking', () => {   it('должен вычислить множества всех подмножеств с помощью рекурсивного подхода', () => {     expect(backtracking([1])).toEqual([[], [1]])      expect(backtracking([1, 2, 3])).toEqual([       [],       [1],       [1, 2],       [1, 2, 3],       [1, 3],       [2],       [2, 3],       [3],     ])   }) })

Каскадный подход

Вероятно, это самый простой способ создания множества всех подмножеств.

Предположим, что у нас есть множество originalSet = [1, 2, 3].

Мы начинаем с пустого подмножества:

powerSets = [[]]

Добавляем первый элемент originalSet во все существующие подмножества:

[[]] ← 1 = [[], [1]]

Добавляем второй элемент:

[[], [1]] ← 2 = [[], [1], [2], [1, 2]]

Добавляем третий элемент:

[[], [1], [2], [1, 2]] ← 3 = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

И так для всех элементов originalSet. На каждой итерации количество множеств удваивается, поэтому в итоге мы получаем 2^n множеств.

Реализация

// algorithms/sets/power-set/cascading.js export default function cascading(set) {   // Начинаем с пустого множества   const sets = [[]]    for (let i = 0; i < set.length; i++) {     // Без этого мы получим бесконечный цикл,     // поскольку длина `sets` будет увеличиваться на каждой итерации     const len = sets.length     for (let j = 0; j < len; j++) {       const _set = [...sets[j], set[i]]       sets.push(_set)     }   }    return sets }

Тестирование

// algorithms/sets/power-set/__tests__/cascading.test.js import cascading from '../cascading'  describe('cascading', () => {   it('должен вычислить множества всех подмножеств с помощью каскадного подхода', () => {     expect(cascading([1])).toEqual([[], [1]])      expect(cascading([1, 2])).toEqual([[], [1], [2], [1, 2]])      expect(cascading([1, 2, 3])).toEqual([       [],       [1],       [2],       [1, 2],       [3],       [1, 3],       [2, 3],       [1, 2, 3],     ])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/power-set

Результат:

Перестановки и комбинации

Описание

• Math is fun
• Шпаргалки

Когда порядок элементов не важен, это комбинация (combination).

Когда порядок элементов важен, это перестановка (permutation).

Перестановки

Перестановки без повторений

Перестановка (permutation) — это перестановка элементов упорядоченного списка S во взаимно однозначное соответствие самому S.

Пример перестановок строки ABC:

ABC ACB BAC BCA CBA CAB

Еще один пример — первые три человека в гонке: вы не можете одновременно быть и первым, и вторым.

Количество вариантов:

n * (n-1) * (n -2) * ... * 1 = n! (факториал `n`)

Реализация

// algorithms/sets/permutations/without-repetitions.js export default function withoutRepetitions(set) {   if (set.length === 1) {     return [set]   }    const result = []    const subset = withoutRepetitions(set.slice(1))   const first = set[0]    for (let i = 0; i < subset.length; i++) {     const smaller = subset[i]     for (let j = 0; j < smaller.length + 1; j++) {       const permutation = [...smaller.slice(0, j), first, ...smaller.slice(j)]       result.push(permutation)     }   }    return result }

Тестирование

// algorithms/sets/permutations/__tests__/without-repetitions.test.js import withoutRepetitions from '../without-repetitions' import factorial from '../../../math/factorial'  describe('withoutRepetitions', () => {   it('должен переставлять элементы множеств без повторений', () => {     const permutations1 = withoutRepetitions(['A'])     expect(permutations1).toEqual([['A']])      const permutations2 = withoutRepetitions(['A', 'B'])     expect(permutations2.length).toBe(2)     expect(permutations2).toEqual([       ['A', 'B'],       ['B', 'A'],     ])      const permutations6 = withoutRepetitions(['A', 'A'])     expect(permutations6.length).toBe(2)     expect(permutations6).toEqual([       ['A', 'A'],       ['A', 'A'],     ])      const permutations3 = withoutRepetitions(['A', 'B', 'C'])     expect(permutations3.length).toBe(factorial(3))     expect(permutations3).toEqual([       ['A', 'B', 'C'],       ['B', 'A', 'C'],       ['B', 'C', 'A'],       ['A', 'C', 'B'],       ['C', 'A', 'B'],       ['C', 'B', 'A'],     ])      const permutations4 = withoutRepetitions(['A', 'B', 'C', 'D'])     expect(permutations4.length).toBe(factorial(4))     expect(permutations4).toEqual([       ['A', 'B', 'C', 'D'],       ['B', 'A', 'C', 'D'],       ['B', 'C', 'A', 'D'],       ['B', 'C', 'D', 'A'],       ['A', 'C', 'B', 'D'],       ['C', 'A', 'B', 'D'],       ['C', 'B', 'A', 'D'],       ['C', 'B', 'D', 'A'],       ['A', 'C', 'D', 'B'],       ['C', 'A', 'D', 'B'],       ['C', 'D', 'A', 'B'],       ['C', 'D', 'B', 'A'],       ['A', 'B', 'D', 'C'],       ['B', 'A', 'D', 'C'],       ['B', 'D', 'A', 'C'],       ['B', 'D', 'C', 'A'],       ['A', 'D', 'B', 'C'],       ['D', 'A', 'B', 'C'],       ['D', 'B', 'A', 'C'],       ['D', 'B', 'C', 'A'],       ['A', 'D', 'C', 'B'],       ['D', 'A', 'C', 'B'],       ['D', 'C', 'A', 'B'],       ['D', 'C', 'B', 'A'],     ])      const permutations5 = withoutRepetitions(['A', 'B', 'C', 'D', 'E', 'F'])     expect(permutations5.length).toBe(factorial(6))   }) })

Перестановки с повторениями

Когда разрешены дубликаты, мы говорим о перестановках с повторениями.

Примером такой перестановки может быть код замка 333.

Количество вариантов:

n * n * n ... (r раз) = n^r (экспонента `r`)

Реализация

// algorithms/sets/permutations/with-repetitions.js export default function withRepetitions(set, length = set.length) {   if (length === 1) {     return set.map((i) => [i])   }    const result = []    const subset = withRepetitions(set, length - 1)    for (const i of set) {     for (const j of subset) {       result.push([i, ...j])     }   }    return result }

Тестирование

// algorithms/sets/permutations/__tests__/with-repetitions.test.js import withRepetitions from '../with-repetitions'  describe('withRepetitions', () => {   it('должен переставлять элементы множеств с повторениями', () => {     const permutations1 = withRepetitions(['A'])     expect(permutations1).toEqual([['A']])      const permutations2 = withRepetitions(['A', 'B'])     expect(permutations2).toEqual([       ['A', 'A'],       ['A', 'B'],       ['B', 'A'],       ['B', 'B'],     ])      const permutations3 = withRepetitions(['A', 'B', 'C'])     expect(permutations3).toEqual([       ['A', 'A', 'A'],       ['A', 'A', 'B'],       ['A', 'A', 'C'],       ['A', 'B', 'A'],       ['A', 'B', 'B'],       ['A', 'B', 'C'],       ['A', 'C', 'A'],       ['A', 'C', 'B'],       ['A', 'C', 'C'],       ['B', 'A', 'A'],       ['B', 'A', 'B'],       ['B', 'A', 'C'],       ['B', 'B', 'A'],       ['B', 'B', 'B'],       ['B', 'B', 'C'],       ['B', 'C', 'A'],       ['B', 'C', 'B'],       ['B', 'C', 'C'],       ['C', 'A', 'A'],       ['C', 'A', 'B'],       ['C', 'A', 'C'],       ['C', 'B', 'A'],       ['C', 'B', 'B'],       ['C', 'B', 'C'],       ['C', 'C', 'A'],       ['C', 'C', 'B'],       ['C', 'C', 'C'],     ])      const permutations4 = withRepetitions(['A', 'B', 'C', 'D'])     expect(permutations4.length).toBe(4 * 4 * 4 * 4)   }) })

Запускаем тесты:

npm run test ./algorithms/sets/permutations

Результат:

Комбинации

Комбинации без повторений

Так работают лотереи. Числа пишутся одно за другим. Побеждает счастливая комбинация, независимо от порядка чисел.

Комбинация чисел без повторений:

[2, 14, 15, 27, 30, 33]

Количество вариантов:

Здесь n — количество вариантов для выбора, а r — выбранное нами количество, без повторений, порядок не важен.

Такая комбинация также называется биномиальным коэффициентом.

Реализация

// algorithms/sets/combinations/without-repetitions.js export default function withoutRepetitions(set, length) {   if (length === 1) {     return set.map((i) => [i])   }    const result = []    set.forEach((i, idx) => {     const subset = withoutRepetitions(set.slice(idx + 1), length - 1)      for (const j of subset) {       result.push([i, ...j])     }   })    return result }

Тестирование

// algorithms/sets/combinations/__tests__/without-repetitions.test.js import combineWithoutRepetitions from '../without-repetitions' import factorial from '../../../math/factorial'  describe('combineWithoutRepetitions', () => {   it('должен комбинировать элементы множеств без повторов', () => {     expect(combineWithoutRepetitions(['A', 'B'], 3)).toEqual([])      expect(combineWithoutRepetitions(['A', 'B'], 1)).toEqual([['A'], ['B']])      expect(combineWithoutRepetitions(['A'], 1)).toEqual([['A']])      expect(combineWithoutRepetitions(['A', 'B'], 2)).toEqual([['A', 'B']])      expect(combineWithoutRepetitions(['A', 'B', 'C'], 2)).toEqual([       ['A', 'B'],       ['A', 'C'],       ['B', 'C'],     ])      expect(combineWithoutRepetitions(['A', 'B', 'C'], 3)).toEqual([       ['A', 'B', 'C'],     ])      expect(combineWithoutRepetitions(['A', 'B', 'C', 'D'], 3)).toEqual([       ['A', 'B', 'C'],       ['A', 'B', 'D'],       ['A', 'C', 'D'],       ['B', 'C', 'D'],     ])      expect(combineWithoutRepetitions(['A', 'B', 'C', 'D', 'E'], 3)).toEqual([       ['A', 'B', 'C'],       ['A', 'B', 'D'],       ['A', 'B', 'E'],       ['A', 'C', 'D'],       ['A', 'C', 'E'],       ['A', 'D', 'E'],       ['B', 'C', 'D'],       ['B', 'C', 'E'],       ['B', 'D', 'E'],       ['C', 'D', 'E'],     ])      const combinationOptions = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']     const combinationSlotsNumber = 4     const combinations = combineWithoutRepetitions(       combinationOptions,       combinationSlotsNumber,     )     const n = combinationOptions.length     const r = combinationSlotsNumber     const expectedNumberOfCombinations =       factorial(n) / (factorial(r) * factorial(n - r))      expect(combinations.length).toBe(expectedNumberOfCombinations)   }) })

Комбинации с повторениями

Примером такой комбинации являются монеты в кармане: (5, 5, 5, 10, 10).

Еще один пример — пять вкусов мороженного: banana, chocolate, lemon, strawberry и vanilla.

Мы можем выбрать 3. Сколько у нас вариантов?

Используем символы для вкусов — { b, c, l, s, v }. Примеры вариантов:

• { c, c, c }
• { b, l, v }
• { b, v, v }

Количество вариантов:

Здесь n — количество вариантов для выбора, дубликаты разрешены, порядок не важен.

Реализация

// algorithms/sets/combinations/with-repetitions.js export default function withRepetitions(set, length) {   if (length === 1) {     return set.map((i) => [i])   }    const result = []    set.forEach((i, idx) => {     const subset = withRepetitions(set.slice(idx), length - 1)      for (const j of subset) {       result.push([i, ...j])     }   })    return result }

Тестирование

// algorithms/sets/combinations/__tests__/with-repetitions.test.js import withRepetitions from '../with-repetitions' import factorial from '../../../math/factorial'  describe('withRepetitions', () => {   it('должен комбинировать элементы множеств с повторами', () => {     expect(withRepetitions(['A'], 1)).toEqual([['A']])      expect(withRepetitions(['A', 'B'], 1)).toEqual([['A'], ['B']])      expect(withRepetitions(['A', 'B'], 2)).toEqual([       ['A', 'A'],       ['A', 'B'],       ['B', 'B'],     ])      expect(withRepetitions(['A', 'B'], 3)).toEqual([       ['A', 'A', 'A'],       ['A', 'A', 'B'],       ['A', 'B', 'B'],       ['B', 'B', 'B'],     ])      expect(withRepetitions(['A', 'B', 'C'], 2)).toEqual([       ['A', 'A'],       ['A', 'B'],       ['A', 'C'],       ['B', 'B'],       ['B', 'C'],       ['C', 'C'],     ])      expect(withRepetitions(['A', 'B', 'C'], 3)).toEqual([       ['A', 'A', 'A'],       ['A', 'A', 'B'],       ['A', 'A', 'C'],       ['A', 'B', 'B'],       ['A', 'B', 'C'],       ['A', 'C', 'C'],       ['B', 'B', 'B'],       ['B', 'B', 'C'],       ['B', 'C', 'C'],       ['C', 'C', 'C'],     ])      const combinationOptions = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']     const combinationSlotsNumber = 4     const combinations = withRepetitions(       combinationOptions,       combinationSlotsNumber,     )     const n = combinationOptions.length     const r = combinationSlotsNumber     const expectedNumberOfCombinations =       factorial(r + n - 1) / (factorial(r) * factorial(n - 1))      expect(combinations.length).toBe(expectedNumberOfCombinations)   }) })

Запускаем тесты:

npm run test ./algorithms/sets/combinations

Результат:

Шпаргалки

Наибольшая общая подпоследовательность

Описание

• Википедия
• YouTube

Задача нахождения наибольшей общей подпоследовательности (НОП) (longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике. Она также широко используется системами контроля версий, такими как Git, для согласования изменений в коллекции файлов.

Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность ABCDEF, то ACE будет подпоследовательностью, но не подстрокой, а ABC будет как подпоследовательностью, так и подстрокой.

Примеры

• НОП для последовательностей ABCDGH и AEDFHR — ADH длиной 3
• НОП для последовательностей AGGTAB и GXTXAYB — GTAB длиной 4

Реализация

НОП можно реализовать, как минимум, двумя способами.

Рекурсивный подход

// algorithms/sets/longest-common-subsequence/recursive.js export default function lcsRecursive(a, b) {   const lcs = (a, b, memo = {}) => {     if (!a || !b) return ''      if (memo[`${a},${b}`]) {       return memo[`${a},${b}`]     }      if (a[0] === b[0]) {       return a[0] + lcs(a.slice(1), b.slice(1), memo)     }      const next1 = lcs(a.slice(1), b, memo)     const next2 = lcs(a, b.slice(1), memo)      const nextLongest = next1.length >= next2.length ? next1 : next2     memo[`${a},${b}`] = nextLongest      return nextLongest   }    return lcs(a, b) }

Тестирование

// algorithms/sets/longest-common-subsequence/__tests__/recursive.test.js import lcsRecursive from '../recursive'  describe('lcsRecursive', () => {   it('должен рекурсивно найти НОП двух строк', () => {     expect(lcsRecursive('', '')).toBe('')     expect(lcsRecursive('ABC', '')).toBe('')     expect(lcsRecursive('', 'ABC')).toBe('')     expect(lcsRecursive('ABABC', 'BABCA')).toBe('BABC')     expect(lcsRecursive('BABCA', 'ABCBA')).toBe('ABCA')     expect(lcsRecursive('sea', 'eat')).toBe('ea')     expect(lcsRecursive('algorithms', 'rithm')).toBe('rithm')     expect(       lcsRecursive(         'Algorithms and data structures implemented in JavaScript',         'Here you may find Algorithms and data structures that are implemented in JavaScript',       ),     ).toBe('Algorithms and data structures implemented in JavaScript')   }) })

Динамическое программирование

Этот подход предполагает использование матрицы (см. ролик на ютубе по ссылке в начале раздела).

// algorithms/sets/longest-common-subsequence/matrix.js export default function lcs(a, b) {   // Инициализируем матрицу LCS   const matrix = new Array(b.length + 1)     .fill(null)     .map(() => new Array(a.length + 1).fill(null))    // Заполняем `0` первую строку   for (let i = 0; i <= a.length; i++) {     matrix[0][i] = 0   }    // Заполняем `0` первую колонку   for (let i = 0; i <= b.length; i++) {     matrix[i][0] = 0   }    // Заполняем матрицу LCS   for (let i = 1; i <= b.length; i++) {     for (let j = 1; j <= a.length; j++) {       if (b[i - 1] === a[j - 1]) {         matrix[i][j] = matrix[i - 1][j - 1] + 1       } else {         matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1])       }     }   }    // Вычисляем LCS на основе матрицы   if (!matrix[b.length][a.length]) {     return ['']   }    const lcs = []   let i = a.length   let j = b.length    while (i > 0 && j > 0) {     if (a[i - 1] === b[j - 1]) {       // Двигаемся по диагонали "влево-верх"       lcs.unshift(a[i - 1])       i--       j--     } else if (matrix[j][i] === matrix[j][i - 1]) {       // Двигаемся влево       i--     } else {       // Двигаемся вверх       j--     }   }    return lcs }

Тестирование

// algorithms/sets/longest-common-subsequence/__tests__/matrix.test.js import lcs from '../matrix'  describe('lcs', () => {   it('должен найти НОП двух множеств', () => {     expect(lcs([''], [''])).toEqual([''])      expect(lcs([''], ['A', 'B', 'C'])).toEqual([''])      expect(lcs(['A', 'B', 'C'], [''])).toEqual([''])      expect(lcs(['A', 'B', 'C'], ['D', 'E', 'F', 'G'])).toEqual([''])      expect(       lcs(['A', 'B', 'C', 'D', 'G', 'H'], ['A', 'E', 'D', 'F', 'H', 'R']),     ).toEqual(['A', 'D', 'H'])      expect(       lcs(['A', 'G', 'G', 'T', 'A', 'B'], ['G', 'X', 'T', 'X', 'A', 'Y', 'B']),     ).toEqual(['G', 'T', 'A', 'B'])      expect(       lcs(['A', 'B', 'C', 'D', 'A', 'F'], ['A', 'C', 'B', 'C', 'F']),     ).toEqual(['A', 'B', 'C', 'F'])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/longest-common-subsequence

Результат:

Кратчайшая общая суперпоследовательность

Описание

• Википедия

Кратчайшая общая суперпоследовательность (КОС) (shortest common supersequence, SCS) двух последовательностей X и Y — это самая короткая последовательность, содержащая X и Y.

Предположим, что у нас есть строки str1 и str2 и нам нужно найти кратчайшую строку, содержащую как str1, так и str2.

Эта задача тесно связана с задачей нахождения наибольшей общей подпоследовательности.

Примеры

• КОС для строк geek и eke — geeke длиной 5
• КОС для строк AGGTAB и GXTXAYB — AGXGTXAYB длиной 9

Реализация

Для реализации алгоритма нахождения КОС можно использовать алгоритм нахождения НОП, разобранный нами в предыдущем разделе.

// algorithms/sets/shortest-common-supersequence.js import lcsFn from './longest-common-subsequence/matrix'  export default function scs(set1, set2) {   // Находим НОП двух множеств   const lcs = lcsFn(set1, set2)    // Если НОП пустая, то КОС будет просто   // объединением множеств   if (lcs.length === 1 && lcs[0] === '') {     return set1.concat(set2)   }    // Добавляем элементы множеств в порядке перед/внутрь/после НОП   let result = []    let idx1 = 0   let idx2 = 0   let idx = 0   let onHold1 = false   let onHold2 = false    while (idx < lcs.length) {     // Добавляем элементы `set1` в правильном порядке     if (idx1 < set1.length) {       if (!onHold1 && set1[idx1] !== lcs[idx]) {         result.push(set1[idx1])         idx1++       } else {         onHold1 = true       }     }      // Добавляем элементы `set2` в правильном порядке     if (idx2 < set2.length) {       if (!onHold2 && set2[idx2] !== lcs[idx]) {         result.push(set2[idx2])         idx2++       } else {         onHold2 = true       }     }      // Добавляем НОП в правильном порядке     if (onHold1 && onHold2) {       result.push(lcs[idx])       idx++       idx1++       idx2++       onHold1 = false       onHold2 = false     }   }    // Добавляем остатки `set1`   if (idx1 < set1.length) {     result = result.concat(set1.slice(idx1))   }    // Добавляем остатки `set2`   if (idx2 < set2.length) {     result = result.concat(set2.slice(idx2))   }    return result }

Тестирование

// algorithms/sets/__tests__/shortest-common-supersequence.test.js import shortestCommonSupersequence from '../shortest-common-supersequence'  describe('shortestCommonSupersequence', () => {   it('должен найти КОС двух множеств', () => {     // LCS (наибольшая общая последовательность) пустая     expect(       shortestCommonSupersequence(['A', 'B', 'C'], ['D', 'E', 'F']),     ).toEqual(['A', 'B', 'C', 'D', 'E', 'F'])      // LCS - "EE"     expect(       shortestCommonSupersequence(['G', 'E', 'E', 'K'], ['E', 'K', 'E']),     ).toEqual(['G', 'E', 'K', 'E', 'K'])      // LCS - "GTAB"     expect(       shortestCommonSupersequence(         ['A', 'G', 'G', 'T', 'A', 'B'],         ['G', 'X', 'T', 'X', 'A', 'Y', 'B'],       ),     ).toEqual(['A', 'G', 'G', 'X', 'T', 'X', 'A', 'Y', 'B'])      // LCS - "BCBA"     expect(       shortestCommonSupersequence(         ['A', 'B', 'C', 'B', 'D', 'A', 'B'],         ['B', 'D', 'C', 'A', 'B', 'A'],       ),     ).toEqual(['A', 'B', 'D', 'C', 'A', 'B', 'D', 'A', 'B'])      // LCS - "BDABA"     expect(       shortestCommonSupersequence(         ['B', 'D', 'C', 'A', 'B', 'A'],         ['A', 'B', 'C', 'B', 'D', 'A', 'B', 'A', 'C'],       ),     ).toEqual(['A', 'B', 'C', 'B', 'D', 'C', 'A', 'B', 'A', 'C'])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/__tests__/shortest-common-supersequence

Результат:

Максимальный подмассив

Описание

• Википедия
• GeeksForGeeks

Задача максимального подмассива (maximum subarray) — это задача поиска подмассива в одномерном массиве a[1..n], числа которого дают наибольшую сумму (числа должны следовать одно за другим).

Исходные массивы обычно содержат отрицательные и положительные числа, а также 0. Например, для массива [−2, 1, −3, 4, −1, 2, 1, −5, 4] максимальным подмассивом будет [4, -1, 2, 1], а его сумма — 6.

Реализация

Для решения задачи нахождения максимального подмассива можно применить, как минимум, 3 подхода.

Грубая сила

Суть этого метода состоит в двойном переборе элементов массива. Поэтому его временная сложность составляет O(n^2).

// algorithms/sets/maximum-subarray/brute-force.js export default function bruteForce(arr) {   let maxStartIdx = 0   let maxLen = 0   let maxSum = null    for (let i = 0; i < arr.length; i++) {     let sum = 0     for (let j = 1; j <= arr.length - i; j++) {       sum += arr[i + (j - 1)]       if (!maxSum || sum > maxSum) {         maxSum = sum         maxStartIdx = i         maxLen = j       }     }   }    return arr.slice(maxStartIdx, maxStartIdx + maxLen) }

Тестирование

// algorithms/sets/maximum-subarray/__tests__/brute-force.test.js import bruteForce from '../brute-force'  describe('bruteForce', () => {   it('должен найти максимальные подмассивы методом грубой силы', () => {     expect(bruteForce([])).toEqual([])     expect(bruteForce([0, 0])).toEqual([0])     expect(bruteForce([0, 0, 1])).toEqual([0, 0, 1])     expect(bruteForce([0, 0, 1, 2])).toEqual([0, 0, 1, 2])     expect(bruteForce([0, 0, -1, 2])).toEqual([2])     expect(bruteForce([-1, -2, -3, -4, -5])).toEqual([-1])     expect(bruteForce([1, 2, 3, 2, 3, 4, 5])).toEqual([1, 2, 3, 2, 3, 4, 5])     expect(bruteForce([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toEqual([4, -1, 2, 1])     expect(bruteForce([-2, -3, 4, -1, -2, 1, 5, -3])).toEqual([4, -1, -2, 1, 5])     expect(bruteForce([1, -3, 2, -5, 7, 6, -1, 4, 11, -23])).toEqual([       7, 6, -1, 4, 11,     ])   }) })

Разделяй и властвуй

При использовании этого подхода нам также приходится перебирать массив дважды. Поэтому его временная сложность также составляет O(n^2).

// algorithms/sets/maximum-subarray/divide-conquer.js export default function divideConquer(arr) {   const dc = (idx, pick) => {     if (idx >= arr.length) {       return pick ? 0 : -Infinity     }      return Math.max(       // Вариант 1: берем текущий элемент и переходим к следующему       arr[idx] + dc(idx + 1, true),       // Вариант 2: не берем текущий элемент       pick ? 0 : dc(idx + 1, false),     )   }    return dc(0, false) }

Тестирование

// algorithms/sets/maximum-subarray/__tests__/divide-conquer.test.js import divideConquer from '../divide-conquer'  describe('dcMaximumSubarraySum', () => {   it("должен найти максимальные подмассивы методом 'Разделяй и властвуй'", () => {     expect(divideConquer([])).toEqual(-Infinity)     expect(divideConquer([0, 0])).toEqual(0)     expect(divideConquer([0, 0, 1])).toEqual(1)     expect(divideConquer([0, 0, 1, 2])).toEqual(3)     expect(divideConquer([0, 0, -1, 2])).toEqual(2)     expect(divideConquer([-1, -2, -3, -4, -5])).toEqual(-1)     expect(divideConquer([1, 2, 3, 2, 3, 4, 5])).toEqual(20)     expect(divideConquer([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toEqual(6)     expect(divideConquer([-2, -3, 4, -1, -2, 1, 5, -3])).toEqual(7)     expect(divideConquer([1, -3, 2, -5, 7, 6, -1, 4, 11, -23])).toEqual(27)   }) })

Динамическое программирование

Это лучшее с точки зрения времени выполнения решение, поскольку позволяет ограничиться одним перебором массива (O(n)).

// algorithms/sets/maximum-subarray/dynamic-programming.js export default function dynamicProgramming(arr) {   let maxSum = -Infinity   let sum = 0    let maxStartIdx = 0   let maxEndIdx = arr.length - 1   let currentStartIdx = 0    arr.forEach((item, idx) => {     sum += item      if (maxSum < sum) {       maxSum = sum       maxStartIdx = currentStartIdx       maxEndIdx = idx     }      if (sum < 0) {       sum = 0       currentStartIdx = idx + 1     }   })    return arr.slice(maxStartIdx, maxEndIdx + 1) }

Тестирование

// algorithms/sets/maximum-subarray/__tests__/dynamic-programming.test.js import dynamicProgramming from '../dynamic-programming'  describe('dynamicProgramming', () => {   it('должен найти максимальные подмассивы методом динамического программирования', () => {     expect(dynamicProgramming([])).toEqual([])     expect(dynamicProgramming([0, 0])).toEqual([0])     expect(dynamicProgramming([0, 0, 1])).toEqual([0, 0, 1])     expect(dynamicProgramming([0, 0, 1, 2])).toEqual([0, 0, 1, 2])     expect(dynamicProgramming([0, 0, -1, 2])).toEqual([2])     expect(dynamicProgramming([-1, -2, -3, -4, -5])).toEqual([-1])     expect(dynamicProgramming([1, 2, 3, 2, 3, 4, 5])).toEqual([       1, 2, 3, 2, 3, 4, 5,     ])     expect(dynamicProgramming([-2, 1, -3, 4, -1, 2, 1, -5, 4])).toEqual([       4, -1, 2, 1,     ])     expect(dynamicProgramming([-2, -3, 4, -1, -2, 1, 5, -3])).toEqual([       4, -1, -2, 1, 5,     ])     expect(dynamicProgramming([1, -3, 2, -5, 7, 6, -1, 4, 11, -23])).toEqual([       7, 6, -1, 4, 11,     ])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/maximum-subarray

Результат:

Комбинация сумм

Описание

• GeeksForGeeks

Дан набор чисел (candidates) (без дубликатов) и целевое число (target). Необходимо найти все уникальные комбинации чисел candidates, сумма которых равняется target.

Дополнительные условия:

• одно и тоже число candidates может использоваться многократно
• все числа (включая target) являются положительными
• решение не должно содержать повторений

Примеры

Дано: candidates = [2,3,6,7], target = 7,  Решение: [   [7],   [2,2,3] ]

Дано: candidates = [2,3,5], target = 8,  Решение: [   [2,2,2,2],   [2,3,3],   [3,5] ]

Объяснение

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

Пример дерева решений для candidates = [2, 3] и target = 6:

                0               /   \            +2      +3           /   \      \        +2       +3    +3       /  \     /  \     \     +2    ✘   ✘   ✘     ✓    /  \   ✓    ✘

Реализация

// algorithms/sets/combination-sum.js function combinationSumRecursive(   candidates,   remainingSum,   finalCombinations = [],   currentCombination = [],   startFrom = 0, ) {   if (remainingSum < 0) {     // Добавив кандидата, мы опустились ниже `0`.     // Это означает, что последний кандидат неприемлем     return finalCombinations   }    if (remainingSum === 0) {     // Если после добавления кандидата, мы получили `0`,     // нужно сохранить текущую комбинацию, поскольку     // это одно из искомых решений     finalCombinations.push(currentCombination.slice())      return finalCombinations   }    // Если мы пока не получили `0`, продолжаем добавлять оставшихся кандидатов   for (let i = startFrom; i < candidates.length; i++) {     const currentCandidate = candidates[i]      currentCombination.push(currentCandidate)      combinationSumRecursive(       candidates,       remainingSum - currentCandidate,       finalCombinations,       currentCombination,       i,     )      // Возвращаемся назад, исключаем текущего кандидата и пробуем другого     currentCombination.pop()   }    return finalCombinations }  export default function combinationSum(candidates, target) {   return combinationSumRecursive(candidates, target) }

Тестирование

// algorithms/sets/__tests__/combination-sum.test.js import combinationSum from '../combination-sum'  describe('combinationSum', () => {   it('должен найти все комбинации чисел для получения указанной суммы', () => {     expect(combinationSum([1], 4)).toEqual([[1, 1, 1, 1]])      expect(combinationSum([2, 3, 6, 7], 7)).toEqual([[2, 2, 3], [7]])      expect(combinationSum([2, 3, 5], 8)).toEqual([       [2, 2, 2, 2],       [2, 3, 3],       [3, 5],     ])      expect(combinationSum([2, 5], 3)).toEqual([])      expect(combinationSum([], 3)).toEqual([])   }) })

Запускаем тесты:

npm run test ./algorithms/sets/__tests__/combination-sum

Результат:

На сегодня это все, друзья. Увидимся в следующей части.

---

---

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩