How to Find Subset of an array

general
, ,
1

How to Find Subset of an array
Can anyone help me with find subset of array

1 Like
2

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)
3

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!

1 Like
4

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);

}

4 Likes
5

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.

2 Likes
6

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

7

@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.

8

can any one help

9

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