Привет, друзья!
В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это шестая часть серии, в которой мы начинаем разбирать алгоритмы.
Сегодня мы поговорим об алгоритмах для работы с множествами.
Код, представленный в этой и других статьях серии, можно найти в этом репозитории.
С вашего позволения, я не буду рассказывать о математических алгоритмах, соответствующий код вместе с комментариями и тестами можно найти в директории 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
.
abc |
Подмножество | |
---|---|---|
0 |
000 |
{} |
1 |
001 |
{c} |
2 |
010 |
{b} |
3 |
011 |
{c, b} |
4 |
100 |
{a} |
5 |
101 |
{a, c} |
6 |
110 |
{a, b} |
7 |
111 |
{a, b, c} |
Реализация
// 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
Результат:
Перестановки и комбинации
Описание
Когда порядок элементов не важен, это комбинация (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
Результат:
Шпаргалки
Наибольшая общая подпоследовательность
Описание
Задача нахождения наибольшей общей подпоследовательности (НОП) (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
Результат:
Максимальный подмассив
Описание
Задача максимального подмассива (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
Результат:
Комбинация сумм
Описание
Дан набор чисел (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-канале ↩