I have arrays comprised of string elements like the following 2 examples. Each of the following lines is a string element of the array.


aaa bbb cc1 dd1 
aaa bbb cc1 dd2 
aaa bbb cc2 dd1 
aaa bbb cc2 dd2 
aaa bbb cc3 dd1 
aaa bbb cc3 dd2 


bbb rrr nnn ttt ooo eee ddd fff contr 
bbb sss nnn ttt ppp eee contr 
bbb sss nnn aaa ooo eee ddd fff contr 
bbb rrr nnn ttt yyy eee ddd fff contr 

I want to simplify and remove "redundant" lines by merging in a single line duplicate attributes. The goal is to have the fewest lines possible, without the data values being confusing. So the results should be:


aaa bbb cc1/c2/c3 dd1
aaa bbb cc1/c2/c3 dd2


bbb rrr nnn ttt ooo/yyy eee ddd fff contr 
bbb sss nnn ttt ppp eee contr 
bbb sss nnn aaa ooo eee ddd fff contr 

(the results are an array as well).

My current approach goes like this: remove the first column then compare all elements. if equal lines are found, merge them. remove second column, compare. It becomes though somewhat complicated, as not all lines have the same number of data values (separated by spaces).

I'm stuck here. Any help would be welcome.

  • 1
    $\begingroup$ Can you please formalize what you want to achieve? For example, it's unclear to me what should be the result for a b1 c1, a b1 c2, a b2 c1. Also, it's possible to further simplify the first example as aaa bbb cc1/cc2/cc3 dd1/dd2; exactly why didn't you do this? Even if it's not allowed, why didn't you merge cc_ instead of dd_? It'll be less lines in the end. $\endgroup$ – Dmitry Jul 28 at 22:47
  • $\begingroup$ @Dmitry thank you for your reply. The goal is to have as few lines as possible. Both a b1 c1/c2, a b2 c1 AND a b1/b2 c1, a b1 c2 are acceptable answers. No aaa bbb cc1/cc2/cc3 dd1/dd2 is not allowed because one doesn't understand to which cc_ belongs dd2. You are right, the best merge would have been by cc_ like this aaa cc1/cc2/cc3 d1, aaa cc1/cc2/cc3 d2 since it offers the fewest lines. $\endgroup$ – MirrorMirror Jul 29 at 6:21
  • 1
    $\begingroup$ By aaa bbb cc1/cc2/cc3 dd1/dd2 I mean that every dd belongs to every cc (i.e. there are $2 \times 3 = 6$ combinations, as we want). Still not allowed? Then do I understand correctly the problem is to minimize the number of lines, when each line can have only one compression term? $\endgroup$ – Dmitry Jul 29 at 8:27
  • $\begingroup$ @Dmitry still not allowed yes. Yes the goal is to minimize the number of lines and each line has only one compression term $\endgroup$ – MirrorMirror Jul 29 at 9:10
  • 1
    $\begingroup$ It won't produce the optimal answer. Consider an example a1 b, a2 b, a3 b, a1 b1, a2 b2, a3 b3. The optimal solution is a1 b/b1, a2 b/b2, a3 b/b3 but you'll find a1/a2/a3 b, a1 b1, a2 b2, a3 b3. $\endgroup$ – Dmitry Jul 30 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.