How to Find Subset of an array
Can anyone help me with find subset of array
in python you can simply use itertools for this…
import itertools
a = [1,2,3,1]
for j in range(1,len(a)+1):
for i in itertools.combinations([1,2,3,1],j):
print i
Or else you can also write recursive function for same… like this…
a = [1,2,3,1]
l = len(a)
current = []
def find(index):
global current
if index == l:
return
else:
find(index+1)
current.append(a[index])
print current
find(index+1)
current.pop()
print find(0)
Hey @drjaat,
There are quite a few ways to generate subsets of an array,
- Using binary representation, in simple terms if there are 3 elements in an array,
A = [1,2,3]
subsets of array will be {[],1,[2],[3],[1,2],[2,3],[1,3],[1,2,3]}
How to generate?
- n elements in an array than it’s for sure that there would be 2^n subsets of that array.
- for three elements, find all the possible binary representation of n bits in size
- let’s suppose for three elements 000, 001, 010, 011, 100, 101, 110, 111
- wherever there is 1 select those elements for set, 000 no elements are chosen, for 001 only 3 is chosen and so on. {[],[3],[2],[2,3],1,[1,3],[1,2],[1,2,3]}
Implementation part would be now easy, you can read go through this link for better explanation.
Hope this helps!
You can use the below snippet to find all subsets of a given array of size n.
int n,a[n];
void foo(int count,vector < int > vec)
{
if(count==n)
{
print(vec);return;
}
foo(count+1,vec);
vec.push_back(vec[count]);
foo(count+1,vec);
}
Here is a link where you can find the code for finding all possible subsets of a given set http://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/
The above code is in Java if you want a c++ code you can find it here http://www.geeksforgeeks.org/power-set/
I Hope it helps.
import java.io.IOException;
class Main
{
static void printSubsets(char set[])
{
int n = set.length;
// Run a loop for printing all 2^n
// subsets one by obe
for (int i = 0; i < Math.pow(2,n); i++)
{
for (int j = 0; j <Math.pow(2,n); j++){
if((i & (1<<j)) > 0 ){
//System.out.print("("+i+" "+j+")"+" ");
System.out.print(set[j]+" ");
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
char set[] = {'a', 'b', 'c'};
printSubsets(set);
}
}
i dont want to print non continous for example a is 1 and c is 3 so i dont want to print it
i only want to print continous set eg a,b,ab,abc,c,bc
@drjaat and others…Can this logic be used for finding subset of an array with n elements?
If so. How?
(because for 5 elements we need to generate 00000,00001,00010,00011…11111. )
I would like to print both contiguous & non-contigious.
One can start with 00000.Use shift operator. But I cannot apply this operator correctly to get the exact sequence of
00000,00001…11111.
import java.util.ArrayList;
public class place2 {
public static void main(String[] args) {
int a[]= {1,2,3,4};
ArrayList ans=new ArrayList();
for(int k=1;k<=a.length;k++){
for(int i=0;i<=a.length-k;i++){
String s="";
for(int j=i;j<i+k;j++)
s+=a[j];
if(s!="")
ans.add(Integer.parseInt(s));
}
}
System.out.println(ans);
}
}
This code works for my requirement
thanks to all
can any one help