bzajdlik

I hope someone can point me in the right direction on a data
recombination problem.

I have a matrix of attributes that tells me whether to combine samples;
1 if a pair should be combined and zero otherwise. Samples can only be
combined if all possible pairwise comparisons among samples are tagged
as one. For example if a =b and b= c but a does not equal c, we cannot
state a = b = c. Nor can I state a = b and b = c as the sample can
only be used once. In this example no combinations of samples are
possible. A few more examples using a 4x4 matrix with column and row
labels a, b, c and d follow illustrate other scenarios.


Example 1:

1, 1, 0, 0
1, 1, 0, 0
0, 0, 1, 1
0, 0, 1, 1

In this case the two groups that should be produced are: ab and cd.

Example 2:

1, 1, 1, 0
1, 1, 1, 0
1, 1, 1, 0
0, 0, 0, 1

In this case the two groups that should be produced are: abc and d.

Example 3:
1, 1, 1, 0
1, 1, 1, 0
1, 1, 1, 1
0, 0, 1, 1

In this case the four groups that should be produced are: a, b, c and
d.

1, 0, 0, 1
0, 1, 0, 0
0, 0, 1, 0
1, 0, 0, 1


In this case the three groups that should be produced are: ad, b and c.


Any leads for this seemingly common (but new to me) problem would be
appreciated. I will end up writing a program in R if anyone is
interested in that.


Cheers,

Barry Zajdlik