How to create all subset of a set in C#?

Question

I mean if user add the amount of a set and add his/ her numbers at the end compiler gives and calculate all of the subsets of the set which have been created. for example: size of set: 3 parameters of set: 5  3 2 result: {5} {3}  {32}  {2}  {}  {352}  {52}  {35}

Vulpes · Answer

Here's a reasonably efficient implementation of that. Please note that 1. I've limited the number of members of the set to 16 (65536 subsets) so that they all print out in a reasonable time. 2. The results are in a different order to yours (which I don't recognize?) and always start with the empty subset and end with the full set. Moreover the order of members within each subset is the same as the original set. 3. If the user enters something that isn't a valid integer 0 will be substituted. 4. If the members of the set include duplicates so will the subsets. 5. If there are 'n' members of the set then the program works by considering the bits of each binary number between 0 and (2^n - 1). If the bit is 1 then the corresponding member of the set is added to the subset. This is an easy way of ensuring that all possible subsets are considered. using System; using System.Collections.Generic; class Program { static int n; static int[] set; static List subset; static byte[] binary; static void Main() { do { Console.Write(Size of set (1 to 16) : ); int.TryParse(Console.ReadLine() out n); } while(n 16); set = new int[n]; subset = new List (n); binary = new byte[n]; string[] items; do { Console.Write(Parameters of set : ); string input = Console.ReadLine(); items = input.Split(''); if (items.Length != n) { Console.WriteLine(There must be exactly {0} parameters n); } } while(items.Length != n); for(int i = 0; i { int.TryParse(items[i] out set[i]); } Console.WriteLine(); int size = 2 for(int i = 0; i { Printsubset(); BinaryIncrement(); } Console.ReadKey(); } static void BinaryIncrement() { for(int i = n - 1; i >= 0; i--) { if (binary[i] == 0) { binary[i] = 1; return; } binary[i] = 0; } } static void Printsubset() { subset.Clear(); for(int i = n - 1; i >= 0; i--) { if (binary[i] == 1) subset.Add(set[n - 1 - i]); } Console.Write({); Console.Write(String.Join( subset)); } } Sample output: Size of set (1 to 16) : 3 Parameters of set : 5 3 2 {} {5} {3} {53} {2} {52} {32} {532}

Vulpes · Answer

The program is not in fact particularly complex and is much easier to understand than a lot of the code you'll find on the internet for generating combinations. Apart from getting the input the code which actually extracts the subsets and prints them to the console is as follows: // within Main() method binary = new byte[n]; // ... int size = 2 for(int i = 0; i { Printsubset(); BinaryIncrement(); } static void BinaryIncrement() { for(int i = n - 1; i >= 0; i--) { if (binary[i] == 0) { binary[i] = 1; return; } binary[i] = 0; } } static void Printsubset() { subset.Clear(); for(int i = n - 1; i >= 0; i--) { if (binary[i] == 1) subset.Add(set[n - 1 - i]); } Console.Write({); Console.Write(String.Join( subset)); } This approach relies on the fact that for a set of 'n' elements there are 2 ^ n subsets including the empty set and the set itself. Moreover if we generate all binary integers from 0 to 2 ^ n - 1 the presence of the '1' or '0' bits will indicate the presence or absence of the corresponding members of the set in the subset in question. For example consider the case of the set {1 2 3} which has 2 ^ 3 = 8 subsets. The binary numbers from 0 to 7 and the corresponding subsets are: 000 -> {} 001 -> {1} 010 -> {2} 011 -> {1 2} 100 -> {3} 101 -> {1 3} 110 -> {2 3} 111 -> {1 2 3} When we create the binary array all its elements are set to zero by default. All we need to do then is to keep adding 1 until we've generated and printed all 8 subsets. The BinaryIncrement method is very simple. If the final digit is 0 then we change it to 1 and we're done. Otherwise we change it to 0 and consider the penultimate digit and keep on going like this until we find a digit which is already 0. Your sample output is the same as mine except that it's in a different order. There's no way I can reproduce that order as it doesn't seem to represent any recognizable pattern. If you've been told to do this exercise using a particular algorithm which leads to that output then you should of course use that algorithm rather than the one I've used.

Joe Wilson · Answer

Thank you for your answer but it was so complex and please respond again and the output in this respond just contain {5} {3}  {32}  {2}  {}  {352}  {52}  {35}. Best wishes