JavaScript: структуры данных и алгоритмы. Часть 604.11.2024 11:16

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

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

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

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

С вашего позволения, я не буду рассказывать о математических алгоритмах, соответствующий код вместе с комментариями и тестами можно найти в директории 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

Результат:

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

Описание

Когда порядок элементов не важен, это комбинация (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-канале ↩

© Habrahabr.ru