An answer to this question on Stack Overflow.

Question

I 'am developing a technique for sorting a table that contains either 0 or 1 such as:

 {{1, 1, 0, 1, 1, 1, 1, 1},
  {1, 1, 0, 0, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {1, 1, 1, 0, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {0, 0, 0, 0, 0, 1, 0, 1},
  {1, 1, 1, 1, 1, 0, 0, 0},
  {1, 1, 1, 1, 1, 1, 0, 1},
  {0, 0, 0, 1, 0, 1, 0, 1},
  {1, 1, 1, 1, 1, 0, 0, 0},
  {1, 1, 1, 1, 1, 0, 0, 0}}

The objective is to count the total per column and sort the table: I. Descending based on the total per column. II. coverage. For instance, in the 1st row the 3rd value is 0. We'll have to find the 1st column that has 1 in the 3rd column and re-sort the columns. In other words, 1 stands for coverage and we have to make sure that we cover all within the 1st few columns.

I managed to get the total per column, as follows:

    For (i=0; i<m; i++)
      For (j=0; j< TS.Size(); j++) 
             if (tc.detected()==1)
                      TS_Detect[j][i]= 1
             else
                      TS_Detect[j][i]= 0
    TC_Sum=(2, TS.Size())
    For (k=0; k<TS.Size(); k++)
      TC_Sum(0, k)=k
      For (l=0; l< m; l++) 
             Flag=TS_Detect[l][k]
             If (flag == 1)
                 TC_Sum(1, k)= TC_Sum(1, k)+1
    int temp
    For (g=0; g<TC_Sum.length-1; g++)
      For (b=1; b< TC_Sum.length-1; b++)
              If (TC_Sum[b-1]< TC_Sum[b])
                    temp= TC_Sum[b-1]
                    TC_Sum[b-1]= TC_Sum[b]
                    TC_Sum[b]= temp
    return TC_Sum

The problem now is that I couldn't sort the original array (TC_Detect) based on the column number from TC_Sum.

Consequently, I would like to re-sort the table so if a column has 0, the next one will be 1.

The expected output for the above example will look like:

 {{1, 1, 0, 1, 1, 1, 1, 1},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {1, 1, 0, 0, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {0, 0, 0, 0, 0, 1, 0, 1},
  {1, 1, 1, 0, 0, 0, 1, 0},
  {1, 1, 1, 1, 1, 1, 1, 0},
  {0, 0, 0, 1, 0, 1, 0, 1},
  {1, 1, 1, 1, 1, 0, 0, 0},
  {1, 1, 1, 1, 1, 1, 0, 1},
  {1, 1, 1, 1, 1, 0, 0, 0},
  {1, 1, 1, 1, 1, 0, 0, 0}}

Any suggestion, please.

Answer

I'm not sure what language you are using, but I think my answer is general enough.

I assume that you have a list of lists, let's call it A.

A = [ [0,1,0,0] , [1,0,1,1] , [0,0,0,0] ]

You've used your counting algorithm above to make another list, call it S for sum.

S = [ 3 , 1 , 0 ]

You now want to sort A based on the values of S.

To make things easy, let's define a third list that we'll call I for index.

I = [ 0 , 1 , 2 ]

I would continue up to 3,4,5,6,... depending on the number of elements in your list

What you need now is a sort function that allows you to sort based on a key. Such a sort function usually takes the thing you want to sort along with a function for comparing two items.

In this case, sort I. The sort function is then passed indices. Compare these indices based on the values in S. The result is a list I* containing indices sorted according to S. You can now reorder A based on I*.

I am not sure what language you are using, but the following Python code accomplishes this:

def MyComparison(i,j):
  return S[j]-S[i]
A = [ [0,1,0,0] , [1,0,1,1], [0,0,0,0] ]
S = [ 1 , 3 , 0 ]
I = [ 0 , 1 , 2 ]
Istar = sorted(I, cmp=MyComparison)
#The above returns: [2, 0, 1]. If this is the wrong order, reverse the result.
[A[x] for x in Istar]
#The above returns: [[1, 0, 1, 1], [0, 1, 0, 0], [0, 0, 0, 0]]

Note that the comparison function returns -1, 0, or 1 depending on the relative ranking of the items compared.