Wszystkie części wspólne podzbiorów, All common sequences of subarrays Opcje

[sabat24]

Interesuje mnie, czy jest gotowy algorytm (na wzór Longest common substring), który operowałby bezpośrednio na tablicach z nieposortowanymi elementami? Przykład dużo bardziej rozjaśni, czego poszukuję:
Wejście:

[PHP] pobierz, plaintext 
array
'bo_1' => 
  array
    0 => 'bo_5'
    1 => 'bo_1'
'bo_5' => 
  array
    0 => 'bo_1'
    1 => 'bo_5'
    2 => 'bo_17'
'bo_17' => 
  array
    0 => 'bo_17'
    1 => 'bo_18'
'bo_19' => 
  array
    0 => 'bo_19'
    1 => 'bo_1'
    2 => 'bo_5'
    3 => 'bo_17'
[PHP] pobierz, plaintext 

Wyjście

[PHP] pobierz, plaintext 
array
0 =>
  array
    0 => 'bo_19'
    1 => 'bo_1'
    2 => 'bo_5'
    3 => 'bo_17'
1 =>
  array
    0 => 'bo_17'
    1 => 'bo_18'
[PHP] pobierz, plaintext 

Próbowałem to wykonać za pomocą array_diff i rekurencji, ale dostawałem nieunikalne wyniki i nie zawsze poprawne.

Ten post edytował sabat24 11.03.2015, 09:52:07

[sabat24]

Po poprawce zwraca także zbiór niepoprawny:

[PHP] pobierz, plaintext 
array
  0 => 
    array
      0 => string 'bo_5' (length=4)
      1 => string 'bo_1' (length=4)
      2 => string 'bo_17' (length=5)
      3 => string 'bo_19' (length=5)
  1 => 
    array
      0 => string 'bo_1' (length=4)
      1 => string 'bo_5' (length=4)
      2 => string 'bo_18' (length=5)
  2 => 
    array
      0 => string 'bo_17' (length=5)
      1 => string 'bo_5' (length=4)
  3 => 
    array
      0 => string 'bo_17' (length=5)
[PHP] pobierz, plaintext 

Ten post edytował sabat24 11.03.2015, 10:32:56

[CuteOne]

Co dokładnie ma być na wyjściu, bo twój przykład jest dość niejasny, i można go interpretować na kilka sposobów

[sabat24]

Każda "podtablica" jest swoistym podzbiorem, stanowiącym pewną całość. Czyli mamy zbiory (prefix 'bo_' pominę, bo jest nieistotny i tak, a mogą być tam inne wartości):
a = {5, 1}
b = {1, 5, 17}
c = {17, 18}
d = {19, 1, 5, 17}

Zbiór d zawiera w sobie całkowicie zbiór a oraz b, zatem do wyjścia powinien zostać wybrany zbiór d. Zbiór c nie zawiera się w całości nigdzie, więc także powinien być dodany do wyniku. Kolejność w podzbiorach nie ma znaczenia. Tzn. {5, 1} jest równe {1, 5}.

Ten post edytował sabat24 11.03.2015, 10:42:31

[Pyton_000]

czyli na wyjściu powinien być zbiór który nie zawiera się w żadnym innym zbiorze oraz zbiór który zawiera maksymalną ilość podzbiorów zawierających się w całości?

[sabat24]

Zgadza się. Oczywiście zarówno zbiorów, które nie zawierają się w innych zbiorach w całości może być kilka, jak i może być kilka różnych zbiorów, które posiadają "w sobie" maksymalną liczbę podzbiorów. Np.
wejście:
a = {1, 2, 3}
b = {2, 3, 5}
c = {1, 2, 3, 4}
b = {2, 3, 4, 5}
e = {5, 6}
f = {5, 7}

powinno dać wyjście:

{1, 2, 3, 4}, {2, 3, 4, 5}, {5, 6}, {5, 7}

[Pyton_000]

Nie jest to kod polotów master developera ale działa

http://pastebin.com/uzB22vE6

[sabat24]

Dziękuję. Wygląda bardziej przyzwoicie niż mój kod. Jedno pytanie. Przy powyższych danych wejściowych daje mi następujący rezultat:

[PHP] pobierz, plaintext 
Array
(
    [c] => 2
)
Array
(
    [b] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 4
            [3] => 5
        )
 
    [e] => Array
        (
            [0] => 5
            [1] => 6
        )
 
    [f] => Array
        (
            [0] => 5
            [1] => 7
        )
 
)
[PHP] pobierz, plaintext 

$maxArrays zawiera zbiór c, ale posiada tylko wartość 2
$none jest w porządku, ale ląduje tam zbiór b, który powinien być chyba w $maxArrays

Generalnie dla mnie nie ma to znaczenia, bo i tak sobie mogę pobrać orginalne dane ze zbioru c i też nie muszę mieć podziału na dwie zmienne, więc nieważne gdzie finalnie wyląduje b. Pytam z ciekawości, czy taki jest zamierzony efekt?

[Pyton_000]

nie bo B nie zawiera się w żadnym zbiorze w całości,

a w maxArrays masz tylko klucze zbiorów które mają maksymalną ilość zbiorów w których dany zbiór się zawiera , jak podzielisz przez /2 to dostaniesz ile zbiorów zawiera się w tym zbiorze

[sabat24]

Mój błąd. W przykładzie dałem 2 zbiory z kluczem B (przez co jeden nadpisywał drugi), a powinno być D dla czwartego zbioru. Wieczorem zrobię jeszcze różne testy. Jeśli nie obrazisz się za symboliczną zapłatę, to podeślij mi proszę nr konta w PW.