Как проверить есть ли заданное соответствие между элементами двух множеств правильно заданным отображением?

Question

[Александр]

Написать программу, которая в качестве входных данных получает два конечные множества и соответствие между элементами этих множеств и определяет, есть ли заданное соотвествие правильно заданным отображением.
Отображение с множества Х в множество У - каждому элементу с множества Х ставит в соответствие некоторый элемент с множества У.
По сути надо проверить нету ли какого-то элемента с первого множества Х для которого нету пары с множества У. Если есть, то соответствие не является отображением. Если нету, то это правильно заданное отображение.
Подскажите как это можно сделать? Надо использовать массивы или что-то другое? Какой алгоритм проверки?
Буду искренне благодарен!

Comments

[Wataru]

В каком формате задано "соответствие между элементами этих множеств" во входных данных?

[Александр]

Илья Николаевский, Не уточнено. По сути любым образом. Я новичок, и поэтому пока не очень понимаю какими образами можно задать соответствия.

[Wataru]

Александр, Ну вот без этого никак не решить. Можно для каждого X задать соответствующий Y - но это уже позволяет задавать только правильные отображения. Можно задать пары (x,y). Тогда надо проверить, что все x из X встречаются по одному разу. Это можно сделать так - выделить все X из пар в массив, отсортировать его и сравнить с множеством X, которое вы тоже читаете в массив и сортируете

[Александр]

Илья Николаевский, Можно примерный код для второго способа? Потому что я пока что не знаю как задавать пары и потом выделить все Х из пар в массив

[AVKor]

Роман,

подозреваю что в виде некой функции, внутри которой может быть что угодно, начиная от поиска соответствия по табличным данным и заканчивая банальной функцией y=f(x)

Бурда. В задаче требуется установить, является ли соответствие функцией.

[AVKor]

По сути надо проверить нету ли какого-то элемента с первого множества Х для которого нету пары с множества У.

Этого недостаточно.

[AVKor]

Роман,

вы Ванга?

Нет. Математик.

Тогда не несите чушь)))

Пшёл вон.

имеется ввиду функция как фрагмент программного кода

Бурда.

ну и про соответствие

Свои ссылки засунь подальше. Я дискретку 14 лет преподавал в университете.

Поэтому логично предположить, что в задаче по программированию под фразой (выделено жирным)

Для неуча "логично предположить" может быть всем чем угодно.

[AVKor]

Роман,

я теперь понимаю

Ты вообще ничего не понимаешь, ибо глуп.

[Александр]

Ребята, давайте жить дружно. Я здесь кое-что написал, а что дальше то делать?

#include <iostream>
using namespace std;

int main()
{
	int n, m;

	cout << "Enter the number of elements of the first set: ";
	cin >> n;
	
	int* arrX = new int[n];

	cout << "Enter the elements of the first set: " << endl;

	for (int i = 0; i < n; i++)
	{
		cout << i + 1 << ") ";
		cin >> arrX[i];
	}
	
	cout << "Enter the number of elements of the second set:";
	cin >> m;

	int* arrY = new int[m];

	cout << "Enter the elements of the second set: " << endl;

	for (int i = 0; i < m; i++)
	{
		cout << i + 1 << ") ";
		cin >> arrY[i];
	}

}

[Александр]

Вот как тупому (пока что) объясните

[Александр]

И как пользователь должен задать соотвествие?

[AVKor]

Роман,

позвольте поинтересоваться вашей научной степенью и научным званием?

Обойдёшься.

лучше быть глупцом, чем хамом с гипертрофированным комплексом собственной непогрешимости.

Ты свои комментарии перечитай (про Вангу, чушь и т.д). Так что не надо. И непогрешимость тут вообще ни при чём, это всего лишь знания.

надеюсь вас уже выперли из вашего университета, ибо человека с таким педагогическим подходом от студентов надо держать как можно дальше.

У меня подход индивидуальный. К наглецам типа тебя - вот такой. Другой педагогики у меня для тебя нет.

[AVKor]

Александр, В третьем комментарии Илья Николаевский уже написал, что надо делать.

Ваш код содержит не все нужные данные. Надо ещё составить пары (x,y).

Потом сделать проверку, как написал Илья Николаевский.

[AVKor]

Александр, Отображение (функция) из X в Y это подмножество декартова произведения XxY, т.е. множество пар (с определёнными свойствами). Так что вводите набор пар (x,y).

[AVKor]

Александр, вам следует игнорировать тот очередной бред, что накатал Роман. Он даже не понимает ни смысла задания, ни того, что я пишу.

[AVKor]

Роман,

Предлагаю спор на ... скажем 5000 руб (вроде и не много, но при этом и не мало).

Зажмёшь.

Вы напишите данное задание на codewars, а я дам на него решение, не противоречащее ни одному моему, высказанному выше утверждению. Если я не предоставлю решение, я проиграл, если предоставлю - вы.

Да я уже вижу решение, ниже. Неверное. И будет тоже неверное.

учитывая что вы по всей видимости никто как программист

Ты смешной. Ты вообще никто, в любом качестве.

готов даже оказать помощь в составлении тестирующей программной части данного задания, естественно под вашим чутким контролем и руководством (дабы избежать обмана с моей стороны)

Это будет болванская "тестирующая программная часть".

[AVKor]

Роман,

Ох, не обижайте меня, мы для этих целей позовем третье лицо, которому переведем по 5000 и который скинет обе ставки победителю. Ну или в банке аккредитив + нотариально заверенные условия сделки.

Да не нужны мне эти деньги. Да ещё к нотариусу идти, не смеши.

Вот именно из-за этих слов я и утверждаю что вы хамло)

Ты на себя посмотри. Повнимательнее.

А в этой моей фразе:

Бурда. В задаче требуется установить, является ли соответствие функцией.

никакого "хамства" нет, есть констатация того факта, что написана бурда, и я назвал её бурдой.

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

На меня не надо работать, тем более, людям, не способным понять условия тривиальной задачи. Иди дворником работать, хоть какая-то польза будет. "Пытаешься донести" ахинею. Мне она не нужна. А терминология - такая, какая есть. Не надо заменять её фальшивой.

Я же как человек с 3-я ступенями высшего образования (технического), и как практикующий программист вижу за данной фразой не только пары, но и функцию (в некоторых частных случаях), а так же систему уравнений/программный алгоритм (абсолютно во всех случаях)

Ты ничего не можешь видеть, поскольку слепой.

Как говорил мой научрук "о терминах не спорят, о них договариваются"

Иди и договаривайся с тем, кто ТС задание дал, договорщик. Ты ссылки тут давал, но в содержании того, на что ссылался, разобраться не в состоянии, так и продолжаешь нести пургу.

Как вы наверное проходили на философии (когда учились в аспирантуре, если вообще учились) одна из нынешних научных парадигм "... сомневаться во всем ..."

Ты бы хоть раз в себе засомневался, парадигматик хренов.

[AVKor]

Роман,

Но я не менее баран

Ты просто баран.

[AVKor]

Роман, Я буду краток: пшёл вон.

[Роман]

AVKor, вот пример реализации про который я говорил.

код

// даны 2 множества X и Y


// x - ученики
const X = [1,2,3,4];

// y - парты
const Y = [1,2];


// соответсвия делаем как программную функцию с 2-я аргументами
const conformity_1_pair = (x,y)=>{
	// соответствие задано набором пар
  // является правильным отображением
  const list = [
    [1,1],
    [2,1],
    [3,2],
    [4,2]
  ];
  return list.some(item=>(item[0]===x&&item[1]===y));
}

const conformity_1_func = (x,y)=>{
	// соответствие задано мат.функцией на интервале
  // является правильным отображением
  if(x<1 || x>4) return false;
  return y===Math.floor((x+1)/2);
}


const conformity_2_pair = (x,y)=>{
	// соответствие задано набором пар
  // не является правильным отображением
  const list = [
    [1,1],
    [2,1],
    [3,2],
    [4,2],
    [1,2]
  ];
  return list.some(item=>(item[0]===x&&item[1]===y))?1:0;
}

const conformity_2_func = (x,y)=>{
	// соответствие задано системой уравнений на интервале
  // не является правильным отображением
  if(x<1 && x>4) return false;
  
  return (y===Math.floor((x+1)/2)) || (x===1&&y===2);
}




// реализация функции проверки правильности отображения
function compare(listX, listY, conformityFunc){
   const res = [];
   listX.forEach(x=>listY.forEach(y=>{
   		const isPresent = conformityFunc(x,y);
      res[x]=(res[x]||0)+(isPresent?1:0);
      /* console.log(x,y,isPresent); */
   }));
   return res.every(v=>v===1);
}


// проверяем
console.log(compare(X, Y, conformity_1_pair)); // true - является правильным отображением
console.log(compare(X, Y, conformity_1_func)); // true - является правильным отображением
console.log(compare(X, Y, conformity_2_pair)); // false - не является правильным отображением
console.log(compare(X, Y, conformity_2_func)); // false - не является правильным отображением

Про минусы такого подхода я и сам знаю, про плюсы бесполезно тебе объяснять, так как ты глупец, не видящий
дальше собственного носа.

На случай если решишь докопаться. В данное решение одной строчкой кода можно добавить проверки на:
- является ли несимметричным соответствием
- является ли инъективным соответствием
- является ли соръективным соответствием
- является ли соответствие биекцией

В общем усрись и захлопнись. Бесишь своей твердолобостью невообразимо

[AVKor]

Роман,

про плюсы бесполезно тебе объяснять, так как ты глупец, не видящий
дальше собственного носа.

В общем усрись и захлопнись.

Иди в жопу, дурень.

[AVKor]

Роман, Тебе на Канатчикову дачу. Иди пролечись.

[AVKor]

Роман, Фантазия у тебя столь же слабая, что и интеллект (если его вообще так можно назвать). И психология дошкольника.

[AVKor]

Роман, Ты долго пытался что-то вымучить, но вымучил только УГ.

[AVKor]

Роман, Ты эхолалией страдаешь, болезный.

[Роман]

AVKor, оставляю тебя наедине с твоим монологом.

Answer 1

[AVKor]

Вот код на Ruby:

#!/usr/bin/env ruby
# frozen_string_literal: true

require 'set'

def relation_is_func?(xset, yset, rset)
  x_is_correct = (rset.map(&:keys).flatten - xset.to_a).empty?
  y_is_correct = (rset.map(&:values).flatten - yset.to_a).empty?
  r_is_correct = rset.map(&:keys).flatten.sort == xset.to_a.sort
  x_is_correct && y_is_correct && r_is_correct ? 'Function.' : 'Not function.'
end

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 2 => 'b' }, { 1 => 'b' }, { 3 => 'b' }, { 4 => 'a' }]
relation_is_func?(x, y, r) #=> "Function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'b' }, { 2 => 'b' }, { 3 => 'b' }, { 4 => 'b' }, { 2 => 'c' }]
relation_is_func?(x, y, r) #=> "Not function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'c' }, { 2 => 'a' }, { 4 => 'b' }]
relation_is_func?(x, y, r) #=> "Not function."

Примечания:

1. Заморачиваться с вводом данных я не стал, просто захардкодил три примера.
   
2. Реализовать упорядоченные пары можно разными способами, я использовал хэши. Можно было реализовать и по-другому (Struct, например).
   
3. Для множеств я использовал Set.
   
4. Проверка корректности входных данных реализована частично. Можете подумать, что стоит добавить.
   
5. В примерах: x - множество X; y - множество Y; r - отношение между X и Y (для которого надо выполнить проверку того, что это функция).
   
6. Запустить на выполнение можно так: сохранить в файл, допустим, test.rb и в терминале выполнить команду: irb test.rb
   

На C++ реализуйте сами.

Comments

[Александр]

Можете кратко объяснить в чем смысл кода? Что этот код делает?
А то это очень сложно понять

[AVKor]

Александр, Написал комментарии:

#!/usr/bin/env ruby
# frozen_string_literal: true

require 'set'

# в комментариях через x, y обозначаются элементы множеств X, Y,
# а в коде вместо X используется имя переменной x, чтобы вывод
# скрипта не замусоривался предупреждениями о том, что изменено
# значение константы (в Ruby имена с заглавных букв используются
# для констант).

def relation_is_func?(xset, yset, rset)
  # проверка того, что в отношении R (которое представляет собой
  # множество упорядоченных пар (x,y)) "задействованы" все элементы
  # x из X, причём ровно по одному разу.
  # получаем это так:
  # rset.map(&:keys) даёт нам массив из одноэлементных массивов
  # ключей. для первого примера ниже он получается таким:
  # [[2], [1], [3], [4]]
  # полученный массив из массивов мы делаем "плоским"
  # (используя метод Array#flatten), получаем соответственно массив
  # [2, 1, 3, 4]
  # методом Set#to_a преобразуем множество X в массив. из первого
  # примера ниже это даёт нам такой массив:
  # [1, 2, 3, 4]
  # rset.map(&:keys).flatten - xset.to_a
  # даёт нам разность полученных массивов, т.е. те элементы первого
  # массива, которых нет во втором массиве. для первого примера
  # она пуста:
  # []
  # метод Array#empty? делает проверку того, что эта разность пустая.
  # т.е. мы убеждаемся в том, что в тех парах (x,y), что принадлежат
  # отношению R, нет таких x, которые не содержатся во множестве X.
  x_is_correct = (rset.map(&:keys).flatten - xset.to_a).empty?
  # аналогичная процедура для множества Y: убеждаемся в том, что
  # в тех парах (x,y), что принадлежат  отношению R, нет таких y,
  # которые не содержатся во множестве Y. поскольку упорядоченные
  # пары (x,y) у нас представлены хэшами { x => y }, то вместо ключей
  # тут мы должны брать значения хэшей:
  # rset.map(&:values)
  # остальное аналогично вышеописанному
  y_is_correct = (rset.map(&:values).flatten - yset.to_a).empty?
  # метод Array#sort сортирует массив.
  # для второго примера ниже получаем:
  # rset.map(&:keys).flatten.sort даёт нам
  # [1, 2, 2, 3, 4]
  # xset.to_a.sort даёт
  # [1, 2, 3, 4]
  # здесь: rset.map(&:keys).flatten.sort == xset.to_a.sort
  # мы проверяем, равны ли массивы. для второго примера они
  # не равны (элементу 2 из X сопоставлены 2 элемента из Y, b и c),
  # для третьего примера тоже равенства не получается,
  # rset.map(&:keys).flatten.sort даёт нам
  # [1, 2, 4]
  # т.е. элементу 3 из X у нас ничего не сопоставлено в Y, массивы
  # не равны.
  r_is_correct = rset.map(&:keys).flatten.sort == xset.to_a.sort
  # проверка того, что все три условия выполняются.
  # если истина, то получаем 'Function.',
  # в противном случае 'Not function.'
  x_is_correct && y_is_correct && r_is_correct ? 'Function.' : 'Not function.'
end

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
# отношение R между X и Y задано как множество хэшей. Хэши состоят
# в данном случае из одной пары "ключ - значение". В качестве ключа
# выступает элемент X, в качестве значения - элемент Y. Таким образом,
# получаем реализацию упорядоченой пары (x,y).
r = Set[{ 2 => 'b' }, { 1 => 'b' }, { 3 => 'b' }, { 4 => 'a' }]
# проверка того, что отношение R есть отображение (функция).
relation_is_func?(x, y, r) #=> "Function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'b' }, { 2 => 'b' }, { 3 => 'b' }, { 4 => 'b' }, { 2 => 'c' }]
relation_is_func?(x, y, r) #=> "Not function."

x = Set[1, 2, 3, 4]
y = Set['a', 'b', 'c', 'd', 'e']
r = Set[{ 1 => 'c' }, { 2 => 'a' }, { 4 => 'b' }]
relation_is_func?(x, y, r) #=> "Not function."