Algoritmo para gerar subconjunto de números inteiros

[Neokratox]

E ai pessoa, beleza?

 

Estou programando e tenho um conjunto de n números inteiros, de , V' = {1, 2, 3, ..., n}

 

Preciso gerar um código que me gere os 2ⁿ - 1 subconjuntos possíveis. ou seja, como exemplo, se tenho um V' = {1,2,3,4}

Terei: {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1, 2, 3}, {4}, {1,4}, {2,4}, {3,4}, {1,2,4},{1,3,4} {2,3,4}, {1,2,3,4}

 

Valeu!!

[rjjj]

Em Teoria dos Conjuntos, a ordem dos elementos e a repetição de elementos em um conjunto ou subconjunto não é importante, sendo idêntico nesse aspecto à combinação simples da Análise Combinatória .

 

 

 

Tendo o conjunto inicial, use um algoritmo combinatório para formar grupos (combinações simples) contendo 1 elemento, 2 elementos, etc, até grupos de n elementos. Esses grupos praticamente seriam os subconjuntos possíveis .

 

 

 

Matematicamente, tem-se C_n,1 + C_n,2 + C_n,3 + ... + C_n,n = 2ⁿ - 1.

 

 

 

Espero ter ajudado .

[Neokratox]

Vetor-de-listas.txtEm Teoria dos Conjuntos, a ordem dos elementos e a repetição de elementos em um conjunto ou subconjunto não é importante, sendo idêntico nesse aspecto à combinação simples da Análise Combinatória .

 

 

 

Tendo o conjunto inicial, use um algoritmo combinatório para formar grupos (combinações simples) contendo 1 elemento, 2 elementos, etc, até grupos de n elementos. Esses grupos praticamente seriam os subconjuntos possíveis .

 

 

 

Matematicamente, tem-se C_n,1 + C_n,2 + C_n,3 + ... + C_n,n = 2ⁿ - 1.

 

 

 

Espero ter ajudado .

 

Deu quase certo, rs. Consegui gerar da forma em anexo. Porém, estou com dificuldades agora para acessar os itens da lista, ou seja, não consigo ver o tamanho da lista e quais itens estão contidos nela.

 

Valeu!

 

[LNW]

@Neokratox

 

 

Se notar bem, percebe-se que isso aí tem uma relação com números binários.. 2⁴ = 16, sendo o primeiro conjunto, vazio (todos os bits desligados).

 

Cada conjunto de bit ligado representaria um conjunto.

 

Então:

 

v[] = {1, 2, 3, 4};

 

0001 = 1 = { v[0] }
0010 = 2 = { v[1] }
0011 = 3 = { v[0], v[1] }
0100 = 4 = { v[2] } (terceiro bit ligado)
0101 = 5 = { v[0], v[2] } (primeiro e terceiro bits ligados)

...

1111 = 15 = { v[0], v[1], v[2], v[3] } (todos os bits ligados)

 

 

A ideia então será montar uma função para gerar justamente esses índices com base no número do conjunto que se deseja saber. Neste caso, os números vão variar de 1..15 (todos). Nesta função, você testaria todos os bits e verificaria qual estaria ligado e determinaria o índice.

 

Bom, é uma forma de fazer..

 

 

 

PS: De que anexo você está falando?

 

 

 

LNW