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

Question

[NikitaWeb]

Нужно написать метод возвращающий список непохожих строк. Но для начала нужно понять, что написано в условии.

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

Первые 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]));
    }

Прошу помочь разобраться с условием. В частности, что понимается под похожими строками в данной ситуации?

Answer 1

[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]
Те строки, у которых эти множества полностью совпадают (первая и вторая строки в примере), считаются по условию похожими.

Comments

[Владимир Олохтонов]

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

[Roman]

Владимир Олохтонов, у Rsa97 тут был дубль ответа.

Answer 2

[Mercury13]

Совпадают множества — это, собственно, равны как множества. Другими словами, равны, если исключить повторы и отсортировать в каком-нибудь порядке.
Например, { 1, 2, 3 } = { 3, 3, 2, 1, 2, 1 }.

Answer 3

[AVKor]

Тут.

Answer 4

[xmoonlight]

Как я понял условие:
Похожие два множества/две строки - это имеющие более 50% уникальных элементов множества.
Непохожие два множества/две строки - имеющие 50% (или менее процентов) уникальных элементов.
Непохож: создаём новый кластер.
Похож: добавляем элемент в похожий кластер.
-----------
Ответ на "Найти список строк этой матрицы максимальной размерности, в котором все строки попарно непохожи друг на друга.":
12244
324158

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