[Java] Print out all the subsets in a set

[Moy]

In my Algebra Class, we are asked to print out all the subsets in a set.

Example Output:
Type the number of elements: 3

Enter Element : 1
Enter Element : 2
Enter Element: 3
Name of the set: A

A = {1,2,3}

The subsets are:

A = { }
A = {1}
A = {1,2}
A = {2,3}
A = {2}
A = {1,3}
A = {3}
A = {1,2,3}

Additional Info: To get the number of subsets in a set, 2 raise to (number of elements)

Advance thanks and I hope someone could help me. BTW please use array.

 

[Menag]

Additional Info: To get the number of elements in a set, 2 raise to (number of elements)

Do you mean power set? And that one would inculde the set itself, thus you would have:

A = { }
A = {1}
A = {1,2}
A = {2,3}
A = {2}
A = {1,3}
A = {3}
A= {1,2,3}

otherwise the power set would have 7 elements, which isn't equal to 2^3 = 8
Well anyway, to your problem, i might look into this!

edit: got an idea, try it with recursion:
if A={}, its power set is {{}}
if A={a,.....}, its power set is the power set of {...} combined once with every subset of {a}, thus
for every subset B of {...} you have once {a} union B and {} union B

gonna try makeing it in java if you want me to...

 

[Rui]

Do they need to come in any specific order? Can elements repeat themselves?

 

[Menag]

I actually made a version in Java, although i'd prefer doing all this stuff without arrays (for example using a set) and in general i somehow don't like my solution. If you want i can show it to you, but I'd prefer if you try it yourself first...

 

[Rui]

I actually do like arrays. I've been thinking about this... for one or two hours ._.' I didn't have algebra yet so I'm clueless if there are any rules to this, but I think I'm getting somewhere, I'm finding patterns with Pascal's triangle and so.

 

[Menag]

If he really means the power set, you don't need any algebra! It's simple set theory! An idea using recursion I wrote above!

 

[Moy]

My professor said that it must be in algorithm or in other words it must be in order. And I really don't quite understand algorithm and I'm just a newbie in java.

EDIT:
WTF!

Additional Info: To get the number of elements in a set, 2 raise to (number of elements)

I mean this:
Additional Info: To get the number of elements subsets in a set, 2 raise to (number of elements)

 

[Dr Super Good]

in other words it must be in order

Except a set is not in any order by definition. You are being contradicting.

Can elements repeat themselves?

Obviously not as a Set cannot contain duplicate elements. If it does then it cannot be called a Set.

Anyway I have no idea how you would go about generating them in the order you showed since Sets have no order. However there are several ways to generate such sets.

1. Brute force way. You make the generated sets themselves comparable and put them in a set to guarantee uniqueness. You then add all sets made from the permutations of 0...N elements from the N sized source set. As the Set filters out duplicates, you will be left with the power set. This method basically requires no thinking, only works on small sets due to time constraints and is bad for the environment.

2. Smart way. Like the above expect instead of using permutations, you use combinations. This Dramatically cuts down on processing time as you no longer need to check for element uniqueness and avoid computing unnecessary sets. This time you create sets from all combinations size 0...N from a Set of size N. This can be done using a recursive approach which I will try and outline below.

1. Get your source Set size N
2. Allocate a Stack size N of Set indicies
3. Add Empty set to output
4. Push index 0 onto stack.
5. Loop forever
5.1. Generate a set from the stack where each level represents the position value of elements to add to it from the source set and add this to output.
5.2. Read top of stack to x
5.3. Increment x
5.4. If x < N then
5.4.1. Push x to stack
5.5. Else
5.5.1. Pop top of stack
5.5.2. If stack size == 0 then
5.5.2.1. Break loop at 5.
5.5.3. Pop top of stack to x
5.5.4. Increment x by 1
5.5.5. Push x to stack
6. return output

I am not sure if it is completely correct but it should work. Obviously nested function calls would also work as a source for the stack but that might overload the thread stack for large sets and also could end up slower due to excessive function calls and argument passing.

3. You can use the ultra efficient approach specifically designed for computers. A power set of the Set size N is basically the brute force computation from 0 to 2^N of a bit mask where each bit represents an element from the set.

Using this approach you eliminate the need for stacks or any complex recursion in place for very simple recursion. The only tricky part is resolving the mask back into a set where a brute-force bit approach would take O(N) to execute. This would give the algorithm a total complexity of O(N*2^N) which is slower than the O(2^N) of method 2. The main advantage of this approach is the simplistic iteration where each cycle has no required dependency on the previous cycle (as you are iterating through a set of numbers). Using this property you can easily multi-thread the algorithm and make it massively scalable as opposed to method 2 which cannot be multi-threaded efficiently (if not at all).

 

[Menag]

I am not sure if it is completely correct but it should work. Obviously nested function calls would also work as a source for the stack but that might overload the thread stack for large sets and also could end up slower due to excessive function calls and argument passing.

For normal computers it doesn't rly matter if you use nested function calls or not. You won't get past the powerset of a set with more then ~25 elements. This would mean creating 2^25 = 33554432 arrays and filling them with data. At least my program crashed with that one because the heap space. The iterated functioncalls are just a very small part of it. The space the functioncalls need is increasing linear, while the space of the rest increases exponential (2^n). Thus, for the jump from 24->25 you will need double as much space for the arrays and shit while only a small amount of space for the functioncall!

 

[GhostWolf]

function _powerset(map, array) {
  map[array.join()] = true
  
  for (var i = 0, l = array.length; i < l; i++) {
    var subset = array.slice(); // Make a copy of the array
    
    subset.splice(i, 1); // Remove ith element
    
    _powerset(map, subset);
  }
  
  return map;
}

function powerset(array) {
  return Object.keys(_powerset({}, array));
}

> powerset([1, 2, 3, 4])
["1", "2", "3", "4", "1,2,3,4", "2,3,4", "3,4", "", "2,4", "2,3", "1,3,4", "1,4", "1,3", "1,2,4", "1,2", "1,2,3"]

+5 imagination
-10 probably not what you want

 

[Moy]

@GhostWolf: Can you please simulate your code? So that I/we can understand it well.

@Menag: Can I see your program code?

I'm really having trouble with the order of the subsets. Sometimes I get INFI Loop

 

[GhostWolf]

The idea of my code is to recursively iterate over a subset of the input, where the ith element is removed.

If the input is {1, 2, 3}, then you get these iterations:

{1, 2, 3}

  {2, 3} // i=1
    {3} // i=1
      {} // i=1
    {2} // i=2
      {} // i=1

  {1, 3} // i=2
    {3}
      {}
    {1}
      {}

  {1, 2} // i=3
    {2}
      {}
    {1}
      {}

This creates many duplicates, so instead of using an array as the output, I use a map (set, hashmap, table, or whatever a language decides to call it), so each time a duplicate is found, it simply overwrites the same key.

At the end you pick all the keys of the map and create an array from them, which is the powerset.

 

[Menag]

/**
 * Removes the first element of an array
 * 
 * @param array
 * @return the resulting array
 */
public static int[] removeFirst(int[] array) {
	int[] result = new int[array.length - 1];
	for (int i = 1; i < array.length; i++) {
		result[i-1] = array[i];
	}
	return result;
}
	
/**
 * Adds an element to an array.
 * 
 * @param elem
 * @param array
 * @return the given array with the element at its end
 */
public static int[] addElementToArray(int elem, int[] array) {
	int[] result = new int[array.length + 1];
	for (int i = 0; i < array.length; i++) {
		result[i] = array[i];
	}
	result[array.length] = elem; 
	return result;
}

/**
 * Adds an element to every element of the given 2d array.
 * 
 * @param elem
 * @param array
 * @return
 */
public static int[][] addElementToArrays(int elem, int[][] array) {
	int[][] powerSet = new int[2 * array.length][];
	for (int i = 0; i < array.length; i++) {
		powerSet[i] = array[i];
	}
	for (int i = array.length; i < powerSet.length; i++) {
		powerSet[i] = addElementToArray(elem, array[i - array.length]);
	}
	return powerSet;
}
	
/**
 * Calculates the power set of a given set and returns an array
 * containing all the subsets of the given set.
 * 
 * @param set
 * @return the power set
 */
public static int[][] powerSet(int[] set) {
	if (set.length == 0) {
		int[][] powerset = {new int[0]};
		return powerset;
	} else {
		return addElementToArrays(set[0], powerSet(removeFirst(set)));
	}
}

edit: just want to mention that i'd also prefer doing it with a set datastructur but since you said arrays only...

 

[Dr Super Good]

He said Set, Set is already a java.util interface with clearly defined behaviour. If not then why did he mention Set in a Java context...

GhostWolf, you can avoid duplicate results and it is recommended to do so for performance. Both my method 2 and 3 should not produce duplicate results and thus save on the need to test for duplicates.

 

[Menag]

He said Set, Set is already a java.util interface with clearly defined behaviour. If not then why did he mention Set in a Java context...

How about you read his post once at least?

BTW please use array.

and well, it's about the mathematical structure "set", how you implement that is the question and he wants to have arrays.

 

[Rui]

Well, today I went to see the problem again and in 5 minutes I magically figured out an easy solution, somehow, after being braindead of playing DotA. The solutions you guys presented seem fairly complicated though.

 

[Dr Super Good]

How about you read his post once at least?
In my Algebra Class, we are asked to print out all the subsets in a set.

Then he went on to contradict himself...

Advance thanks and I hope someone could help me. BTW please use array.

My professor said that it must be in algorithm or in other words it must be in order. And I really don't quite understand algorithm and I'm just a newbie in java.

Which violates set restrictions as the meaning of a set is that it cannot be ordered.

So how about you stop thinking I did not read his posts and try help the guy?

and well, it's about the mathematical structure "set", how you implement that is the question and he wants to have arrays.

Except he wants it ordered which violates set restrictions. Yes you can get an ordered view of a set but the set itself is still an unordered collection of unique elements.

In any case everything I said can apply to an array backed set. People generally avoid only using only an array backed set because it is too inefficient to check for uniqueness when adding elements to it so instead they use hybrids which have some kind of map or tree to speed things up.

Well, today I went to see the problem again and in 5 minutes I magically figured out an easy solution, somehow, after being braindead of playing DotA. The solutions you guys presented seem fairly complicated though.

So why not post your solution? People might be able to learn from it...

 

[Menag]

God, are you serious?
He wants a set represented by an array. And of this set he wants the power set in a specific order, everything represented by arrays.
IT DOESN'T FUCKING MATTER THAT A SET USUALLY DOESN'T HAVE AN ORDER

PS: Set theory can prove that every set is well-ordered thus there's actually at least one order in every set.

 

[Dr Super Good]

PS: Set theory can prove that every set is well-ordered thus there's actually at least one order in every set.

The order in which the elements of a set or multiset are listed is irrelevant (unlike for a sequence or tuple).

Not according to Wikipedia.

 

[Menag]

Just shows me that you actually have no idea what you're talking about.

 

[Dr Super Good]

Just shows me that you actually have no idea what you're talking about.

It shows me you have no idea what a set is...

Sets have no order because they are a collection of unique elements. Come on, this is the kind of stuff they teach you in first year.

Although to represent a set you do define an order, that order has no influence on the meaning of a set.

{1,2} == {2,1} as long as 1 == 1 and 2 == 2 and 1 != 2 and {x} represents a set containing x.

 

[Menag]

And that's the problem, it's the stuff they teach you in FIRST year. Afterwards, real set theory comes in.
I said you can define a well-order on every set, thus there exists at least one order in every set. Still, the set {a,b,c}={a,c,b}={a,b,c,b,a}.
Although the order in a set doesn't matter if the set is equal to another or not, it doesn't mean that you can't order it. And that's the whole point.

 

[Dr Super Good]

Yes but that is still an ordered view. Every set is not well-ordered but can be well-ordered as well-ordering is a relationship that together with its accompanying set becomes a well-ordered set.

A set itself has no order. A well-ordered set can be created from any set by using well-ordering with a domain of that set. A well-ordered set does have an order and is different from a set.

 

[Menag]

Except a set is not in any order by definition. You are being contradicting.

Okay and now, tell me how he contradicts himself, when he asks for the sets coming out in a special order?

 

[Dr Super Good]

Okay and now, tell me how he contradicts himself, when he asks for the sets coming out in a special order?

are asked to print out all the subsets in a set.
in other words it must be in order

Except he has not defined any well-ordering relationship? One minute he is asking to print out all subsets in a set and the next thing he is talking about some kind of order which he has not defined.

From his example I struggle to see any algorithm which will generate the sets in that order.

 

[Rui]

You don't reckon we've drifted a little off-topic here? I was going to report to ask for a move of posts, but then again we don't have a Maths discussion forum.

DSG, it is possible that the OP wasn't being rigorous on his term usage, as in, he did not write what he meant to say.