簡単に言えば組み合わせ問題( nCr 問題)にちょっと条件が付いた。
課題は「任意長nの配列から最大r個の要素を組み合わせた集合を作る。ただし複数の要素はそれぞれが隣り合わない番地に在ること」という超ニッチな条件。
で、実装に3日悩んでしまったものがこちら☟
public void serchCombination(int n, int r, ArrayList<ArrayList<Integer>> list, ArrayList<Integer> element, int address) { ArrayList<Integer> copyElement = new ArrayList<Integer>(element); ArrayList<Integer> addElement; int count = copyElement.size(); int num = address; for(int i=num; i<n; i++) { if(count >= r) break; if(count < r) { if( count == 0 || (i > copyElement.get(copyElement.size()-1)+1) ) { copyElement.add(i); addElement = new ArrayList<Integer>(copyElement); list.add(addElement); count++; if(count == r && i < n-1) { copyElement.remove(copyElement.size()-1); count--; serchCombination(n, r, list, copyElement, i+1); break; } serchCombination(n, r, list, copyElement, i+1); // 次の要素を入れるために除去 copyElement.remove(copyElement.size()-1); count--; } } } }
まあちょっとごっちゃりしててわかりにくいと思うけれど実行させるとちゃんと動く。
for(ArrayList<Integer> i : List) { for(int j : i) { System.out.print(j + " "); } System.out.println(""); }
例えば、 ArrayList
0 0 2 0 2 4 0 2 4 6 0 2 4 7 0 2 5 0 2 5 7 0 2 6 0 2 7 0 3 0 3 5 0 3 5 7 0 3 6 0 3 7 0 4 0 4 6 0 4 7 0 5 0 5 7 0 6 0 7 1 1 3 1 3 5 1 3 5 7 1 3 6 1 3 7 1 4 1 4 6 1 4 7 1 5 1 5 7 1 6 1 7 2 2 4 2 4 6 2 4 7 2 5 2 5 7 2 6 2 7 3 3 5 3 5 7 3 6 3 7 4 4 6 4 7 5 5 7 6 7
と出てくれる。
このコードを改良したい気もあるけど、プログラム制作の一環でできた代物なので、まずはプログラムを完成させてから。 何方かいい案あったら教えてください。
追記 : 参考にしたもの(後から検証する程度)
mixi.jp ↑チョット理解した
chakotay.jugem.jp ↑まだ読んでない
wagashi1349.hatenablog.com ↑チョット読んだ(再帰にするならメソッド一つでやりくりしたかったのでご縁がなかった)
kuidaored.hatenablog.com ↑最初の内は参考にしてた。
codeday.me ↑ばなな