樹形図をたどる、重複する組み合わせはスキップしたい

Question

ある重複のある数列から任意の個数の、ある条件にあった数字を取り出す組み合わせを、樹形図をたどるようなアルゴリズムをつかって列挙したいんです。

その際に、重複した組み合わせが出力されそうなときにその出力をスキップしたいんです。
つまり、ただ樹形図をたどって出力していると同じ組み合わせが複数回出力されてしまうことになると思うのですが、いままでで出力してある場合は出力したくないんです。

樹形図を辿って出力するだけのプログラムはできたんですが、いままで出たことがあるのか判定することはできるんでしょうか？

(追記)
組み合わせの総数を単純に計算すると15000位になってしまって、ハッシュ値みたいのものを保存しておいて、検索するようなことは厳しいです。

Answer 1

javaならArrayListがあるので、

ArrayList<Data> datalist = new ArrayList<Data>();//表示した過去データを格納
tree = [樹形図]//

for(tree???){//樹形図のデータを取り出すループ
   Data data = [tree樹形図のデータ]
   boolean flag = true;
   for(int n = 0; n < datalist.size(); n++){
      if(data.equals(datalist.get(n))){//過去のものと重複した
         flag = false;//表示しない
         break;
      }
   }
   if(flag){//重複がなかった
      System.out.print(data);
      datalist.add(data);
   }
}

みたいに過去に表示したものとの一致を検出するのはどうでしょうか。
データが増えるとパフォーマンスがどんどん下がる方式だとは思います。

Comments

[akamakku]

やっぱりそういうシンプルなものになってしまいますか～
とりあえずそれでやってみようかなと思います。

[退会済みユーザー]

ArrayListよりもHashSetがおすすめです。
HashSetは同じ要素を複数格納できないという制約がある上に、ハッシュを使った検索も内部で行っています。
また、重複の検索には、HashSet#containsを使えばよいでしょう（ArrayListにもcontainsがあるのですが）。

[swordone]

HashSetを使うならcontainsを使わずとも、addすればいいだけだと思います。
すでに同じ要素があればSetは変化しません。

[intelf___]

気になって調べてみましたがHashSet#addはよさそうですね
勉強になります。
重複なしだと戻り値がtrueになるので
if(hashSet.add(data))
System.out.print(data);
みたいな文ができそうですね。

[akamakku]

HashSet　！！
まさにいまの自分のためにできたんじゃないかというようなクラスです！笑
コメントしてくださった皆さんも含めてBAです
ありがとうございます！