combinacoes.c

#include <stdio.h>
/*
 * Para compilar e executar
 * gcc -std=c11 % && time ./a.out
 */

/* isto aqui é magica pra mim. Magia negra */
unsigned long long int nexthi_same_count_ones(unsigned long long a) {
  /* works for any word length */
  unsigned long long int c = (a & -a);
  unsigned long long int r = a+c;
  return ((((r ^ a) >> 2) / c) | r);
}

/* faz o shift de bits 64 vezes imprimindo o contador para cada bit ligado */
void print_sequence(unsigned long long int bit_seq){
  for (char i = 1; i <=64 ; i++) {
    if (bit_seq & 0x1LL) {
      printf("%d ", i);
    }
    bit_seq = bit_seq >> 1;
  }
  puts("");
}

int main(){
  /* a forma de representacao utiliza 60 bits de uma variavel de 64 bits */
  /* se o n'ésimo bit estiver ligado é porque faz parte da combinação */
  unsigned long long int limit= 0x0fc0000000000000LL; /* representa a combinação 54 55 56 57 58 59 60 */
  unsigned long long int candidate= 0x000000000000003fLL; /* representa a combinação 1 2 3 4 5 6 */
  unsigned long int counter = 1; 
  while (candidate < limit) {
    candidate = nexthi_same_count_ones(candidate);
    if (counter % 1000 == 0) print_sequence(candidate); /* Imprime uma a cada 1000 sequencias */
    counter++; 
  }
  printf("Numero de combinacoes: %d\n", counter); 
  puts("ultima combinacao:");
  print_sequence(candidate);
  puts("End of program.");
  return 0;
}