data structures and algorithms. Part 6

Hello friends!

In this series of articles, we examine the data structures and algorithms presented in this wonderful repository. This is the sixth part of the series in which we begin to analyze algorithms.

Today we will talk about algorithms for working with sets.

The code presented in this and other articles in the series can be found in this repository.

With your permission, I will not talk about mathematical algorithms; the corresponding code, along with comments and tests, can be found in the directory math.

Interesting? Then I ask under cat.

Direct product

Description

In set theory, a Cartesian product is a mathematical operation that returns a set whose elements are all possible ordered pairs of elements of the original sets. Thus, for sets A And B a direct product is a set of ordered pairs (a, b)Where a ∈ A And b ∈ B.

Direct product A x B sets A={ x, y, z } And B={ 1, 2, 3 }:

Implementation

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

Testing

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

Let's run the tests:

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

Result:

Fisher-Yates shuffle

Description

Fisher-Yates shuffling is an algorithm for creating arbitrary permutations of a finite set, in other words, for randomly shuffling a set. A properly implemented algorithm is unbiased, so each permutation is generated with equal probability. The modern version of the algorithm is very efficient and requires time proportional to the number of elements of the set, and also does not require additional memory.

The basic procedure of the Fisher-Yates shuffle is similar to randomly drawing numbered notes from a hat or cards from a deck, one element at a time, until there are no more elements. The algorithm provides an efficient and rigorous method for such operations, guaranteeing an unbiased result.

Implementation

// 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
}

Testing

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

Let's run the tests:

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

Result:

The set of all subsets

Description

The set of all subsets (Boolean, exponential set) (power set) – a set consisting of all subsets of a given set
S (including the empty set and the set itself S); denoted by
P(S) or 2^S (since it corresponds to the set of mappings from S V {0, 1}).

For example, the set of all subsets of the set { x, y, z } will:

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

An illustration of the elements of this set, ordered by inclusion order:

Number of subsets

If S is a finite set containing |S| = n elements, then the number of subsets S equals |P(S)| = 2^n.

Algorithms

Binary Approach

The bits of each number in the binary representation range from 0 to 2^n indicate whether the corresponding element of the set should be included in the subset (1 – turn on, 0 – do not include). For example, for a set { 1, 2, 3 } binary number 0b010 means that only the second element of the set is included in the subset, i.e. 2.

Implementation

// 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
}

Testing

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

Recursive approach

With this approach, we recursively try to add the next element of the set to the subset, remember the subset, then remove the current element and take the next one.

Implementation

// 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
}

Testing

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

Cascade approach

This is probably the simplest way to create the set of all subsets.

Suppose we have a set originalSet = [1, 2, 3].

We start with an empty subset:

powerSets = [[]]

Adding the first element originalSet to all existing subsets:

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

Add a second element:

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

Add a third element:

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

And so for all elements originalSet. At each iteration the number of sets doubles, so in the end we get 2^n sets.

Implementation

// 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
}

Testing

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

Let's run the tests:

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

Result:

Permutations and combinations

Description

When the order of the elements is not important, it is a combination.

When the order of the elements is important, it is a permutation.

Rearrangements

Permutations without repetition

Permutation is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with itself S.

Example of string permutations ABC:

ABC ACB BAC BCA CBA CAB

Another example is the first three people in a race: you cannot be both first and second at the same time.

Number of options:

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

Implementation

// 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
}

Testing

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

Permutations with repetitions

When duplicates are allowed, we talk about permutations with repetitions.

An example of such a permutation would be the lock code 333.

Number of options:

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

Implementation

// 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
}

Testing

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

Let's run the tests:

npm run test ./algorithms/sets/permutations

Result:

Combinations

Combinations without repetitions

This is how lotteries work. The numbers are written one after another. The lucky combination wins, regardless of the order of the numbers.

Combination of numbers without repetitions:

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

Number of options:

Here n – the number of options to choose from, and r – the quantity we have chosen, no repetitions, the order is not important.

This combination is also called binomial coefficient.

Implementation

// 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
}

Testing

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

Combinations with repetitions

An example of such a combination is coins in your pocket: (5, 5, 5, 10, 10).

Another example is the five flavors of ice cream: banana, chocolate, lemon, strawberry And vanilla.

We can choose 3. How many options do we have?

We use symbols for tastes – { b, c, l, s, v }. Example options:

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

Number of options:

Here n — number of options to choose from, duplicates are allowed, order is not important.

Implementation

// 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
}

Testing

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

Let's run the tests:

npm run test ./algorithms/sets/combinations

Result:

Cheat sheets

Largest common subsequence

Description

The longest common subsequence (LCS) problem is the problem of finding a sequence that is a subsequence of several sequences (usually two). This is a classic computer science problem that has applications, in particular, in the task of comparing text files (the utility diff), as well as in bioinformatics. It is also widely used by version control systems such as Gitto reconcile changes to a collection of files.

A subsequence is different from a substring. For example, if there is a source sequence ABCDEFThat ACE will be a subsequence, but not a substring, but ABC will be both a subsequence and a substring.

Examples

• LOP for sequences ABCDGH And AEDFHR — ADH length 3
• LOP for sequences AGGTAB And GXTXAYB — GTAB length 4

Implementation

NOP can be implemented in at least two ways.

Recursive approach

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

Testing

// 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')
  })
})

Dynamic programming

This approach involves the use of a matrix (see the video on YouTube at the link at the beginning of the section).

// 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
}

Testing

// 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'])
  })
})

Let's run the tests:

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

Result:

Shortest general supersequence

Description

Shortest common supersequence (SCS) of two sequences X And Y is the shortest sequence containing X And Y.

Let's assume we have strings str1 And str2 and we need to find the shortest string containing both str1so str2.

This problem is closely related to the problem of finding the greatest common subsequence.

Examples

• CBS for strings geek And eke — geeke length 5
• CBS for strings AGGTAB And GXTXAYB — AGXGTXAYB length 9

Implementation

To implement the algorithm for finding the COS, you can use the algorithm for finding the NOP, which we discussed in the previous section.

// 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
}

Testing

// 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'])
  })
})

Let's run the tests:

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

Result:

Maximum subarray

Description

The maximum subarray problem is the problem of finding a subarray in a one-dimensional array a[1..n]whose numbers give the largest sum (the numbers must follow one after the other).

Source arrays usually contain negative and positive numbers, as well as 0. For example, for an array [−2, 1, −3, 4, −1, 2, 1, −5, 4] the maximum subarray will be [4, -1, 2, 1]and its sum is 6.

Implementation

To solve the problem of finding the maximum subarray, you can apply at least 3 approaches.

Brute force

The essence of this method is to double-iterate the array elements. Therefore its time complexity is 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)
}

Testing

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

Divide and conquer

With this approach we also have to iterate over the array twice. Therefore its time complexity is also 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)
}

Testing

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

Dynamic programming

This is the best solution in terms of execution time, since it allows you to limit yourself to one iteration of the array (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)
}

Testing

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

Let's run the tests:

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

Result:

Combination of amounts

Description

Given a set of numbers (candidates) (no duplicates) and target number (target). It is necessary to find all unique combinations of numbers candidatesthe sum of which is equal to target.

Additional terms:

• the same number candidates can be used repeatedly
• all numbers (including target) are positive
• the solution should not contain repetitions

Examples

Дано:
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]
]

Explanation

Since the goal is to get all possible results, not the best result or the number of results, we don't need dynamic programming. To solve the problem, a recursive approach is sufficient.

Example decision tree for candidates = [2, 3] And target = 6:

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

Implementation

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

Testing

// 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([])
  })
})

Let's run the tests:

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

Result:

That's all for today, friends. See you in the next part.

News, product reviews and competitions from the Timeweb.Cloud team – in our Telegram channel ↩