0

Consider one set of numbers S which contains the N numbers , I want 2 subsets(S1, S2) of S such that S1 U S2 = S. S1 intersection S2 = null . I want all possible combinations of S1 ans S2. I got that if my Set contains N numbers i will get 2^N combinations of subsets. I have tried following code.

DemoPartition Class

public class DemoPartition {

    ArrayList nodes = new ArrayList();
    ArrayList<Partitioning> partition = new ArrayList<>();

    public static void main(String[] args) {
        DemoPartition dp = new DemoPartition();
        try {
            int nums=3;

            dp.DividePartition(dp.nodes,nums);
            System.out.println(dp.partition);
            System.out.println(dp.partition.size());

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void DividePartition(ArrayList nodes,int nums) {
         for (int i = 1; i <= nums; i++) {
                nodes.add(i);
            }
        for (int i = 0; i < nodes.size(); i++) {
            Partitioning parts = new Partitioning(new ArrayList(), new ArrayList());
            parts.getMobile().add(nodes.get(i));
            partition.add(parts);
        }

        ArrayList<Partitioning> temparray = new ArrayList<>();
        for (Partitioning parts : partition) {
            for (Object obj : nodes) {
                if (!parts.getMobile().contains(obj)) {
                    parts.getCloud().add(obj);
                }
            }
            if (nodes.size() != 2) {
                Partitioning newone = new Partitioning(parts.getCloud(), parts.getMobile());
                temparray.add(newone);
            }
        }
        partition.addAll(temparray);

        Partitioning parts = new Partitioning(new ArrayList(), new ArrayList());
        for (int i = 0; i < nodes.size(); i++) {
            parts.getMobile().add(nodes.get(i));
        }
        partition.add(parts);
        Partitioning newone = new Partitioning(partition.get(partition.size() - 1).getCloud(), partition.get(partition.size() - 1).getMobile());
        partition.add(newone);
    }

}

Partitioning Class

public class Partitioning {

    private ArrayList mobile;
    private ArrayList cloud;

    public Partitioning(ArrayList mobile, ArrayList cloud) {
        this.mobile = mobile;
        this.cloud = cloud;
    }

    public ArrayList getCloud() {
        return cloud;
    }

    public void setCloud(ArrayList cloud) {
        this.cloud = cloud;
    }

    public ArrayList getMobile() {
        return mobile;
    }

    public void setMobile(ArrayList mobile) {
        this.mobile = mobile;
    }

    @Override
    public String toString() {
        return "S1=" + mobile + " S2=" + cloud + "\n";
    }



}

output when nums = 3 

[S1=[1] S2=[2, 3]
, S1=[2] S2=[1, 3]
, S1=[3] S2=[1, 2]
, S1=[2, 3] S2=[1]
, S1=[1, 3] S2=[2]
, S1=[1, 2] S2=[3]
, S1=[1, 2, 3] S2=[]
, S1=[] S2=[1, 2, 3]
]
8

which works when nums is 2 and 3 and not works when nums >3. I know my code is not complete , I am not getting the generic logic how to solve this problem, Please help me out.

swapnil7
  • 808
  • 1
  • 9
  • 22
  • Note that you need to obtain powerset, and for each s in Powerset, s1=s, s2=set\s1 – amit Apr 29 '15 at 10:01
  • My question is different , go through it . I Two conditions that , partitioning must have 2 subset S1 and S2 . and S1 intersection S2 must be null – swapnil7 Apr 29 '15 at 10:02
  • I did, everything that you need to do in order to get your partitions to s1,s2 is identical to getting the powerset, by setting s1=s,s2=originalSet\s for every s in the power set. – amit Apr 29 '15 at 10:04
  • your above suggestion does not satisfy condition S1 intersect S2 = null – swapnil7 Apr 29 '15 at 10:16
  • 1
    yes, it does, by definition of `\` operator, an element cannot be in both `s1` and `s2`. `X \ Y` means - `X` without everything that is in `Y`. `originalSet \ s` ensures s1[inersetction]s2 = {}, and s1 U s2 = originalSet. – amit Apr 29 '15 at 10:18

0 Answers0