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

Автор: admin от 19-01-2015, 13:53, посмотрело: 380

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

Содержание



  • 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]


Заключение


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

Источник: Хабрахабр

Категория: Программирование » Веб-разработка

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *