0

The assignment is as follows:

Write a program that would generate and print all r-subsets of a set S. The set S and the number r are provided by the user. Your program should also print the number of r-subsets of S. Subsets of a set can be generated using a mask. A good description of the method is presented at http://compprog.wordpress.com/2007/10/10/generating-subsets/. The page also contains a link to the code in C (sub.c) Please use a mask to generate all subsets of S and print the subsets that have r elements (r-subsets). Your program should do the following:

  1. Prompt the user to enter the size of set S, elements of S, and the number r. You may assume that the size of S is no more than 10. Assume that all the elements entered by the user are different (no duplicates). (You do not need to check that there are no duplicates.)
  2. Generate all subsets of S using a mask.
  3. For each subset generated in 2), compute the number of elements in the subset. If the number of elements in the subset is equal to r then output the subset.
  4. Output total number of r-subsets of S. Dialog with the user may look like the following (keep in mind that the order of elements in a set does not matter):
Please enter S: 1 2 3 4 5 6
Please enter r: 4
4-subsets of S are the following:
{ 1 2 3 4 }
{ 1 2 3 5 }
{ 1 2 4 5 }
{ 1 3 4 5 }
{ 2 3 4 5 }
{ 1 2 3 6 }
{ 1 2 4 6 }
{ 1 3 4 6 }
{ 2 3 4 6 }
{ 1 2 5 6 }
{ 1 3 5 6 }
{ 2 3 5 6 }
{ 1 4 5 6 }
{ 2 4 5 6 }
{ 3 4 5 6 }
There are 15 r-subsets

The instructor never talked about "masks" in class, so naturally I was confused about this. I tried to Google to figure it out, but to no avail. So, I decided to just try solving the problem in general. This is my code so far:

import java.util.*;
import java.util.Scanner;


public class Main {

  public static void func(int[] ARR, int s, int R) {
           for (int j = i + 1; j <= R; j++) {
               System.out.println(ARR[i] + " " + ARR[j]);
           }
  }
  
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Size of set S: ");
    int S = input.nextInt();
    int[] arr = new int[S];    
    System.out.print("Values of set S: ");
    for (int i = 0; i < S; i++) {
      arr[i] = input.nextInt();
    }
    System.out.print("Value of r: ");
    int r = input.nextInt();
    func(arr, S, r);
  }
}

How do I go about making this code work/creating this "mask" thing that the instructor is asking us to implement?

Zaynab B.
  • 9
  • 2
  • 1
    https://www.geeksforgeeks.org/find-distinct-subsets-given-set/. https://www.youtube.com/watch?v=wpWGDHmpbgA. I found those links in a fraction of the the time it'd have taken to formulate this question. HTH. – Abhijit Sarkar Apr 20 '23 at 22:03
  • Per the link you cited, a "mask" is simply a string of boolean true/false values indicating whether or not that particular set is present. It's a [bitmask](https://en.wikipedia.org/wiki/Mask_(computing)). You can set, clear and check mask values using the Java [boolean operators](https://www.freejavaguide.com/boolean_operators.htm). – paulsm4 Apr 20 '23 at 22:22
  • @AbhijitSarkar The problem is author of the link doesn't understand what a mask is, so little surprise that you don't. What's described there is *not* a mask, but rather an *array* of boolean values that is used to keep track of which values are in a set: You first sort the elements in a list. Then each location in the sorted list corresponds to the same location in the boolean array, which indicates if the element has been used. When generating the subsets, you update the array when you add an element, but first you check if it's already true and if so abort that branch early. – Bohemian Apr 20 '23 at 22:24
  • What pointless microoptimization! Trying to squezze subsets into a single machine word to save a couple bytes of storage, but using a dreadfully inefficient algorithm, which, by generating all subsets, requires O(2^n) operations to emit (n choose r) < O(n^r) subsets. If you wish to optimize, perhaps start by not iterating over subsets you could not possibly need? A decently efficient algorithm can be found on my answer to https://stackoverflow.com/questions/4504974/how-to-iteratively-generate-k-elements-subsets-from-a-set-of-size-n-in-java – meriton Apr 20 '23 at 23:57
  • Just as an example how bad your instructor's approach is: If |S| = 30 and r = 5, their code iterates 1073741824 subsets to emit 142506. – meriton Apr 21 '23 at 00:05

1 Answers1

0

The idea about the mask is to associate each set a number whose each bit indicates if the corresponding order is in the set.

Then the set {} is coded 0. The set {0} is coded 1, the set {1} is coded 2, set set {0,1} is coded 1+2=3.

With this scheme you add easily a number to a set:

s = s | 1<<number;

You can also test the membership of a number in a set:

if (s & 1<<number != 0)
   System.out.println("number is in set");

The << notation indicates a number (here 1) whose the bits are shift in a given amount.

Using a mask for sets is very efficient: the |, & and << operators are built in the processor. But it is limited by the number of bits in the CPU registers.

In your example, you can type something like this:

for(int set=0; set< (1<<S); s++)
{
   // count the number of items
   int n=0;
   for(int i=0;i<S;i++)
      if(set & 1<<i != 0)
         n++;
   // if the number of item match r
   // print the set
   if(n==r)
   {
      for(int i=0;i<S;i++)
         if(set & 1<<i != 0)
            System.out.print(arr[i]);
      System.out.println();
    }
}

Note, here 1 << n code the set arr[n] and not n. Then S must be inferior to the size of your cpu registers, but arr are not so much limited.

Frédéric LOYER
  • 1,064
  • 5
  • 10