[Java]booleanの2次元配列から生成するあるデータ構造の構成について

Question

###ひとこと
投稿はおろか，このサイトを利用することが初めてで，わかりにくい質問だと思いますがよろしくお願いします．
もし質問の書き方についても．ここはこう書いたほうがいい，などのアドバイスがあったら修正します．

###前提・実現したいこと
"Web Page Recommendation Based on Bitwise Frequent Pattern Mining"という論文内で登場するVI-listというデータ構造をJavaで実装したいのですが上手くいかないので，アドバイス等お願いします．

この構造体VI-listは，
以下の表のようなWB-tableというデータ構造(実際は0/1ではなくTrue/False)から
||1|2|3|4|5|
|:--|:--:|--:|
|A|0|1|0|0|1|0|
|B|1|0|1|0|0|0|
|C|1|0|0|0|1|0|
|D|0|1|1|0|1|0|
|E|1|1|1|0|0|0|

以下のようなリストとして生成されます．

Column index	Row indeces
1	2,3,5 (WB-table上のB,C,Eを指す)
2	1,4 (WB-table上のA,Dを指す)

仕様は以下のような感じです．
0. WB-tableの各行に対して列の左から見て，初出の1(WB-table内太字部分)となる組み合わせをVI-listに格納していく．

1. Column indexには配列などを用いた数の組み合わせの表現が可能であり，その組み合わせも取り出せる．
2. Column indexについて昇順に並んだ状態である．
3. WB-tableはboolean[][]の二次元の行列で構成されている．

拙い説明ですがよろしくお願いします．

###試したこと，問題点

• HashMapで構成しようとしたが，上記の仕様の2.と3.を満たさない(?)
• Column IndexとRowIndecesをArrayListを用いて別々に作ろうとしたが，仕様の3.が満たせない．Column Indexのソートを行うとRow Indecesとの対応関係が切れてしまう．
• 一番の問題点は自分がプログラミングの経験，知識がほとんどないことだと思います・・・

###自分が書いたコード

ここは無視してもらっても大丈夫です．
上記のArrayListで構成しようとしたver.です．
途中でこれだとできそうにないことに気づいてやめてしまっており，また，多々おかしなところがあると思います．
自分のプログラミングのレベルとやりたいことの雰囲気だけでもわかってもらえれば幸いです．

public class VI_List{
  ArrayList<Integer> row = new ArrayList<Integer>();
  ArrayList<ArrayList<Integer>> rowList = new ArrayList<ArraList<Integer>>();
  ArrayList<Integer[]> col = new ArrayList<Integer[]>();

  VI_List(WB_Table wb){
    boolean flg = true;
    
    for(int i=0;i<wb.table.length;i++){
      for(int j=0;flg;j++){
        if(wb.table[i][j]){
          if(!this.col.contains(j)){
            this.col.get(j);
          }　
          //このあたりで昇順に並べられないことに気づき中断
          this.row.add(i);
          flg = false;
        }
      }
    }
  }

Comments

[swordone]

Column Indexが1に対応するのは、2,3,5ではないですか？

Answer 1

そんな複雑に考えなくていいと思います。
重要なのは「各行最初にtrueが出現する列」が必要ということです。
まず、素直にboolean2次元配列でWB-tableを表現します。例の場合は

boolean[][] wbTable = {{false, true, false, false, true},
                       {true, false, true, false, false},
                       {true, false, false, false, true},
                       {false, true, true, false, true},
                       {true, true, true, false, false}};

のようになります。
次に、行ごとに最初にtrueが出現する列を取得し、それを行と対応するように保持します。

// 各行で最初にtrueが出現する列番号を保持する配列
int[] first = new int[wbTable.length];
for (int i = 0; i < wbTable.length; i++) {
    for (int j = 0; j < wbTable[i].length; j++) {
        if (wbTable[i][j]) {
            // 0を未発見に対応させるため、1加えて列数にする
            first[i] = j + 1;
            break;
        }
    }
}

そして、今度は保持した列番号ごとに行を分類します。HashMapを使うと楽です。昇順に並べる処理は後からできます。

Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < first.length; i++) {
    List<Integer> list = map.get(first[i]);
    if (list == null) list = new ArrayList<Integer>();
    list.add(i + 1);
    map.put(first[i], list);
}

後は、このMapの内容を、キーとなる列番号の昇順で出力すればいいのです。Mapにはキーと値の組をコレクションとして取り出すentrySet()というメソッドがあります。これを使います。

List<Map.Entry<Integer, List<Integer>>> entries = new ArrayList<>(map.entrySet());
Collections.sort(entries, Comparator.comparing(Map.Entry::getKey));
for (Map.Entry<Integer, List<Integer>> entry : entries) {
    System.out.println("[" + entry.getKey() + "]" + entry.getValue());
}

Answer 2

説明の表現が自分には曖昧に感じました。

WB-tableとVI-listの構造についてはわかりました。またWB-tableが入力ということ、VI-listを出力とすることもわかります。しかしもう一つ入力があるはずで、それが何かが曖昧に感じます。こういうことでしょうか？

input-1: WB-table
input-2: VI-listのColumn-index(求めたいものを好きなだけ指定できる)
=>例えば以下の2つの組み合わせ
[1,2,3,4,5],
[5,4,3,2,1]

output: input-2のそれぞれに大する完成したVI-list構造
=>
[1->[2,3,5],2->[1,4]]
[5->[1,3,4],3->[2,5]]

このようなことなのかなと感じました。上記のような確認は本来、質問コメントとして書くべき内容ですが、書きづらいのでここに書きました。

---

もし上記のようなものであるなら、そしてデータ構造をどうするかに混乱しておられるなら、例えば次のようなものを想定すればよいのではないかと思いました。

少々冗長なクラス構造ですが、単純な配列で書いても構造がわかりにくいのであえて冗長にしています。

// for input

class WBTable {
  boolean[][] matrix;
}

class ColumnIndices {
  int[] indices;
}

// for output


class VIList {
  Column[] columnArray;
}

class Column {
  int columnIndex;
  int[] rowIndices;
}


作りたい関数のインターフェース＝＞

VIList[] makeVIListFrom(WBTable wbTable, ColumnIndices[] requiredColumnIndiceList) {
  ...
}

Comments

[Tsuruta708]

紛らわしい書き方をしてすみません．入力はWB-tableのみです．
Column Indexは指定できるわけではなく，WB-tableの各行で初出となった1の列の数で決まります．
例えば，以下のようなWb-tableの場合，
[1,0,0,0,1]
[0,1,0,0,0]
[0,0,0,1,1]
[0,0,0,1,0]
[0,1,0,0,1]

構成されるVI-tableは以下のように，3行になります．
[1][1]
[2][2,5]
[4][3,4]

回答本当にありがとうございます．直接的な解決には至りませんでしたが，クラス構造の例がとても参考になりました．
おかげさまで，より柔軟に考えられそうです．
このまま他の方の回答がなければ，この回答をベストアンサーとさせていただきます．

[KSwordOfHaste]

そうでしたか。「2. Column indexには配列などを用いた数の組み合わせの表現が可能であり，その組み合わせも取り出せる．」とあったので、任意の列順を指定してVI-Listを複数求められると受け取ったのですが、できたVIListから「列インデックスのみ取り出せる」といったことだったのでしょうかね。

[Tsuruta708]

確かに，2.の書き方だとそう解釈してしまいますね．．．
仰るとおりです．