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]

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