patternjavaMinor
Print all possible subsets of an array
Viewed 0 times
allarraysubsetspossibleprint
Problem
I solved the problem to print all possible subsets of an array. I just want to know a better approach or anything different I could have done.
Question: Print all possible subsets of an array.
My approach: I know that there are \$2^N\$ (no. of elements in the set) subsets and each subset can be represented with the help of \$N\$-bit binary number. As a part of an assignment I have already made a decimal to binary and to reverse(prints no. in reverse digit by digit) a number program.So I combined the two to solve this question.
Input:
Output:
My Code:
Question: Print all possible subsets of an array.
My approach: I know that there are \$2^N\$ (no. of elements in the set) subsets and each subset can be represented with the help of \$N\$-bit binary number. As a part of an assignment I have already made a decimal to binary and to reverse(prints no. in reverse digit by digit) a number program.So I combined the two to solve this question.
Input:
{1, 2, 3}Output:
3, 2, 32, 1, 31, 21, 321My Code:
private static void subset(int[] arr) {
int size = arr.length;
int binaryLimit = (int) Math.pow(2, size) - 1;
for (int i = 0; i = arr.length - counter; j--) {
// if binary no is greater then one digit, compare each digit separately.
if (counter > 1) {
int k = binary;
while (k != 0) {
int rem = k % 10;
if (rem == 1) { //if binary digit == 1, print corresponding no. from array
System.out.print(arr[j]);
}
j--;
k = k / 10;
}
System.out.println();
} else {
if (binary == 1) {
System.out.println(arr[j]);
j--;
}
}
}
}
}Solution
Simplify
This could be written a lot simpler.
For each number until
you could iterate over the bits using bit shifting,
and moving the current index in the array,
printing values when the bit is set.
Calculating powers of 2
Note that
Naming
Usability
As there is no punctuation between elements as they are printed,
this method will not be very useful for larger arrays,
or arrays where values have more than one digit.
Java conventions
Capitalized variable names are normally used for constants,
never for local variables.
Method decomposition
Your implementation is very long,
and could have been split to smaller pieces that are easier to read and test individually.
This could be written a lot simpler.
For each number until
binaryLimit,you could iterate over the bits using bit shifting,
and moving the current index in the array,
printing values when the bit is set.
private static void printAllSubsets(int... arr) {
int size = arr.length;
int binaryLimit = (1 0) {
if ((num & 1) == 1) {
System.out.print(arr[index]);
}
index--;
num >>= 1;
}
System.out.println();
}
}Calculating powers of 2
Note that
Math.pow takes and returns double. Converting between types is ugly, and what's worse, floating point math is fraught with problems in general. Fortunately, for calculating powers of 2, a clean and blazingly fast alternative is to use bit shifting, as demonstrated in the code above.Naming
subset is a poor name for a void method that prints subsets of elements of an array.Usability
As there is no punctuation between elements as they are printed,
this method will not be very useful for larger arrays,
or arrays where values have more than one digit.
Java conventions
Capitalized variable names are normally used for constants,
never for local variables.
Method decomposition
Your implementation is very long,
and could have been split to smaller pieces that are easier to read and test individually.
Code Snippets
private static void printAllSubsets(int... arr) {
int size = arr.length;
int binaryLimit = (1 << size) - 1;
for (int i = 1; i <= binaryLimit; i++) {
int index = size - 1;
int num = i;
while (num > 0) {
if ((num & 1) == 1) {
System.out.print(arr[index]);
}
index--;
num >>= 1;
}
System.out.println();
}
}Context
StackExchange Code Review Q#153514, answer score: 6
Revisions (0)
No revisions yet.