Декартовое произведение Java

Рейтинг: 0Ответов: 1Опубликовано: 30.03.2023

Здраствуйте, у меня есть клас Set для задания и получения множеств и также класс Operations с методами множеств. Все методы моего класса (типа объединение множеств, декартового произведения...) должны выполняться над полученными на предыдущем шаге битовыми строками множеств. Все методы работают хорошо, но я не знаю как переписать Декартовое произведение(cartesian Product) по типу предыдущих методов, он работает на основе обичных чисел, а не битов. Помогите переписать этот метод. Класс Set

import java.util.Arrays;

public class Set<T> {

    private T[] set;

    public void setSet(T[] set) {
        this.set = (T[]) Arrays.stream(set).distinct().toArray();
    }

    public T[] getSet() {
        return set;
    }

    public Set(T[] array) {
        setSet(array);
    }

}

Класс Operations

import java.util.Arrays;

public class Operations<T> {

     // Перевод в битовую строку
     public String toBitString(Set set) {
         Object[] elements = set.getSet();
         int maxElement = Arrays.stream(elements).mapToInt(e -> (int) e).max().orElse(-1);
         int bitStringLength = maxElement + 1;
         StringBuilder sb = new StringBuilder();
         for (int i = 0; i < bitStringLength; i++) {
             if (Arrays.asList(elements).contains(i)) {
                 sb.append("1");
             } else {
                 sb.append("0");
             }
         }
         return sb.toString();
     }

     // Объединение множеств
     public T[] unionSets(Set s1, Set s2) {
         String bitString1 = toBitString(s1);
         String bitString2 = toBitString(s2);
         int maxLength = Math.max(bitString1.length(), bitString2.length());
         StringBuilder sb1 = new StringBuilder();
         StringBuilder sb2 = новый StringBuilder();
         for (int i = 0; i < maxLength; i++) {
             if (i < bitString1.length()) {
                 sb1.append(bitString1.charAt(i));
             } else {
                 sb1.append("0");
             }
             if (i < bitString2.length()) {
                 sb2.append(bitString2.charAt(i));
             } else {
                 sb2.append("0");
             }
         }
         String unionBitString = "";
         for (int i = 0; i < maxLength; i++) {
             int bit1 = Integer.parseInt(String.valueOf(sb1.charAt(i)));
             int bit2 = Integer.parseInt(String.valueOf(sb2.charAt(i)));
             unionBitString+=(bit1|bit2);
         }
         Object[] elements = new Object[unionBitString.length() - unionBitString.replace("1", "").length()];
         int index=0;
         for (int i = 0; i < unionBitString.length(); i++) {
             if (unionBitString.charAt(i) == '1') {
                 elements[index++] = i;
             }
         }
         return(T[]) new Set(elements).getSet();
     }

     // Проверка есть ли элемент в массиве
     public boolean contains(T elem, Object[] array) {
         for (T element : (T[]) array) {
             if (elem.equals(element)) {
                 return true;
             }
         }
         return false;
     }

     // Сечение множеств
     public T[] intersectionSets(Set s1, Set s2) {
         String bitString1 = toBitString(s1);
         String bitString2 = toBitString(s2);
         int maxLength = Math.max(bitString1.length(), bitString2.length());
         StringBuilder sb1 = new StringBuilder();
         StringBuilder sb2 = новый StringBuilder();
         for (int i = 0; i < maxLength; i++) {
             if (i < bitString1.length()) {
                 sb1.append(bitString1.charAt(i));
             } else {
                 sb1.append("0");
             }
             if (i < bitString2.length()) {
                 sb2.append(bitString2.charAt(i));
             } else {
                 sb2.append("0");
             }
         }
         String intersectionBitString = "";
         for (int i = 0; i < maxLength; i++) {
             int bit1 = Integer.parseInt(String.valueOf(sb1.charAt(i)));
             int bit2 = Integer.parseInt(String.valueOf(sb2.charAt(i)));
             intersectionBitString += (bit1 & bit2);
         }
         Object[] elements = new Object[intersectionBitString.length() - intersectionBitString.replace("1", "").length()];
         int index=0;
         for (int i = 0; i < intersectionBitString.length(); i++) {
             if (intersectionBitString.charAt(i) == '1') {
                 elements[index++] = i;
             }
         }
         return(T[]) new Set(elements).getSet();
     }

     // Разница множеств
     public T[] differenceSets(Set s1, Set s2) {
         String bitString1 = toBitString(s1);
         String bitString2 = toBitString(s2);
         int maxLength = Math.max(bitString1.length(), bitString2.length());
         StringBuilder sb1 = new StringBuilder();
         StringBuilder sb2 = новый StringBuilder();
         for (int i = 0; i < maxLength; i++) {
             if (i < bitString1.length()) {
                 sb1.append(bitString1.charAt(i));
             } else {
                 sb1.append("0");
             }
             if (i < bitString2.length()) {
                 sb2.append(bitString2.charAt(i));
             } else {
                 sb2.append("0");
             }
         }
         String differenceBitString = "";
         for (int i = 0; i < maxLength; i++) {
             int bit1 = Integer.parseInt(String.valueOf(sb1.charAt(i)));
             int bit2 = Integer.parseInt(String.valueOf(sb2.charAt(i)));
             differenceBitString += (bit1 & ~bit2);
         }
         Object[] elements = new Object[differenceBitString.length() - differenceBitString.replace("1", "").length()];
         int index=0;
         for (int i = 0; i < differenceBitString.length(); i++) {
             if (differenceBitString.charAt(i) == '1') {
                 elements[index++] = i;
             }
         }
         return(T[]) new Set(elements).getSet();
     }
// Симметричная разница множеств
     public T[] symmetricDiffSets(Set s1, Set s2) {
         String bitString1 = toBitString(s1);
         String bitString2 = toBitString(s2);
         int maxLength = Math.max(bitString1.length(), bitString2.length());
         StringBuilder sb1 = new StringBuilder();
         StringBuilder sb2 = новый StringBuilder();
         for (int i = 0; i < maxLength; i++) {
             if (i < bitString1.length()) {
                 sb1.append(bitString1.charAt(i));
             } else {
                 sb1.append("0");
             }
             if (i < bitString2.length()) {
                 sb2.append(bitString2.charAt(i));
             } else {
                 sb2.append("0");
             }
         }
         String symmetricDiffBitString = "";
         for (int i = 0; i < maxLength; i++) {
             int bit1 = Integer.parseInt(String.valueOf(sb1.charAt(i)));
             int bit2 = Integer.parseInt(String.valueOf(sb2.charAt(i)));
             symmetricDiffBitString += (bit1^bit2);
         }
         Object[] elements = new Object[symmetricDiffBitString.length() - symmetricDiffBitString.replace("1", "").length()];
         int index=0;
         for (int i = 0; i < symmetricDiffBitString.length(); i++) {
             if (symmetricDiffBitString.charAt(i) == '1') {
                 elements[index++] = i;
             }
         }
         return(T[]) new Set(elements).getSet();
     }

    // Декартовое произведение множеств
     public T[] cartesianProduct(Set s1, Set s2) {
         Object[] elements1 = s1.getSet();
         Object[] elements2 = s2.getSet();
         Object[] cartesianProduct = new Object[elements1.length * elements2.length];
         int index=0;
         for (Object element1 : elements1) {
             for (Object element2 : elements2) {
                 Object[] tuple = {element1, element2};
                 cartesianProduct[index++] = tuple;
             }
         }
         return (T[]) cartesianProduct;
     }
}

У меня есть пример для этого метода, но он работает неправильно

public T[] cartesianProductSets(Set s1, Set s2) {
    String bitString1 = toBitString(s1);
    String bitString2 = toBitString(s2);
    int maxLength = bitString1.length() + bitString2.length();
    String[] bitStrings = new String[maxLength];
    for (int i = 0; i < bitString1.length(); i++) {
        for (int j = 0; j < bitString2.length(); j++) {
            int index = i + j;
            String bitString = "";
            if (bitString1.charAt(i) == '1' && bitString2.charAt(j) == '1') {
                bitString = "1";
            } else {
                bitString = "0";
            }
            if (bitStrings[index] == null) {
                bitStrings[index] = bitString;
            } else {
                bitStrings[index] += bitString;
            }
        }
    }
    Object[] elements = new Object[1 << maxLength];
    int index = 0;
    for (int i = 0; i < bitStrings.length; i++) {
        String bitString = bitStrings[i];
        if (bitString == null) {
            break;
        }
        for (int j = 0; j < (1 << i); j++) {
            elements[index++] = Integer.parseInt(bitString, 2);
        }
    }
    return (T[]) new Set(elements).getSet();
}
java битовые-операции множества
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Декартово произведение двух множеств представляет собой массив/список пар элементов из каждого множества, поэтому непохоже, что здесь должны использоваться битовые строки.

Для простоты представим декартовое произведение как список списков, тогда можно получить результат при помощью Stream API (Stream::flatMap):

public List<List<T>> cartesianProductSets(Set set1, Set set2) {
    return Arrays.stream(set1.getSet())
        .flatMap(s1 -> Arrays.stream(set2.getSet())
            .map(s2 -> Arrays.asList(s1, s2))
        )
        .collect(Collectors.toList());
}

Вариант с битовыми строками:

public int[][] cartesianProductSets(Set set1, Set set2) {
    String bs1 = toBitString(set1);
    String bs2 = toBitString(set2);
    int[][] result = new int[(int) (bs1.chars().filter(c -> c == '1').count() * bs2.chars().filter(c -> c == '1').count())][2];

    for (int i = 0, r = 0, n = bs1.length(); i < n; i++) {
        if (bs1.charAt(i) == '0') continue;
        for (int j = 0, m = bs2.length(); j < m; j++) {
            if (bs2.charAt(j) == '0') continue;
            result[r++] = new int[]{i, j};
        }
    }

    return result;
}