Fórum de Matemática | DÚVIDAS? Nós respondemos!
https://forumdematematica.org/

Como saber o número de subconjuntos que um número inteiro pertence?
https://forumdematematica.org/viewtopic.php?f=19&t=8352		 Página 1 de 1
Autor:  allexandrefsr [ 30 mar 2015, 13:20 ]
Título da Pergunta:  Como saber o número de subconjuntos que um número inteiro pertence?
Bom dia,

Este é meu primeiro post, acredito que eu esteja na seção correta. Minha dúvida é a seguinte:

Dado que eu tenho um conjunto de números inteiros N = {1, 2, 3, ..., n}, eu sei que existem 2n-1 subconjuntos possíveis, dado pelas combinações entre cada um dos seus elementos. Eu gostaria então de saber a quantos desses subconjuntos, cada um dos meus elementos pertence, como exemplo, a quantos destes subconjuntos meu número 2 pertenceria? Preciso saber disso para terminar de implementar computacionalmente, pois meu conjunto N tem 100 elementos, o que me leva a 1.267.650.600.228.230.000.000.000.000.000 de subconjuntos...

Espero que tenha conseguido ser totalmente claro.

A função que eu gero os subconjuntos (S) e seus complementos (S_) em C++ é:

Código:
void SubsetGen(vector<vector<int > > &S, vector<vector<int > > &S_, int i, int n){
  int k_max = pow(2,n); //máximo de subconjuntos possíveis

 //adicionara o nó 'i' ao subconjunto se ele fizer a condição válida
 //set S {k in artificial_set} ordered := {i in V_: k div 2**(ord(i) - 1) mod 2 = 1};
  for (int k = 0; k <= (k_max-1); k++){ //percorrendo os subconjuntos possíveis
    int i_aux = i;
    for(int pos = 1; pos <= n+1; pos++){
        if (int(floor(k/pow(2,(pos-1))))%2 == 1){
            S[k].push_back(i_aux); //adiciona ao fim da lista
            i_aux++;
        }
        else{
            S_[k].push_back(i_aux);
            i_aux++;
        }
    }
  }
}


Muito obrigado,

Allexandre.
Autor:  Sobolev [ 31 mar 2015, 10:55 ]
Título da Pergunta:  Re: Como saber o número de subconjuntos que um número inteiro pertence?
Bom dia,

Pode pensar do seguinte modo, os conjuntos a que certo elemento pertence são formados pela união do conjunto formado apenas por esse elemento com qualquer subconjunto formado pelos restantes. O número de subconjuntos formados com os restantes (n-1) inteiros pode ser obtido com a mesma fórmula que referiu. Assim, tomando o seu exemplo com o número 2, começamos por determinar o número de subconjuntos de {1,3,4, ..., n}, que será de \(2^{n-1}\) (incluindo o conjunto vazio). Este é exactamente o número de subconjuntos que inclui o inteiro 2. No caso de n=100 terá 2^99= 633.825.300.114.114.700.748.351.602.688 conjuntos nessas coindições.
Autor:  allexandrefsr [ 01 abr 2015, 13:51 ]
Título da Pergunta:  Re: Como saber o número de subconjuntos que um número inteiro pertence?
Sobolev Escreveu:
Bom dia,

Pode pensar do seguinte modo, os conjuntos a que certo elemento pertence são formados pela união do conjunto formado apenas por esse elemento com qualquer subconjunto formado pelos restantes. O número de subconjuntos formados com os restantes (n-1) inteiros pode ser obtido com a mesma fórmula que referiu. Assim, tomando o seu exemplo com o número 2, começamos por determinar o número de subconjuntos de {1,3,4, ..., n}, que será de \(2^{n-1}\) (incluindo o conjunto vazio). Este é exactamente o número de subconjuntos que inclui o inteiro 2. No caso de n=100 terá 2^99= 633.825.300.114.114.700.748.351.602.688 conjuntos nessas coindições.


Obrigado Sobolev,

Acabei percebendo isso, mas revisando meu problema, acabei descobrindo que ele tem uma grande maneira de ser simplificado. \(\forall i \in N = \{1,...,100\}, \exists N_i \subseteq N.\). Cada um destes subconjuntos \(N_i, \forall i \in N\), chamado de vizinhança de i, contém o inteiro i (referente a um ponto no plano cartesiano) e os índices dos 9 outros pontos mais próximos a ele. Assim, eu só me interesso pelos subconjuntos de \(N_i, \forall i \in N\) que também contém i. Meu real problema agora reside em como gerar somente os subconjuntos de \(N_i, \forall i \in N\) que contenham i.

Vocês tem alguma ideia de como fazer isso?

Muito obrigado,

Allexandre.
Autor:  allexandrefsr [ 01 abr 2015, 14:00 ]
Título da Pergunta:  Re: Como saber o número de subconjuntos que um número inteiro pertence?
allexandrefsr Escreveu:
Sobolev Escreveu:
Bom dia,

Pode pensar do seguinte modo, os conjuntos a que certo elemento pertence são formados pela união do conjunto formado apenas por esse elemento com qualquer subconjunto formado pelos restantes. O número de subconjuntos formados com os restantes (n-1) inteiros pode ser obtido com a mesma fórmula que referiu. Assim, tomando o seu exemplo com o número 2, começamos por determinar o número de subconjuntos de {1,3,4, ..., n}, que será de \(2^{n-1}\) (incluindo o conjunto vazio). Este é exactamente o número de subconjuntos que inclui o inteiro 2. No caso de n=100 terá 2^99= 633.825.300.114.114.700.748.351.602.688 conjuntos nessas coindições.


Obrigado Sobolev,

Acabei percebendo isso, mas revisando meu problema, acabei descobrindo que ele tem uma grande maneira de ser simplificado. \(\forall i \in N = \{1,...,100\}, \exists N_i \subseteq N.\). Cada um destes subconjuntos \(N_i, \forall i \in N\), chamado de vizinhança de i, contém o inteiro i (referente a um ponto no plano cartesiano) e os índices dos 9 outros pontos mais próximos a ele. Assim, eu só me interesso pelos subconjuntos de \(N_i, \forall i \in N\) que também contém i. Meu real problema agora reside em como gerar somente os subconjuntos de \(N_i, \forall i \in N\) que contenham i.

Vocês tem alguma ideia de como fazer isso?

Muito obrigado,

Allexandre.


Um ponto que esqueci de falar, que a cardinalidade de \(N_i, \forall i \in N\) é de 10 elementos, assim, a cardinalidade dos seus subconjuntos é menor ou igual a 10.
Autor:  Sobolev [ 01 abr 2015, 15:46 ]
Título da Pergunta:  Re: Como saber o número de subconjuntos que um número inteiro pertence?
A escolha dos conjuntos \(N_i\) não parece a mais evidente, já que esses conjuntos não são simétricos relativamente ao inteiro i. É preciso pois especificar um pouco melhor como é obtida. Por exemplo, considera que

\(N_{10} = \{6,7,8,9,10,11,12,13,14,15\}\)

ou

\(N_{10} = \{5,6,7,8,9,10,11,12,13,14\}\)?
Página 1 de 1 Os Horários são TMG [ DST ]
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/