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

В. Дунаев

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

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

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

Функции 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 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 } //**************************************************************** function showset(a,x,y,z){ // a - массив одномерный if (!x) x=0; if (!y) y=0; if (!z) z=0; var h=Math.min(10,a.length); var str="<textarea rows="+h+ " style='position:absolute;left:"+x+";top:"+y+";zIndex:"+z+"'>"+ a.join("\n"); document.write(str+'< /textarea>') // здесь перед < поставлен пробел, который надо удалить }

Ниже приведен пример. Чтобы выполнить этот код и посмотреть результат, щелкните на кнопке

// Бинарное отношение: 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","b") arel[7]=new Array("z","d") // Подмножество : ax=new Array("x","y") // Замыкание Галуа: a=Rn(Rn(ax,arel),arel,1) showset(a,100,400,1) // вывод результата