@NikitaWeb

Что такое совпадение множеств?

Нужно написать метод возвращающий список непохожих строк. Но для начала нужно понять, что написано в условии.
Дана целочисленная матрица, в которой имеется N строк, а число элементов в строке для каждой строки может быть любым, в том числе нулевым. Строки назовем похожими, если совпадают множества чисел, встречающихся в этих строках. Найти список строк этой матрицы максимальной размерности, в котором все строки попарно непохожи друг на друга. Из похожих строк в список включить строку с наибольшим номером. Порядок элементов в списке произвольный.

5d7e87024697a653374906.png
Первые 2 строки похожи друг на друга и непохожи на 3 строку. Ответом будет список из 2 и 3 строк.

К примеру метод должен пройти следующие тесты:
public void testMatrixNonSimilarRows() {
        int[][] matrix1 = {{}, {1, 2, 2, 4, 4}, {4, 2, 1, 4}, {3, 2, 4, 1, 5, 8}, {2, 3, 1, 4, 1, 5, 8}, {1, 8, 1, 1, 8}};
        List<int[]> nonSimilarRows1 = new MatrixNonSimilarRows(matrix1).getNonSimilarRows();
        assertEquals(4, nonSimilarRows1.size());
        assertTrue(nonSimilarRows1.contains(matrix1[0]));
        assertTrue(nonSimilarRows1.contains(matrix1[2]));
        assertTrue(nonSimilarRows1.contains(matrix1[4]));
        assertTrue(nonSimilarRows1.contains(matrix1[5]));
        int[][] matrix2 = {{1, 2, 2, 4, 4}, {4, 5, 1, 4}, {2, 4, 1}, {2, 4, 1, 4, 1, 2}, {1, 8, 1, 1, 8}};
        List<int[]> nonSimilarRows2 = new MatrixNonSimilarRows(matrix2).getNonSimilarRows();
        assertEquals(3, nonSimilarRows2.size());
        assertTrue(nonSimilarRows2.contains(matrix2[1]));
        assertTrue(nonSimilarRows2.contains(matrix2[3]));
        assertTrue(nonSimilarRows2.contains(matrix2[4]));
        int[][] matrix3 = {{}, {}};
        List<int[]> nonSimilarRows3 = new MatrixNonSimilarRows(matrix3).getNonSimilarRows();
        assertEquals(1, nonSimilarRows3.size());
        assertTrue(nonSimilarRows3.contains(matrix3[1]));
    }

Прошу помочь разобраться с условием. В частности, что понимается под похожими строками в данной ситуации?
  • Вопрос задан
  • 161 просмотр
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для каждой строки составляете множества чисел, которые в этой строке присутствуют . Для вашего примера:
1 2 2 4 4 => [1, 2, 4]
4 2 1 4 => [1, 2, 4]
3 2 4 1 5 8 => [1, 2, 3, 4, 5, 8]
Те строки, у которых эти множества полностью совпадают (первая и вторая строки в примере), считаются по условию похожими.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@Mercury13
Программист на «си с крестами» и не только
Совпадают множества — это, собственно, равны как множества. Другими словами, равны, если исключить повторы и отсортировать в каком-нибудь порядке.
Например, { 1, 2, 3 } = { 3, 3, 2, 1, 2, 1 }.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Как я понял условие:
Похожие два множества/две строки - это имеющие более 50% уникальных элементов множества.
Непохожие два множества/две строки - имеющие 50% (или менее процентов) уникальных элементов.
Непохож: создаём новый кластер.
Похож: добавляем элемент в похожий кластер.
-----------
Ответ на "Найти список строк этой матрицы максимальной размерности, в котором все строки попарно непохожи друг на друга.":
12244
324158

Ответ на "Из похожих строк в список включить строку с наибольшим номером.":
4214
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
MyWed Рязань
от 80 000 до 120 000 руб.
Spice IT Recruitment Москва
До 250 000 руб.
OptiSystems Краснодар
от 100 000 руб.
22 нояб. 2019, в 02:42
10000 руб./за проект
22 нояб. 2019, в 01:59
5000 руб./за проект
22 нояб. 2019, в 00:57
500 руб./за проект