Опираясь на @ Марк Байерс и Морон ответы на вашу задачу можно переформулировать следующим образом:
Перечислите все способы размещения K нулей в N местах (см. комбинаций с повторениями и Звезды и столбцы ).
Пример: для 15 битов и шаблона 1 2 6 1 есть N = 5 мест (до / после числа и между 1 с), чтобы поставить K = 2 нуля (число ведущих нулей для правильного числа сброса) ). Число путей равно биномиальному (N + K - 1, K), то есть биномиальному (5 + 2-1, 2) = 15.
Ключевыми функциями в коде ниже являются next_combination_counts() и comb2number().
Полная программа на C
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#define SIZE(arr) (sizeof(arr)/sizeof(*(arr)))
#define PRInumber "u"
typedef unsigned number_t;
// swap values pointed to by the pointer
static void
iter_swap(int* ia, int* ib) {
int t = *ia;
*ia = *ib;
*ib = t;
}
// see boost::next_combinations_counts()
// http://photon.poly.edu/~hbr/boost/combinations.html
// http://photon.poly.edu/~hbr/boost/combination.hpp
static bool
next_combination_counts(int* first, int* last) {
/*
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0
*/
int* current = last;
while (current != first && *(--current) == 0) {
}
if (current == first) {
if (first != last && *first != 0)
iter_swap(--last, first);
return false;
}
--(*current);
iter_swap(--last, current);
++(*(--current));
return true;
}
// convert combination and pattern to corresponding number
// example: comb=[2, 0, 0] pattern=[1,1] => num=5 (101 binary)
static number_t
comb2number(int comb[], int comb_size, int pattern[], int pattern_size) {
if (pattern_size == 0)
return 0;
assert(pattern_size > 0);
assert(comb_size > pattern_size);
// 111 -> 1000 - 1 -> 2**3 - 1 -> (1 << 3) - 1
// 111 << 2 -> 11100
number_t num = ((1 << pattern[pattern_size-1]) - 1) << comb[pattern_size];
int len = pattern[pattern_size-1] + comb[pattern_size];
for (int i = pattern_size - 1; i--> 0; ) {
num += ((1 << pattern[i]) - 1) << (comb[i+1] + 1 + len);
len += pattern[i] + comb[i+1] + 1;
}
return num;
}
// print binary representation of number
static void
print_binary(number_t number) {
if (number > 0) {
print_binary(number >> 1);
printf("%d", number & 1);
}
}
// print array
static void
printa(int arr[], int size, const char* suffix) {
printf("%s", "{");
for (int i = 0; i < (size - 1); ++i)
printf("%d, ", arr[i]);
if (size > 0)
printf("%d", arr[size - 1]);
printf("}%s", suffix);
}
static void
fill0(int* first, int* last) {
for ( ; first != last; ++first)
*first = 0;
}
// generate {0,0,...,0,nzeros} combination
static void
init_comb(int comb[], int comb_size, int nzeros) {
fill0(comb, comb + comb_size);
comb[comb_size-1] = nzeros;
}
static int
sum(int* first, int* last) {
int s = 0;
for ( ; first != last; ++first)
s += *first;
return s;
}
// calculated max width required to print number (in PRInumber format)
static int
maxwidth(int comb[], int comb_size, int pattern[], int pattern_size) {
int initial_comb[comb_size];
int nzeros = sum(comb, comb + comb_size);
init_comb(initial_comb, comb_size, nzeros);
return snprintf(NULL, 0, "%" PRInumber,
comb2number(initial_comb, comb_size, pattern, pattern_size));
}
static void
process(int comb[], int comb_size, int pattern[], int pattern_size) {
// print combination and pattern
printa(comb, comb_size, " ");
printa(pattern, pattern_size, " ");
// print corresponding number
for (int i = 0; i < comb[0]; ++i)
printf("%s", "0");
number_t number = comb2number(comb, comb_size, pattern, pattern_size);
print_binary(number);
const int width = maxwidth(comb, comb_size, pattern, pattern_size);
printf(" %*" PRInumber "\n", width, number);
}
// reverse the array
static void
reverse(int a[], int n) {
for (int i = 0, j = n - 1; i < j; ++i, --j)
iter_swap(a + i, a + j);
}
// convert number to pattern
// 101101111110100 -> 1, 2, 6, 1
static int
number2pattern(number_t num, int pattern[], int nbits, int comb[]) {
// SIZE(pattern) >= nbits
// SIZE(comb) >= nbits + 1
fill0(pattern, pattern + nbits);
fill0(comb, comb + nbits + 1);
int i = 0;
int pos = 0;
for (; i < nbits && num; ++i) {
// skip trailing zeros
for ( ; num && !(num & 1); num >>= 1, ++pos)
++comb[i];
// count number of 1s
for ( ; num & 1; num >>=1, ++pos)
++pattern[i];
}
assert(i == nbits || pattern[i] == 0);
const int pattern_size = i;
// skip comb[0]
for (int j = 1; j < pattern_size; ++j) --comb[j];
comb[pattern_size] = nbits - pos;
reverse(pattern, pattern_size);
reverse(comb, pattern_size+1);
return pattern_size;
}
int
main(void) {
number_t num = 11769;
const int nbits = 15;
// clear hi bits (required for `comb2number() != num` relation)
if (nbits < 8*sizeof(number_t))
num &= ((number_t)1 << nbits) - 1;
else
assert(nbits == 8*sizeof(number_t));
// `pattern` defines how 1s are distributed in the number
int pattern[nbits];
// `comb` defines how zeros are distributed
int comb[nbits+1];
const int pattern_size = number2pattern(num, pattern, nbits, comb);
const int comb_size = pattern_size + 1;
// check consistency
// . find number of leading zeros in a flush-right version
int nzeros = nbits;
for (int i = 0; i < (pattern_size - 1); ++i)
nzeros -= pattern[i] + 1;
assert(pattern_size > 0);
nzeros -= pattern[pattern_size - 1];
assert(nzeros>=0);
// . the same but using combination
int nzeros_comb = sum(comb, comb + comb_size);
assert(nzeros_comb == nzeros);
// enumerate all combinations
printf("Combination Pattern Binary Decimal\n");
assert(comb2number(comb, comb_size, pattern, pattern_size) == num);
process(comb, comb_size, pattern, pattern_size); // process `num`
// . until flush-left number
while(next_combination_counts(comb, comb + comb_size))
process(comb, comb_size, pattern, pattern_size);
// . until `num` number is encounterd
while (comb2number(comb, comb_size, pattern, pattern_size) != num) {
process(comb, comb_size, pattern, pattern_size);
(void)next_combination_counts(comb, comb + comb_size);
}
return 0;
}
Выход:
Combination Pattern Binary Decimal
{1, 0, 0, 1, 0} {1, 2, 6, 1} 010110111111001 11769
{1, 0, 1, 0, 0} {1, 2, 6, 1} 010110011111101 11517
{1, 1, 0, 0, 0} {1, 2, 6, 1} 010011011111101 9981
{2, 0, 0, 0, 0} {1, 2, 6, 1} 001011011111101 5885
{0, 0, 0, 0, 2} {1, 2, 6, 1} 101101111110100 23540
{0, 0, 0, 1, 1} {1, 2, 6, 1} 101101111110010 23538
{0, 0, 0, 2, 0} {1, 2, 6, 1} 101101111110001 23537
{0, 0, 1, 0, 1} {1, 2, 6, 1} 101100111111010 23034
{0, 0, 1, 1, 0} {1, 2, 6, 1} 101100111111001 23033
{0, 0, 2, 0, 0} {1, 2, 6, 1} 101100011111101 22781
{0, 1, 0, 0, 1} {1, 2, 6, 1} 100110111111010 19962
{0, 1, 0, 1, 0} {1, 2, 6, 1} 100110111111001 19961
{0, 1, 1, 0, 0} {1, 2, 6, 1} 100110011111101 19709
{0, 2, 0, 0, 0} {1, 2, 6, 1} 100011011111101 18173
{1, 0, 0, 0, 1} {1, 2, 6, 1} 010110111111010 11770