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

Описание

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

В теории множеств прямое (декартово) произведение (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