CODEWITHSUNDEEP
c++combinations
Gschneider
Gschneider

Reputation: 254

Generating all possible allocations of objects into k bins of size n1,n2,...nk in C++

I'm trying to write C++ code which will compute all possible orderings of groups of integers, whose sizes are given in a vector (unknown in length).

For example, if the input is (group1=2, group2=3, group3=2), then I need to compute every ordering of the first 7 integers, in groups of 2, 3, and 2.

Groups matter in avoiding duplicates (i.e. 1234567 is the same as 2134567 which is the same as 1234576).

The output should be:

1234567
1234657
1234756
1235647
...
6734512

But there could be as many as 10 different groups given (usually the size of the group is less than or equal to 5)

I'm still fairly new to C++, but it seems like I need to use next_permutation from algorithm, possibly in recursion, but I haven't been able to work out the details.

The following is working (inefficient) R code I've written, (in case my question was unclear) but it's far too slow for reasonably large group numbers/sizes.

Thanks!

#Input group sizes for k;
CombnMult<-function(k){
n<-sum(k)
A1<-combn(n,k[1])
CHOOSE<-rep(0,length(k))
CHOOSE[1]<-factorial(n)/(factorial(k[1])*factorial(n-k[1]))
for(i in 1:(length(k)-1)){
CHOOSE[i+1]<-factorial(n-cumsum(k)[i])/(factorial(k[i+1])*factorial(n-cumsum(k)[i+1]))
assign(paste("B",i,sep=''),matrix(get(paste("A",i,sep='')), nrow=cumsum(k)[i]))
if(length((1:n)[is.na(pmatch((1:n),get(paste("B",i,sep=''))[,1]))])>1)  
assign(paste("A",i+1,sep=''),apply(get(paste("B",i,sep='')),2,function(z) rbind(matrix(rep(z,CHOOSE[i+1]),ncol=CHOOSE[i+1]),combn((1:n)[is.na(pmatch((1:n),z))],k[i+1]))))
if(length((1:n)[is.na(pmatch((1:n),get(paste("B",i,sep=''))[,1]))])==1) 
assign(paste("A",i+1,sep=''),apply(get(paste("B",i,sep='')),2,function(z) rbind(matrix(rep(z,CHOOSE[i+1]),ncol=CHOOSE[i+1]),(1:n)[is.na(pmatch((1:n),z))])))
}
t(get(paste("A",i+1,sep='')))
}

#Example:
CombnMult(c(2,3,2))

Upvotes: 1

Views: 576

Answers (2)

Ben Voigt
Ben Voigt

Reputation: 283793

This seems to work for me:

void allocate_to_groups_impl( std::vector<char>& usage, std::vector<int>& order, const std::vector<int>& cumsum, int group, int place, int min )
{
    if (place == cumsum[group]) {
        group++;
        min = 0;
        if (group == cumsum.size()) {
            // the allocation is stored in order, we'll just print it out but you could do something else with it
            for( std::vector<int>::iterator it = order.begin(); it != order.end(); ++it )
                putchar(digitset[*it]);
            putchar('\n');
            return;
        }
    }

    for( int v = min, max = usage.size() + place - cumsum[group]; v <= max; ++v ) {
        if (!usage[v]) {
            order[place] = v;
            usage[v] = 1;
            allocate_to_groups_impl(usage, order, cumsum, group, place+1, v+1);
            usage[v] = 0;
        }
    }
}

template<size_t Ngroups>
void allocate_to_groups( int (&c)[Ngroups] )
{
    size_t sum_of_c = 0;
    std::vector<int> cumsum_of_c;
    for( int* it = c; it < c + Ngroups; ++it )
        cumsum_of_c.push_back(sum_of_c += *it);
    std::vector<int> order(sum_of_c);
    std::vector<char> usage(sum_of_c);

    allocate_to_groups_impl(usage, order, cumsum_of_c, 0, 0, 0);
}

How it works: A fairly standard enumeration of all permutations of the identifiers, modified so that the identifiers within a single group are forced to be strictly increasing. At each group boundary, the identifier is allowed to decrease.

Upvotes: 3

unixman83
unixman83

Reputation: 9943

What you are trying to do looks similar to a shuffle algorithm.

Upvotes: 1

Related Questions