For ComplexCombinationGenerator add "number of elements in every group"

[dpaukov]

Reported by [email protected], Feb 23, 2015
For the ComplexCombinationGenerator it should not only be possible to specify the number of groups, but also the number of elements in every group. E.g. searching for [1, 2, 3, 4, 5, 6] only searching for groups of length 3 should output:

[1] 1 3 5
[2] 2 4 6

[1] 1 3 4
[2] 2 5 6

[1] 1 3 4
[2] 2 6 5

[1] 1 2 5
[2] 3 4 6

[1] 1 2 4
[2] 3 5 6

[1] 1 2 4
[2] 3 6 5

[1] 1 2 5
[2] 4 3 6

[1] 1 2 3
[2] 4 5 6

[1] 1 2 3
[2] 4 6 5

[1] 1 2 4
[2] 5 3 6

[1] 1 2 3
[2] 5 4 6

[1] 1 2 3
[2] 5 6 4

[1] 1 2 4
[2] 6 3 5

[1] 1 2 3
[2] 6 4 5

[1] 1 2 3
[2] 6 5 4

Generating all the items and using an IFilter is very slow. Taking the length of the sub lists into concideration should speed up the generation a lot. Please see an algorithm in R as reference: http://stackoverflow.com/a/14758057

Thanks & regards, Kristian

[dpaukov]

Thanks for accepting this issue so quickly. I have already adapted the R code to Java. If you would like to take a look at the implementation, this may be valuable as a reference:

/** adaption from pseudo / R code of http://stackoverflow.com/a/14758057 **/
private static <T> List<List<List<T>>> groups(List<T> x,int n) {
    //nx <- length(x); ning <- nx/n
    int nx = x.size(), ning = nx/n;

    //group1 <- rbind( matrix(rep(x[1],choose(nx-1,ning-1)),nrow=1), combn(x[-1],ning-1) )
    List<List<T>> group1 = new ArrayList<List<T>>();
    T kfst = x.get(0);
    int knum = (int)choose(nx-1,ning-1);
    ICombinatoricsVector<T> kvec = Factory.createVector(x.subList(1,nx));
    Generator<T> kgen = Factory.createSimpleCombinationGenerator(kvec, ning-1);
    List<ICombinatoricsVector<T>> kcoms = kgen.generateAllObjects();
    for(int kidx=0;kidx<knum;kidx++) {
        ICombinatoricsVector<T> kcom = kcoms.get(kidx);
        group1.add(new ArrayList<T>(knum){ private static final long serialVersionUID = 1L; {
            add(kfst); addAll(kcom.getVector());
        }});
    }

    //ng <- ncol(group1)
    int ng = group1.size();

    //if(n > 2){ ... } else { ... }
    if(n > 2){
        //out <- vector('list',ng)
        List<List<List<T>>> out = new ArrayList<List<List<T>>>(ng);

        //for(i in seq_len(ng)){
        for(int i=0;i<ng;i++) {
            //other <- perm.groups(setdiff(x,group1[,i]),n=n-1)
            List<T> kdif = new ArrayList<>(x), kgri = group1.get(i);
            kdif.removeAll(kgri);
            List<List<List<T>>> other = groups(kdif,n-1);

            //out[[i]] <- lapply( seq_along(other),function(j) cbind(group1[,i],other[[j]]) )
            for(int j=0;j<other.size();j++) {
                List<List<T>> kotj = other.get(j);
                out.add(new ArrayList<List<T>>(){ private static final long serialVersionUID = 1L; {
                    add(kgri); addAll(kotj);
                }});
            }
        }

        //unnecesarry: out <- unlist(out,recursive=FALSE)
        return out;
    } else {
        //other <- lapply(seq_len(ng),function(i) matrix(setdiff(x,group1[,i]),ncol=1))
        //out <- lapply(seq_len(ng), function(i) cbind(group1[,i],other[[i]]) )
        List<List<List<T>>> out = new ArrayList<List<List<T>>>(ng);
        for(int i=0;i<ng;i++) {
            List<T> kdif = new ArrayList<>(x), kgri = group1.get(i);
            kdif.removeAll(kgri);
            out.add(Arrays.asList(group1.get(i), kdif));
        }

        return out;
    }
}

private static long choose(int n,int k) {
    if(k>n-k)
        k = n-k;
    long b = 1;
    for(int i = 1,m = n;i<=k;i++,m--)
        b = b*m/i;
    return b;
}

Regards, Kristian