Gerando todos os subconjuntos

Para resolver alguns tipos de problemas, precisamos construir de um algoritmo para gerar todos os subconjuntos para encontrar subconjunto em particular que satisfaz uma dada propriedade.

O algoritmo para construir todos os subconjuntos pode ser usado em algoritmo de busca  exaustiva que consiste em enumerar explicitamente todas os subconjuntos e testá-los   e/ou em um algoritmo de enumeração implícita.

Algoritmo para gerar todos os subconjuntos

#include <stdio.h>
#include <stdlib.h>
int conj[32];
int cont;
void subconjunto(int i, int n){
 int j;
 if(i>n){
  printf("%d subconjunto:",++cont);
  for(j=1;j<=n;j++)
   if(conj[j]==1)
    printf("%d ",j);
  printf("\n");
 }else{
  conj[i] = 1;
  subconjunto(i+1,n);
  conj[i] = 0;
  subconjunto(i+1,n);
 }
}

int main(){
 int n;
 scanf("%d",&n);
 cont = 0;
 subconjunto(1,n);
 return 0;
}

Saída

3
1 subconjunto:1 2 3
2 subconjunto:1 2
3 subconjunto:1 3
4 subconjunto:1
5 subconjunto:2 3
6 subconjunto:2
7 subconjunto:3
8 subconjunto:



Tabela da execução do algoritmo

Gerando todos os subconjunto usando bitsmask
Algoritmo para gerar todos os subconjuntos

#include <stdio.h>
#include <stdlib.h>

int main(){
 int n,i,j;
 scanf("%d",&n);
 
 for(i=0;i<(1<<n);i++){
  printf("subconjunto %d: ",i);
  for(j=0;j<n;j++){
   if((i & (1<<j))!= 0){
    printf("%d ",j+1);
   }
  }
  printf("\n");
 }
 return 0;
}

Saída

3
subconjunto 0:
subconjunto 1: 1
subconjunto 2: 2
subconjunto 3: 1 2
subconjunto 4: 3
subconjunto 5: 1 3
subconjunto 6: 2 3
subconjunto 7: 1 2 3

Registrador de Deslocamento

Um Registrador de Deslocamento é um circuito que desloca de uma posição os elementos de um vetor de bits. O registrador de deslocamento tem uma entrada (um bit) e uma saída (também um bit), e é comandado por um pulso de relógio. Quando o pulso ocorre, o bit de entrada se transforma no bit mais significativo do vetor, o bit menos significativo é jogado na saída do registrador, e todos os outros bits são deslocados de uma posção em direção ao bit mais significativo do vetor (em direção à saída).

Um Registrador de Deslocamento com Retroalimentação Linear (em inglês, lfsr) é um registrador de deslocamento no qual o bit de entrada é determinado pelo valor do ou-exclusivo de alguns dos bits do registrador antes do pulso de relógio. Os bits que são utilizados na retroalimentação do registrador são chamados de torneiras. A figura abaixo mostra um lfsr de 16 bits, com quatro torneiras (bits 11, 13 , 14 e 16).

Fonte: http://br.spoj.pl/problems/REGISTRA/

A configuração das torneiras para a retroalimentação pode ser expressa como um polinômio mod 2. Isso significa que os coeficientes do polinômio pode ser  0 ou 1. Este polinômio é chamado de polinômio de retroalimentação ou polinômio característico. Por exemplo, a configuração das torneiras acima pode ser expressa como o seguinte polinômio mod 2:

$x^{16} + x^{14} + x^{13} + x^{11} + 1$

Este registrador de deslocamento com retroalimentação linear pode ser utilizado para a geração de números pseudo-aleatórios. Um registrador de deslocamento com retroalimentação maximal gera uma sequência pseudo-aleatória periódica e maximal. O polinômio de retroalimentação que gera uma sequência pseudo-aleatória com comprimento maximal é chamado de polinômio primitivo.

Tabela de polinômio primitivos

Considere o seguinte exemplo:

n = 3

O resultado do xor dos bits 2 e 3 será 1. O resultado será deslocado 1 bit para a direita e o bit mais a esquerda será o resultado do xor dos bits 2 e 3.

 unsigned lfsr = 1u;
 unsigned period = 1u;
 unsigned bit;
 
 do {
  
  /* taps: 3 2; characteristic polynomial: x^3 + x^2 + 1 */
  bit  = ((lfsr >> 0) ^ (lfsr >> 1)  ) & 1;
  printf("bit %u\n",bit);
  lfsr =  (lfsr >> 1) | (bit  << 2);
  printf("period %u lfsr %u\n",period, lfsr);
  period++;
 } while(lfsr != 1u);

Saída:

bit 1
period 1 lfsr 4
bit 0
period 2 lfsr 2
bit 1
period 3 lfsr 5
bit 1
period 4 lfsr 6
bit 1
period 5 lfsr 7
bit 0
period 6 lfsr 3
bit 0
period 7 lfsr 1

Paralelismo de bits

O vetor de bits (ou array de bits, bitboard, bitmap) é uma maneira de armazenar e endereçar bits diretamente. Usando essa estrutura, podemos explorar o paralelismo de bits para executar tarefas mais rapidamente e ainda reduzir os requisitos de memória.

Essa técnica está sendo aplicada com sucesso para efetuar operações sobre a matriz de adjacência de um grafo, efetuar operações sobre emparelhamentos de cadeias de caracteres e efetuar operações em jogos de tabuleiro como o xadrez.

As tarefas podem ser executadas mais rapidamente por causa da correspondência direta entre as operações realizadas nessa estrutura e operações bit-a-bit da linguagem C. Por exemplo, existe uma correspondência entre as operações de teoria dos conjuntos e as operações bit-a-bit. A_B representa o vetor de bits definido pelo conjunto A.

A Ç B = AB  & BB A’ = ~ AB AÈ B = AB  | BB (AÈ B)- (A Ç B) = AB  ^ BB

A – (A Ç B) = (AB  ^ BB ) & AB A- B = AB & ~ BB AÍB = AB & ~ BB == Æ

O jogo do sodoku pode ser descrito da seguinte maneira:

Um tabela quadrada com 9 linhas e 9 colunas é dividida em 9 quadrados menores de 3 x 3 como mostrado na figura abaixo. Em algumas das células estão escritos digitos de 1 a 9. As outras células são vazias. O objetivo é preencher as células vazias com dígitos decimais de 1 a 9, um digito por célula, de tal modo que em cada linha, em cada coluna, e em cada subquadrado 3 x 3, todos os dígitos de 1 a 9 apareçam.

Uma variável do tipo inteira de 32 bits pode ser utilizada para representar conjuntos de até 32 elementos. Vamos definir os conjuntos dos números que aparecem em cada linha, coluna e cada subquadrado.

unsigned int linha[9];

unsigned int coluna[9];

unsigned int subquadrado[9];

Toda vez que um número for encontrado na tabela do jogo Sodoku, vamos adicionar no respectivo conjunto. 

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {       

          if(A[i][j] != 0){

               int ii = i / 3;

                int jj = j / 3;

                linha[i]     |=  1<<(A[i][j]-1);

                coluna[j]    |=  1<<(A[i][j]-1);                   

                subquadrado[3*ii+jj] |=  1<<(A[i][j]-1);

          }   

}

}

Para descobrir quais são os valores possíveis para cada célula (i,j), bastar descobrir quais são os elementos do conjunto representado pelo vetor de bits C:

ii = i / 3;

jj = j / 3;

C = linha[i] | coluna[j] | box[3*ii+jj];

C = ~C & ~(1<<9);

Critério de divisibilidade por 3

Os critérios de divisibilidade são regras simples que permitem verificar se um determinado número inteiro A é divisível por um inteiro B baseado em propriedades da sua representação.

Os critérios de divisibilidade podem ser utilizados para realizar de testes de validade para cálculos de somas, subtrações e multiplicações.

Critério de divisibilidade de 3 na base 10

Para desenvolver a regra de divisibilidade por 3, vamos considerar um número n com 4 dígitos na notação decimal abcd.

Logo, um número é divisível por 3, se somente se, a soma dos seus dígitos decimais é divisível por 3.

int sum_dig(int n){
  int s=0;
  while(n>0){
    s = s + n%10;
    n=n/10;
  }
  return s;
}
int mod3(int n){
  while( n >= 10){
    printf("%d = ",n);
    n = sum_dig(n);
    printf("%d mod 3\n",n);
  }
  printf("%d = %d mod 3\n",n,n%3);
  return  n%3;
}
int main(){
  int n;
  while( scanf("%d",&n) && n > 0){
    mod3(n);
  }
}
Saída 

254245
254245 = 22 mod 3
22 = 4 mod 3
4 = 1 mod 3

Critério de divisibilidade na base 2

Vamos desenvolver agora o critério de divisibilidade por 3 na base 2, vamos considerar um número n  com 4 dígitos na notação binária abcd.

Logo, um número é divisível por 3 na base 2, se somente se, a soma dos dígitos binários das posições pares menos os dígitos da posição ímpar é divisível por 3.
Para n < 0, podemos desenvolver a seguinte critério de divisibilidade por 3.

Logo, um número negativo é divisível por 3 na base 2, se somente se, a soma dos dígitos binários das posições ímpares menos os dígitos binários das posições pares é divisível por 3.


Problema 1 Pegar os dígitos nas posições pares.
Em cada byte, precisamos extrair os seguintes bits 01010101 = 55 (hexadecimal).

#define EVEN(n) n & 0x55555555

Problema 2 Pegar os dígitos nas posições ímpares.

Em cada byte, precisamos extrair os seguintes bits 10101010 = aa (hexadecimal).

#define ODD(n) n &  0xaaaaaaaa

Problema 3 Contar os bits ligados um número inteiro. 

Solução 1: 
int count_bits1(int num){
  int count = 0;
  while(num){
    count += num & 1;
    num >>=1;
  }
  return count;
}


Complexidade O(lg N)



Solução 2
int count_bits2(int num)
{
    int count = 0;
    while(num)
    {
          num = num & (num - 1);
          count++;
    }
    return count;
}


Complexidade O(k) k é o número de bits ligados

Solução 3 Construindo uma tabela, em tempo de compilação usando metaprogramação, 

que conta todos os bits ligados em todos os números que podem ser representados 

por 1 byte.

   

Número
   

Binário
   

BitsSetTable256
  
   

0
   

00000000
   

0
  
   

1
   

00000001
   

1
  
   

2
   

00000010
   

1
  
   

3
   

00000011
   

2
  

static const unsigned char BitsSetTable256[256] =
{
# define B2(n) n, n+1, n+1, n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
int count_bits3(int num){
  return BitsSetTable256[num & 0xff] +   

BitsSetTable256[(num >> 8) & 0xff] +   

BitsSetTable256[(num >> 16) & 0xff] +   

BitsSetTable256[num >> 24]; 

}

Algoritmo Final

int mod3(int n){
  while(n>=2 || n <= -2){
    printf("%d = ",n);
    if(n>0){
      n = count_bits3(EVEN(n)) - count_bits3(ODD(n));
    }else{
      //Magnitude de um n�mero negativo
      n = ~n + 1; //complemento de 2 + 1
      n = count_bits3(ODD(n)) - count_bits3(EVEN(n));
    }
    printf("%d mod 2\n",n);  
  }
  if(n<0) { printf("%d = %d mod 2\n",n,n+3); n = n+3; }
  return n;
} 
int main(){
  int n;
  while( scanf("%d",&n) && n > 0){
    mod3(n);
  }
  system("PAUSE");
}

Saída

254245

254245 = 1 mod 3

Números inteiros

Entender a representação dos números inteiros no computador é extremamente importante para evitar certos problemas de precisão e que podem fazer uma solução “certa” ficar errada. Saber o que acontece quando ocorre um overflow/underflow e os limites de cada tipo de dados é bastante valioso durante a codificação de uma solução.

Os números inteiros com sinal são armazenados no computador utilizando a notação binária complemento de 2 mais 1. Nesta notação, o bit mais significativo indica o sinal se o dígito for zero então o número é positivo, caso contrário, o número é negativo. No caso do número negativo, a magnitude, ou seja, o valor absoluto do número é obtido fazendo o complemento do número mais 1.

Tabela dos números representados com 3 bit na notação complemento de 2 mais 1

Binário	Complemento	Complemento +1	Decimal
000			0
001			1
010			2
011			3
100	011	100	-4
101	010	011	-3
110	001	010	-2
111	000	001	-1

Problema 1: Maior Inteiro com sinal positivo

O maior inteiro com sinal pode ser obtido fazendo o bit mais significativo igual a 1 e depois fazendo o complemento.

Problema 2: Menor Inteiro com sinal positivo

O menor inteiro com sinal pode ser obtido fazendo o bit mais significativo igual a 1.

#include <stdio.h>

#include <stdlib.h>

int main(){

  char a,b;

  a = (1<<7);

  b = ~(1<<7);

  printf("CHAR      %2d BIT MIN %20d MAX %d\n",sizeof(a)*8,a,b);

  short c,d;

  c = (1<<15);

  d = ~(1<<15);

  printf("SHORT     %2d BIT MIN %20d MAX %d\n",sizeof(c)*8,c,d);

  int e,f;

  e = (1<<31);

  f = ~(1<<31);

  printf("INT       %2d BIT MIN %20d MAX %d\n",sizeof(e)*8,e,f);

  long long int g,h;

  g = (1LL<<63);

  h = ~(1LL<<63);

  printf("LONG LONG %2d BIT MIN %20lld MAX %lld\n",sizeof(g)*8,g,h);

     

}

Saída

CHAR       8 BIT MIN                 -128 MAX 127

SHORT     16 BIT MIN               -32768 MAX 32767

INT       32 BIT MIN          -2147483648 MAX 2147483647

LONG LONG 64 BIT MIN -9223372036854775808 MAX 9223372036854775807

No caso do long long int, para encontrar o maior e o menor número representado, nós utilizamos a constante 1LL e depois deslocamos para a esquerda 63 bit. Se não for utilizada essa constante, o compilador vai dar o seguinte aviso:

 [Warning] left shift count >= width of type

Problema  4: Maior Inteiro sem sinal

O maior inteiro sem sinal pode ser obtido apenas fazendo o complemento de zero, ou seja, colocando todos os bits setados.

#include <stdio.h>

#include <stdlib.h>

int main(){

  unsigned char a;

  a = ~0;

  printf("CHAR      MAX %u\n",a);

  unsigned short b;

  b = ~0;

  printf("SHORT     MAX %u\n",b);

  unsigned int c;

  c = ~0L;

  printf("INT       MAX %u\n",c);

  unsigned long long int d;

  d = ~0LL;

  printf("LONG LONG MAX %llu\n",d);

     

}

Saída

CHAR      MAX 255

SHORT     MAX 65535

INT       MAX 4294967295

LONG LONG MAX 18446744073709551615

Problema 5: Inicializando um vetor inteiro com memset

int B[100];

memset(B,1,sizeof(B));

O código acima não inicializa o vetor B com 1. A função memset() preenche a memória por chars não por ints.

#include <stdio.h>
#include <stdlib.h>
int main(){
    int INF1 = 0x7FFFFFFF; //constante hexadecimal
    // valor = 2147483647   
    //maior valor inteiro da máquina
   
    int INF2 = ~(1<<31);
    // valor = 2147483647
    //maior valor inteiro da máquina usando operações bit-a-bit
   
    int INF3 = INF2/2;
    // valor = 1073741823
    //maior valor inteiro que pode ser multiplicado por 2 sem dar overflow
    //Por exemplo, no algoritmo do floyd-warshall tem o seguinte condicao
    // if( d[i][j] > d[i][k] + d[k][j]) 
    // este comando pode dar overflow por que d[i][k] e d[k][j] são inicializados com INF
    // ou seja, você está somando dois valores INF.
   
    int INF4 = 0x3FFFFFFF;
    // valor 1073741823
    //maior valor inteiro que pode ser multiplicado por 2 sem dar overflow
   
    int INF5 = 0x3F3F3F3F;
  // valor 1061109567
  //maior valor inteiro que pode ser multiplicado por 2 sem dar overflow
  //que pode ser utilizado para inicializar um vetor com memset
  //memset(m,0x3f,sizeof(m));

}

Tutorial sobre XOR

O XOR (^) é um tipo de disjunção lógica binária que resulta no valor true se exatamente uns dos seus operandos tem o valor true. O XOR goza das seguintes propriedades: 

1. A  ^  B = B ^ A (Comutatividade) 
2. (A ^ B)^ C  = A^ (B^ C) (Associatividade) 
3. A^0 = A (Elemento Neutro) 
4. A^A = 0 (Elemento Inverso)

O XOR é importante por vários motivos:

• Em algumas arquiteturas de computadores, para armazenar 0 em um registrador é mais eficiente realizar a operação XOR com o valor do próprio registrador do que carregar e armazenar o valor zero no registrador.

• O XOR foi um grande desafio para a área de redes neurais. O XOR foi a primeiro exemplo de função que não é linearmente separável. Isso representa que o XOR não pode ser aprendido por um único neurônio artificial e requer uma rede neural multicamada. A área de redes neurais passou um grande tempo para se recuperar desse baque (1969-1982). O problema só foi resolvido como o desenvolvimento de algoritmo de aprendizagem para redes neurais multicamadas.

•  O XOR é utilizado em sistemas RAID para guardar informações de paridade. As informações de paridade são utilizadas para detecção de erros e correção.

• O XOR pode ser utilizado para detectar overflow em operações aritméticas com números binários com sinal.

• O XOR pode ser utilizado também para trocar duas variáveis sem a utilização de variáveis auxiliares.

Vamos tentar entender a importância do XOR analisando os seguintes problemas:

Problema 1 100 pessoas são postas em uma fila e cada uma delas recebe um chapéu, que pode ser preto ou branco. Cada pessoa só consegue ver os chapéus das pessoas que estão a sua frente. É pedido que cada uma delas tente adivinhar a cor do seu chapéu. Cada pessoa pode dizer uma cor em voz alta para que todas as pessoas da fila ouçam. A ordem das perguntas na fila é da última pessoa para a primeira. Qual o máximo número de acertos que se pode garantir, dado que as pessoas podem combinar uma estratégia antes de recebê-los. (Problema extraído da revista Eureka n° 31, 2010)

Podemos facilmente conseguir 50 acertos. Basta dividir as pessoas em pares: (100,99), (98, 97),...(2, 1) e assim o maior número de cada par falar a cor da pessoa da frente. Que apenas precisa repeti-lo, para garantir 1 acerto por par. Mas utilizando a informação de paridade que pode ser obtida aplicado o XOR, podemos conseguir 99 acertos da seguinte maneira. A última pessoa calcula a paridade de todas as 99 pessoas que estão a sua frente se a quantidade for par, ela fala BRANCO e se for ímpar, ela fala PRETO. A próxima pessoa calcula a paridade das pessoas que estão a sua frente, se paridade calculada for igual a paridade calculada pela pessoa antes dela na fila então o seu chapéu é BRANCO, caso contrário, o seu chapéu será PRETO. Ela sempre fala a paridade calculada por ela.

Vamos considerar o seguinte exemplo:

5	4	3	2	1
0	1	1	0	1

1.    A última pessoa (pessoa 5) calcula a paridade dos chapéus visíveis por ele. A quantidade é ímpar então ele fala PRETO.

2.    A próxima pessoa (pessoa 4) calcula a paridade dos chapéus visíveis por ele. A quantidade é par e quantidade calculada pela pessoa anterior foi ímpar(Ela disse PRETO). Logo, o seu chapéu é PRETO. Ela fala BRANCO.

3.    A próxima pessoa (pessoa 3) calcula a paridade dos chapéus visíveis por ele. A quantidade é ímpar e quantidade calcula pela pessoa anterior foi par (Ela disse BRANCO) então o seu chapéu é PRETO. 

Problema 2 O algoritmo de troca de valores de duas variáveis utiliza uma variável auxiliar para realizar a operação da seguinte maneira:

temp = a

a = b

b = temp

Podemos utilizar o XOR para realizar esta operação sem precisar de uma variável auxiliar.

troca_xor(a,b)

a = a^ b (1)

b = a^ b (2)

a = a^ b (3)

Na primeira linha, temos que a = a ^ b. Substituindo o valor de a (1) na equação (2) , temos:

b = a^ b^ b

b = a^ (b^ b) Associatividade

b = a^ 0 Elemento Inverso

b = a Elemento Neutro

Substituindo o valor de a (1) e b(2) na equação (3), temos:

                                   a = a^ b

                                   a = a^ b^ a (Comutatividade)

                                   a = a^ a^ b (Associatividade)

                                   a = (a  ^ a)^ b Elemento Inverso

                                   a = 0^ b Elemento Neutro

                                   a = b

 

Problema 3 Um vetor com n-1 inteiros armazena valores [1..n]. Somente um valor está faltando, descubra qual é o número que está faltando.

Estratégia 1: Utilize um vetor marc para guardar os valores que estão no vetor.

cin >> n;

int vet[n-1];

int marc[n];

memset(marc,0,sizeof(marc));

for(i=0;i<n-1;i++){

  cin >> vet[i] ;

  marc[vet[i]-1] = 1;

}

for(i=0;i<n;i++)

   if(marc[i]==0)

     cout << "Valor faltando: " << i+1 << endl;

Complexidade de espaço extra: O(n)

Estratégia 2: Calcula a soma de todos os números entre 1 e n e soma o valor de todos os valores que estão no vetor e depois fazer a diferença.

int n,i;

int soma,total;

cin >> n;

int vet[n-1];

total = ((1+n)*n)/2;

soma = 0;

for(i=0;i<n-1;i++){

  cin >> vet[i] ;

  soma += vet[i];

}

cout << "Valor faltando: " << total - soma << endl;

           

Complexidade de espaço extra = O(1)

Problema: Pode ocorrer overflow no cálculo da soma e do total.

Estratégia 3:

int n,i;

int total;

cin >> n;

int vet[n-1];

total = 0;

for(i=1;i<=n;i++)

  total ^= i;

for(i=0;i<n-1;i++){

  cin >> vet[i] ;

  total ^= vet[i];

}

cout << "Valor faltando: " << total << endl;

Explicação:

Entrada

n=3, v = {2,1}

total = 1^  2^ 3

total = total ^ v[0] = 1^ 2^ 3^ 2 = 1 ^ 3

total = total ^ v[1] = 1^ 3^ 1 = 3

Valor que está faltando : 3 

Problema 4 Alice e Bob estão em ilhas separadas. Bob está doente, e Alice tem o medicamento. Eva tem um barco e uma caixa que pode ser bloqueado. Ela está disposta a transportar objetos entre Alice e Bob, mas apenas na caixa, e se a caixa estiver aberta, ela vai roubar o que está dentro. Se Alice e Bob tem cadeados e chaves de tal forma que a sua própria chave só abre o seu próprio cadeado, como Alice envia Bob o medicamento de forma que Eva não vai roubá-lo? e o que precisamos assumir para que esse transporte aconteça?

1° Alice coloca o medicamento na caixa e coloca o seu cadeado.

2° Eva leva a caixa para Bob

3° Bob coloca seu cadeado junto com o cadeado de Alice

4° Eva traz a caixa de volta para Alice

5° Alice retira seu cadeado, evidentemente 'deixando' o cadeado de Bob pois ela não possui a chave

6° Eva leva a caixa para Bob

 7° Bob agora pode abrir a caixa e retirar o seu medicamento

Problema 5 Alice e Bob novamente estão em ilhas separadas. Alice quer enviar um inteiro de 32 bits em segredo para Bob. Ela pode enviar um inteiro de 32 bits para Bob atráves de Eva. Eva pode ver o inteiro que ela está levando! Como Bob pode enviar para Alice esse número sem que Eva descubra que número é esse?

Dica: Alice e Bob podem utilizar o operador binário XOR.
Solução:
Seja A um número secreto escolhido por Alice e B um número secreto escolhido por Bob.
Seja X o número que Alice quer enviar em segredo para Bob.

1° Alice envia para Bob X ^ A .

2° Bob envia X^A ^B

3° Alice envia para BOB X^A ^B ^A

4° Bob descobre o número enviado aplicando X ^A ^B^A^B 

Desafio Um vetor com n+1 inteiros armazena valores [1..n]. Somente um valor está duplicado, descubra qual é o número que está duplicado usando XOR.