Генерация всех возможных размещений объектов в k бинах размером n1, n2, ... nk в C ++ - PullRequest
Новая
       1

Генерация всех возможных размещений объектов в k бинах размером n1, n2, ... nk в C ++

1 голос
/ 31 января 2012

Я пытаюсь написать код C ++, который будет вычислять все возможные упорядочения групп целых чисел, размеры которых указаны в векторе (длина неизвестна).

Например, если входное значение (group1 = 2, group2 = 3, group3 = 2), тогда мне нужно вычислить каждый порядок первых 7 целых чисел в группах по 2, 3 и 2.

Группы имеют значение во избежание дублирования (т. Е. 1234567 - это то же самое, что и 2134567, что совпадает с 1234576).

Выходные данные должны быть: 

1234567
1234657
1234756
1235647
...
6734512

Но можетдать до 10 различных групп (обычно размер группы меньше или равен 5)

Я все еще довольно новичок в C ++, но мне кажется, что мне нужно использовать next_permutation из алгоритма,возможно в рекурсии, но я не смог разобраться в деталях.

Следующее работает (неэффективно) код R, который я написал, (в случае, если мой вопрос был неясен), но он слишком медленныйдля достаточно больших групповых номеров / размеров.

Спасибо! 

#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))

Ответы [ 2 ]

3 голосов
/ 31 января 2012

Мне кажется, это работает: 

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);
}

Как это работает: довольно стандартное перечисление всех перестановок идентификаторов, модифицированных таким образом, что идентификаторы в пределах одной группы вынуждены строго увеличиваться. На границе каждой группы идентификатор может уменьшаться.

1 голос
/ 31 января 2012

То, что вы пытаетесь сделать, похоже на алгоритм shuffle .

...