Сжатие векторов в декартовых изделиях

Question

У меня есть N 10-мерных векторов, где каждый элемент может иметь значение 0,1 или 2. Например, vector v=(0,1,1,2,0,1,2,0,1,1) является одним из векторов. Есть ли алгоритм (желательно на python), который сжимает эти векторы в минимальное количество декартовых произведений. Если это не идеальное решение, есть алгоритм, который, по крайней мере, дает хорошее сжатие.

Пример: два "декартовы векторы" ([1,2], 0, 1, 0, 0, 0, 1, 1, [0,1], 0]) (дает 4 векторов) и (0, 1, 0, 2, 0, 0, [0,2], 2, 0, 1) (дает 2 векторов) дает оптимальное решение для векторов N = 6:

1,0,1,0,0,0,1,1,0,0 
2,0,1,0,0,0,1,1,0,0 
1,0,1,0,0,0,1,1,1,0 
2,0,1,0,0,0,1,1,1,0 
0,1,0,2,0,0,0,2,0,1 
0,1,0,2,0,0,2,2,0,1 

Answer 1

Если векторы (0, 1) -значение, вы столкнетесь с минимальной проблемой DNF, which is (исправьте меня, если я ошибаюсь) NP-hard. Наличие (0,1,2) -значных векторов не делает проблему более простой.

Answer 2

Жадный алгоритм может быть полезен:

Let S = <V1, V2, ... Vn> 

has_merge_ops = True 

while has_merge_ops: 
    has_merge_ops = False 

    S' = [] 
    for v in S: 
     if there exits v' which differs from v by just only ONE element: 
      V = merge v and v' by merging the different values at index k 
      S'.append(V) 
      S.remove(v) 
      S.remove(v') 
      has_merge_ops = True 

    S = S' 

return S 

Так как это работает:

after sorting, S = 
0,1,0,2,0,0,0,2,0,1 
0,1,0,2,0,0,2,2,0,1 
1,0,1,0,0,0,1,1,0,0 
1,0,1,0,0,0,1,1,1,0 
2,0,1,0,0,0,1,1,0,0 
2,0,1,0,0,0,1,1,1,0 

After first pass: 
0,1,0,2,0,0,[0,2],2,0,1 
1,0,1,0,0,0,1,1,[0,1],0 
2,0,1,0,0,0,1,1,[0,1],0 

After 2nd pass: 
0,1,0,2,0,0,[0,2],2,0,1 
[1,2],0,1,0,0,0,1,1,[0,1],0 

Algorithm stops since no more merging is possible.