0

I want to generate a subsets of size n = 0, 1, 2, ... of a set of numbers.
There should not be repetition of the same numbers with different order, like 2-3-4 = 3-2-4 = 4-2-3 = 4-3-2

e.g. 

vector<unsigned int> list = {2,4,6,8,9}

so subsets will be like,

n=0 {}

n=1 {2}{4}{6}{8}{9}

n=2 {2,4}{2,6}{2,8}{2,9}{4,6}{4,8}{4,9}{6,8}{6,9}{8,9}
Kiril Kirov
  • 37,467
  • 22
  • 115
  • 187
DataMiner
  • 325
  • 1
  • 3
  • 16
  • Here is a similar question: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – Vaughn Cato Oct 14 '11 at 15:21

3 Answers3

3

Generate all binary numbers of length equal to your number of numbers.

3 numbers:
000
001
010
011
100
101
110
111

Next choose the numbers according to position and map them to the according set (i.e. if 001, you would map it to 1, for 101 you would map it to 3).

For initial set {1,2,3}:

{}      ->0
{3}     ->1
{2}     ->1
{2,3}   ->2
{1}     ->1
{1,3}   ->2
{1,2}   ->2
{1,2,3} ->3

I'm just giving you an idea because this seems like homework and this isn't a homework solving site. This should give you a starting point.

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
  • I was about to argue that this doesn't scale well for large `n`, but then realized if `n` gets that big, there's not enough space on the computer to generate all the answers. So nevermind. – Mooing Duck Oct 14 '11 at 17:08
1

Most algorithms work by generating all possible subsets and then take the ones you want [ here its length ].

One of the ideas you can use is recursion . Abstracted so you do your homework .

Consider a given set G = {1,2,3} for which you have to find subsets .

Maintain a set Y = { {} } to start with .

Step 1 : 1 may or may not be there . Y = { {1} , {} } . G = {2,3}

Step 2 : 2 may or may not be there . Y = { {1,2} , {2} , {1} , {} } . G = {3} .

Ans it goes till G != {}

Anil Shanbhag
  • 950
  • 1
  • 13
  • 31
0

For the subsets, the rule is

"There are at least two subsets: null and the set itself. All subsets count is always = 2^(n), which n is the number of elements in the set."

You can use recurisve-backtracking to solve this.