Множества и отношения

Работа с массивами как с множествами

Здесь представлены несколько функций на JavaScript для работы с массивами как с множествами: пересечение, уникализация элементов, декартово произведение, соответствия Галуа.
Как известно, конечные множества в программах можно представлять в виде массивов. Принципиальное отличие конечного множества от массива состоит в том, что оно содержит только различающиеся (уникальные элементы).
Бинарное отношение можно представить как двумерный массив, состоящий из двухэлементных одномерных массивов. В каждом таком двухэлементном массиве содержится пара элементов, находящихся в рассматриваемом отношении.

Ниже перечислены функции, коды которых приведены на данной странице:

across(массив1, массив2) — пересечение массивов (массив, содержащий элементы, входящие одновременно в оба массива)
auniq(массив) — возвращает массив уникальных элементов из заданного массива. Очевидно, множества представляются массивами. Однако непустое множество должно содержать различающиеся элементы.
DP(массив1, массив2) — декартово произведение двух массивов
R1(элемент, отношение, направление) — возвращает массив всех элементов, находящихся в отношении с заданным элементом; если направление не указано, то предполагается прямое отношение, иначе — обратное; отношение задается двумерным массивом, элементы которого задаются в виде двухэлементных массивов; данная функция используется в функции Rn() (см. ниже)
Rn(массив, отношение, направление) — возвращает массив всех элементов, находящихся в отношении со всеми элементами из заданного массива ; если направление не указано, то предполагается прямое отношение, иначе — обратное; отношение задается двумерным массивом, элементы которого задаются в виде двухэлементных массивов; данная функция использует функцию R1() (см. выше)

Функции R1() и Rn() могут использоваться для определения соответствий Галуа между подмножествами множеств, элементы которых находятся в заданном бинарном отношении.
Например, пусть задано некоторое бинарное отношение R между множествами A и B (отношение задано в виде двумерного массива). Тогда замыкание Галуа подмножества X множества A есть множество (массив) CX, возвращаемое следующим выражением:
CX=Rn(Rn(X, R), R,1)

Ниже приводятся определения функций:
/*****************************/ function across(a1, a2){ /* Пересечение массивов (массив, содержащий элементы, входящие одновременно в оба массива) a1, a2 - массивы одномерные */ var arez=new Array(); if (a1.length==0 || a2.length==0) return arez var i=0,j; while(i<a1.length){ // для каждого элемента a1 j=0 while (j<a2.length){ if (a1[i]==a2[j]) { arez.push(a1[i]); break; } j++; } i++; } return arez } /*****************************/ function auniq(a){ /* Возвращает массив уникальных элементов из заданного массива a - массив одномерный*/ var arez=new Array() if (a.length==0) return arez arez[0]=a[0] var i=1,j,is_element; while (i<a.length){ is_element=0 j=0 while (j<arez.length) { if ((a[i]==arez[j])){ is_element=1 break } j++ } if (is_element==0) arez.push(a[i]) i++ } return arez } /*****************************/ function R1(x,a,mod){ /* Возвращает массив всех элементов, находящихся в отношении с заданным элементом; если направление не указано, то предполагается прямое отношение, иначе — обратное a - двумерный массив, элементами которого являются массивы длины 2 mod - если пусто, то прямая связь, иначе - обратная */ var arez=new Array() var m=0, k=1 if (mod) { m=1 k=0 } i=0 while (i<a.length){ if (x==a[i][m]) arez.push(a[i][k]) i++ } return arez } /*****************************/ function Rn(ax,a,mod){ /* Возвращает массив всех элементов, находящихся в отношении со всеми элементами из заданного массива ; если направление не указано, то предполагается прямое отношение, иначе — обратное ax - одномерный массив a - двумерный массив, элементами которого являются массивы длины 2 mod - если пусто, то прямая связь, иначе - обратная*/ var ay=new Array() // массив образов (множеств) var i=0 if (!ax) { if (!mod){ while (i<a.length){ arez.push(a[i][1]) i++ } }else{ while (i<a.length){ arez.push(a[i][0]) i++ } } return arez } while (i<ax.length){ ay.push(R1(ax[i],a,mod)) i++ } i=0 arez=ay[0] while (i<ay.length-1){ arez=across(arez,ay[i+1]) i++ } return arez } /*****************************/ function DP(a1,a2){ /* Декартово произведение a1, a2 - массивы одномерные */ var arez=new Array() var i=0, j=0, x; while (i<a1.length){ j=0 while (j<a2.length){ x=new Array(a1[i],a2[j]) arez.push(x) j++ } i++ } return arez }

Пример 1. Вычисление декартового произведения двух массивов,содержащих буквы

a1= new Array("x","y","z")
a2= new Array("a","b","c","d")
// Декартово произведение:
a=DP(a1,a2)

Пример 2. Замыкание Галуа для бинарного отношения, заданного двумерным массивом arel, содержащим буквы

// Бинарное отношение:
arel=new Array()
arel[0]=new Array("x","a")
arel[1]=new Array("x","b")
arel[2]= new Array("y","c")
arel[3]=new Array("y","b")
arel[4]=new Array("y","d")
arel[5]=new Array("x","d")
arel[6]=new Array("z","a")
arel[7]=new Array("z","d")
// Подмножество :
ax=new Array("x","z")
// Замыкание Галуа:
a=Rn(Rn(ax,arel),arel,1)

Чтобы выполнить приведённые выше коды примеров и посмотреть результаты, щелкните на соответствующей кнопке