Como saber o número de subconjuntos que um número inteiro pertence?

[allexandrefsr]

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 2ⁿ-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.

[Sobolev]

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.

[allexandrefsr]

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.

[allexandrefsr]

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.

[Sobolev]

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\}\)?