Бинарные операции над множествами

В данной публикации я проведу алгоритмизацию операций над массивами, а так же расскажу о самих операциях.

Содержание

• I. Пересечение массивов
• II. Разность массивов
• III. Объединение массивов
• IV. Симметрическая разность массивов
• Заключение

I. Пересечение массивов

Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function Intersection(A, B)
{
	var m = A.length, n = B.length, c = 0, C = [];
	for (var i = 0; i < m; i++)
	{ 
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < n) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j != n && k == c) C[c++] = A[ i ];
	}
	return C;
}

Пример:

Intersection ([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [1,2,7]

II. Разность массивов

Разность двух массивов A и B — это массив с элементами A, не совпадающими с элементами B, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function Diff(A, B)
{
	var M = A.length, N = B.length, c = 0, C = [];
	for (var i = 0; i < M; i++)
	{
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < N) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j == N && k == c) C[c++] = A[ i ];
	}
	return C;
}

Пример:

Diff([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [3,9]
Diff([4,5,7,2,1,5], [1,2,3,7,9]); //На выходе [4,5]

III. Объединение массивов

Объединение двух массивов A и B — это массив с элементами A и элементы массива B, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function Sum(A, B)
{
	var M = A.length, N = B.length, count = 0, C = [];
	C = A;
	count = M;
	var cnt = 0;
	for (var i=0;i<N;i++)
	{ 
		var plus = false;
		for (var j=0;j<M;j++)
			if (C[j] == B[i]) {plus = true; break;}
		if (plus === false) C[count++] = B[i];
	}
	return C;
}

Пример:

Sum([1,2,3,7,9],[4,5,7,2,1,5]); //На выходе [1,2,3,7,9,4,5]
Sum([4,5,7,2,1,5],[1,2,3,7,9]); //На выходе [4,5,7,2,1,5,3,9]

IV. Симметрическая разность массивов

Симметрическая разность двух массивов A и B — это такой массив, куда входят все те элементы первого массива, которые не входят во второй массив, а также те элементы второго массива, которые не входят в первый массив.

Сложность алгоритма O(2m*n), где m и n — длины входных массивов A и B соответственно.

По сути это вычитание массивов, сначала A из B, затем B из A.

function SymmetricDiff(A,B)
{
	var M = A.length, N = B.length, c = 0, C = [];
	for (var i = 0; i < M; i++)
	{
		var j = 0, k = 0;
		while (B[j] !== A[ i ] && j < N) j++;
		while (C[k] !== A[ i ] && k < c) k++;
		if (j == N && k == c) C[c++] = A[ i ];
	}
	for (var i = 0; i < N; i++)
	{
		var j = 0, k = 0;
		while (A[j] !== B[ i ] && j < M) j++;
		while (C[k] !== B[ i ] && k < c) k++;
		if (j == M && k == c) C[c++] = B[ i ];
	}
	return C;
}

Пример:

SymmetricDiff([1,2,3,7,9],[4,5,7,2,1,5]);//На выходе [3,9,4,5]
SymmetricDiff([1,2,3,4,5],[3,4,5,6,7]); //На выходе [1,2,6,7]

Заключение

Живой пример ^[1] на примере друзей вконтакте. При вводе ссылок на страницы пользователей вконтакте сервис выдает все пересечения массивов друзей пользователей (пересечения — это общие друзья пользователей).

Автор: dooza

Источник ^[2]