最大1sの列を持つ最小の行を見つける

Question

私はすべて0と1を持つnumpyの2D配列を持っています。そして、各列に対して少なくとも1つの行が必要です。例：

問題の説明：すべての列に最大1を与える最小限の行を見つけます。

INPUT1：ここ

A B C D E 
t1 0 0 0 1 1 
t2 0 1 1 0 1 
t3 0 1 1 0 1 
t4 1 0 1 0 1 
t5 1 0 1 0 1 
t6 1 1 1 1 0 

、（T6、T1）のような複数の回答があり、（T6、T2）、（T6、T3）、（T6、T4）、（T6、T5 ）。

INPUT2：

A B C D E 
t1 0 0 0 1 1 
t2 0 1 1 0 1 
t3 0 1 1 0 1 
t4 1 0 1 0 1 
t5 1 0 1 0 1 
t6 1 1 1 1 1 

回答：T6

私の元の行列が非常に大きいと私は強引な方法を使用する必要はありません。これを行うにはスマートな方法がありますか？

Answer 1

ナイーブ溶液、最悪の場合O（2^N）

行のすべての可能な選択肢に対するこの反復、通常低多項式時間平均のケースを作り、できるだけ少数の行で始まります。

from itertools import combinations 
import numpy as np 

def minimum_rows(arr): 
    out_list = [] 
    rows = arr.shape[0] 
    for x in range(1, rows): 
     for combo in combinations(range(rows),x): 
      if np.logical_or.reduce(arr[[combo]]).all(): 
       out_list.append(combo) 
     if out_list: 
      return out_list 

私はこれを電話で多くのテストをせずに全面的に書いているため、動作している場合と動作しない場合があります。それはトリックを使用しませんが、かなり速いです。 columns/rowsの比率が大きい場合、または特定の要素がTrueの確率が小さい場合、必要な条件を満たす行が少なくなり、xが増加する可能性が低くなるため、比率が遅くなることに注意してください繰り返しの組み合わせの数。