Minimalna różnica symetryczna (xor) n zbiorów równa zbiorowi

0

Mamy:
zbiór A zawierający p elementów: A = {x 1, x 2, ..., x p}
N zbiorów B, z których każdy jest jakimś podzbiorem A różnym od A. Każdy zbiór jest inny.
Zbiór C, określony podzbiór A.
Zadanie: znaleźć dowolny najmniejszy zbiór D, składający się ze zbiorów B oraz opcjonalnie elementów C, taki że różnica symetryczna wszystkich zbiorów B będących elementami D wraz z wybranymi elementami C jest równa zbiorowi C, a jednocześnie |D| < |C|. Zbiór D może nie istnieć.

Przykład:
A = {1, 2, 3, 4, 5, 6, 7, 8}
B 1 = {3, 4, 6, 7}; B 2 = {4, 6, 7, 8}; B 3 = {1, 2, 3, 5}
C = {1, 2, 3, 4, 5, 6, 7}
|C| = 7

Rozwiązanie:
D = {B 1, B 3, 3}
|D| = 3

B 1 ^ B 3 = {1, 2, 4, 5, 6, 7}
{1, 2, 4, 5, 6, 7} ^ {3} = C

lub
D = {B 2, B 3, 8}
B 2 ^ B 3 = {1, 2, 3, 4, 5, 6, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8} ^ {8} = C

Jakim algorytmem to rozwiązać? Bruteforce - sprawdzanie najpierw wszystkich B, potem wszystkich par B, potem wszystkich trójek... oczywiście działa, ale jest bardzo wolne.

0

Źle użyłem indeksów dolnych, przepraszam, tutaj korekta

Mamy:
zbiór A zawierający p elementów: A = {x1, x2, ..., xp}
N zbiorów B, z których każdy jest jakimś podzbiorem A różnym od A. Każdy zbiór jest inny.
Zbiór C, określony podzbiór A.
Zadanie: znaleźć dowolny najmniejszy zbiór D, składający się ze zbiorów B oraz opcjonalnie elementów C, taki że różnica symetryczna wszystkich zbiorów B będących elementami D wraz z wybranymi elementami C jest równa zbiorowi C, a jednocześnie |D| < |C|. Zbiór D może nie istnieć.

Przykład:
A = {1, 2, 3, 4, 5, 6, 7, 8}
B1 = {3, 4, 6, 7}; B2 = {4, 6, 7, 8}; B3 = {1, 2, 3, 5}
C = {1, 2, 3, 4, 5, 6, 7}
|C| = 7

Rozwiązanie:
D = {B1, B3, 3}
|D| = 3

B1 ^ B3 = {1, 2, 4, 5, 6, 7}
{1, 2, 4, 5, 6, 7} ^ {3} = C

lub
D = {B2, B3, 8}
B2 ^ B3 = {1, 2, 3, 4, 5, 6, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8} ^ {8} = C

Jakim algorytmem to rozwiązać? Bruteforce - sprawdzanie najpierw wszystkich B, potem wszystkich par B, potem wszystkich trójek... oczywiście działa, ale jest bardzo wolne.

0
  1. sortujesz zbiór A
  2. sortujesz zbiór B
  3. dopóki w A są elementy oraz w B są elementy ...
  4. jeżeli element na początku A jest mniejszy od elementu na początku B to przenosisz element z A do C
  5. w przeciwnym przypadku jeżeli element na początku A jest większy od elementu na początku B to przenosisz element z B do C
  6. w przeciwnym przypadku usuwasz element z A oraz usuwasz element z B
  7. ... koniec pętli
  8. przenieś resztę elementów z A do C
  9. przenieś resztę elementów z B do C
0
_13th_Dragon napisał(a):

sortujesz zbiór A

  1. sortujesz zbiór B
  2. dopóki w A są elementy oraz w B są elementy ...
  3. jeżeli element na początku A jest mniejszy od elementu na początku B to przenosisz element z A do C
  4. w przeciwnym przypadku jeżeli element na początku A jest większy od elementu na początku B to przenosisz element z B do C
  5. w przeciwnym przypadku usuwasz element z A oraz usuwasz element z B
  6. ... koniec pętli
  7. przenieś resztę elementów z A do C
  8. przenieś resztę elementów z B do C

To chyba jakaś pomyłka... nie widzę żadnego związku z problemem.
O ile dobrze zrozumiałem, opisałeś jeden z możliwych algorytmów do obliczenia różnicy symetrycznej (xor) dwóch zbiorów, A i B, gdzie wynikiem jest C.

0
_13th_Dragon napisał(a)

Zgadza się, zostało sprawdzić przynależność, czy na to też potrzebujesz algorytm?

Sprawdzić przynależność? Czego? Wszystkich możliwych zbiorów zawierających zbiory B o mocy < |C|? Czyli oczywisty bruteforce, o którym napisałem na końcu posta.
Pytaniem jest to, czy istnieje szybszy algorytm niż bruteforce.

0

xor jest symetryczny, więc dla:

B1 = {3, 4, 6, 7}; B2 = {4, 6, 7, 8}; B3 = {1, 2, 3, 5}
C = {1, 2, 3, 4, 5, 6, 7}

D1 = C^B2^B3 = {8}
D2 = C^B1^B3 = {3}
D3 = C^B1^B2 = {1,2,4,5,8}

1 użytkowników online, w tym zalogowanych: 0, gości: 1