yipuran-core で書いた Combinations
yipuran-core/Combinations.java at master · yipuran/yipuran-core · GitHub
は、要素の重複を許さない、組み合わせだ。
つまり、"A", "B", "C" の組み合わせで、"AAA" や、"AAB" という解を許さない Combination である。
この要素の重複、"AAA" や、"AAB" を組み合わせの解に持つ、nHr
homogeneous
を Java で求めることを検討した。
まず、参考にさせていただいたのだが、https://ideone.com/gRQfPt であるが、これをちょっと加工して以下のように数字パターンで求めるもの
int n = 4; int r = 3; int[] d = new int[n > r ? n+1 : r+1]; for(int i=1; i <= n; i++) d[i] = 1; while(d[0] <= 0){ if (d[d.length-1] != 0){ for(int i=1; i <= r ; i++) System.out.print(d[i]); System.out.println(""); } for(int j=r; 0 <= j; j--){ d[j]++; for(int k=j+1; k <=r; k++) { d[k] = d[k-1]; } if (d[j] <= n) break; } }
上のこれには、大きな欠点がある。n には、10以上を指定すると数字が要素に並んでしまうので区切りない。
n < r の場合、n=3 , r=5 では、想定以外の '11101' が結果として出てしまう。
また、数字ではなく文字やオブジェクト要素の組み合わせを求めるものではない。
現実的にはこのままでは使えない
そこで、以下のように Stream を使う。
public static <T> List<List<T>> homogeneous(List<T> list, int len){ List<List<T>> rtn = new ArrayList<>(); int n = list.size(); int[] d = new int[n > len ? n+1 : len+1]; for(int i=1; i <= n; i++) d[i] = 1; while(d[0] <= 0){ if (d[d.length-1] != 0){ List<T> lt = Arrays.stream(d).boxed() .filter(e->e > 0) .map(e->list.get(e-1)) .limit(len) .collect(Collectors.toList()); if (lt.size()==len){ rtn.add(lt); } } for(int j=len; 0 <= j; j--){ d[j]++; for(int k=j+1; k <= len; k++) { d[k] = d[k-1]; } if (d[j] <= n) break; } } return rtn; }
filter と、limit で組み合わせる数を指定するところが、ミソである。