@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]));
    }

Прошу помочь разобраться с условием. В частности, что понимается под похожими строками в данной ситуации?
  • Вопрос задан
  • 218 просмотров
Решения вопроса 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
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы