Декартово произведение для чайников
June 08, 2020
Как-то для работы мне потребовалось перебирать все возможные варианты перестановок некоторого количества множеств до тех пор, пока не найдётся нужное. Для этого существует математическая операция Прямого, или декартова, произведения (Cartesian product). Похожую задачу могут дать и на собеседовании, явно сказав, что нужно написать функцию для нахождения декартова произведения, так и предложив найти все возможные сочетания некоторых множеств.
Немного математики
Множество - одно из фундаментальных понятий математики, просто говоря — набор каких-либо объектов. В математике обычно обозначаются большими латинскими буквами , а его элементы записываются в фигурных скобках, к примеру, множество натуральных чисел:
В программировании под множеством может пониматься как множество (Set как структура данных, содержащая неупорядоченный набор уникальных значений) так и просто список/массив/слайс/etc.
Для двух множеств A и B декартово произведение обозначается как и определяется как:
Декартово произведение — это умножение двух множеств, формирующее все возможные упорядоченные пары элементов исходных множеств. Первый элемент пары принадлежит первому множеству, второй — второму. Для примера:
Примеры для двух множеств
Решение для двух множеств элементарно, как правило, нас интересует декартово произведение N множеств, но для полноты картины приведу и этот пример.
Typescript
const product = (arr1: any[], arr2: any[]) => {
const result = []
for (let el2 of arr2) {
for (let el1 of arr1) {
result.push([el1, el2])
}
}
return result
}
console.log(product([1, 2], [3, 4]))
// [ [ 1, 3 ], [ 2, 3 ], [ 1, 4 ], [ 2, 4 ] ]Go
package main
import "fmt"
func product(arr1, arr2 []int) [][]int {
result := make([][]int, 0, len(arr1)*len(arr2))
for _, el2 := range arr2 {
for _, el1 := range arr1 {
result = append(result, []int{el1, el2})
}
}
return result
}
func main() {
fmt.Println(product([]int{1, 2}, []int{3, 4}))
// [[1 3] [2 3] [1 4] [2 4]]
}Как видим, просто два цикла — скука, поехали дальше.
Программируем классические (относительно) варианты
Для проверки того, что мы пишем, возьмём результат работы функции прямого произведения из стандартной библиотеки питона:
from itertools import product
print(list(product([1, 2], [3, 4])))
# [(1, 3), (1, 4), (2, 3), (2, 4)]Пример на TypeScript в функциональном стиле
const product = (lists: any[][]) => {
return lists.reduce(
(acc, list) =>
acc
.map(x => list.map(y => x.concat(y)))
.reduce((acc, list) => acc.concat(list), []),
[[]],
)
}
console.log(
product([
[1, 2],
[3, 4],
]),
)
// [ [ 1, 3 ], [ 2, 3 ], [ 1, 4 ], [ 2, 4 ] ]Пример на TypeScript в императивном стиле
const product = (lists: any[][]) => {
let i,
j,
l,
m,
a1,
o = []
if (!lists || lists.length == 0) return lists
a1 = lists.splice(0, 1)[0] // первый массив lists
lists = product(lists)
for (i = 0, l = a1.length; i < l; i++) {
if (lists && lists.length)
for (j = 0, m = lists.length; j < m; j++) o.push([a1[i]].concat(lists[j]))
else o.push([a1[i]])
}
return o
}
console.log(
product([
[1, 2],
[3, 4],
]),
)
// [ [ 1, 3 ], [ 2, 3 ], [ 1, 4 ], [ 2, 4 ] ]Пример на Go
package main
import "fmt"
func Product(lists ...[]int) [][]int {
return product(0, lists)
}
func product(idx int, lists [][]int) [][]int {
var result [][]int
if idx == len(lists) {
result = append(result, []int{})
} else {
for _, el := range lists[idx] {
for _, list := range product(idx+1, lists) {
list = append(list, el)
result = append(result, list)
}
}
}
return result
}
func main() {
fmt.Println(Product([]int{1, 2}, []int{3, 4}))
// [[3 1] [4 1] [3 2] [4 2]]
}С основными примерами — всё. В следующий понедельник, почему в моём проекте эти «классические» реализации не прокатили, и что я с этим делал.