0

Javaで実装した、論理演算の吸収律を適用する以下のようなアルゴリズムをPythonに書き直しております。

1 Vector matrix = [ [a], [a, b], [a, c] ];
2 for (int i = 0; i < matrix.size(); i++) {
3    Vector element_left = matrix.get(i);
4
5    for (int j = i+1; j < matrix.size(); j++) {
6        Vector element_right = matrix.get(j);
7
8        if (isIncluded(left, right)) {
9            // 左辺の要素が右辺の要素が部分集合であれば
10            matrix.remove(j);
11            j--;
12       }
13    }
14 }

10,11行目の「i番目の要素がj番目の部分集合である場合、j番目の要素を削除して、jをデクリメントする処理」をPythonで実装する方法がわかりません。

この処理をPythonで実現する書き方をご教示いただけないでしょうか。
初歩的な質問でお手数おかけいたしますが、どうぞよろしくおねがいします。
※ PythonのSet{}を使う方法もあるかと思いますが、可能であれば2次元配列を使用した方法ですと幸甚です。

2
  • 本質とは関係なさそうな確認ですが、変数 matrix は DNF もしくは CNF を表しているということですよいでしょうか? (変項を表すであろう部分が文字列 (名前) でなくて変数そのものである部分が気になりますが……。ID として管理なさっているのでしょうか。)
    – nekketsuuu
    2019年3月4日 2:38
  • isIncluded(left, right)leftright が未定義なのでこのままだとコンパイルエラーを起こします。element_leftelement_right の誤記でしょうか? また、「2次元配列を使用した方法」というのが良く分からなかったです。というのも isIncluded(left, right)leftright は1次元配列だからです。
    – nekketsuuu
    2019年3月4日 2:59

1 件の回答 1

1

あるリストが別のリストに対して集合として部分集合になっているかどうかは、ご指摘の通り setset.issubset() を使うと簡単に判定できます。

これを使いたくない場合、Java の方で isIncluded() を実装したのと同じように Python でも実装できるはずです。たとえば、部分集合の定義通り、片方の要素が他方に全て含まれているかどうか逐一検査するというやり方です (ただし要素の重複を無視するかどうかは決める必要があります)。

リストから要素を削除する方法も Java 同様 matrix.remove(matrix[i]) を使ったり、あるいは del matrix[i] を使ったりすることで実現できます。今回はインデックスで削除しているので del matrix[i] の方が向いていそうです。

補足:ただし私だったら、ループしながら削除するのではなく、別の新しいリストを用意して、ループしながらそれに append していく方法を選びそうです。in-place ではなくなりますが、インデックス周りのバグが起きにくそうだからです。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。