CareerCup

could u tell us your definition for valid and invalid

assuming number of distinct integers is less than 32 (WLOG)
assign each value a bit position
create a mask for each of the exclusion rule set
generate subsets from original set (different n-bit values)
for mask in masks:
if value & mask == mask
then exclude, continue generation
print value

exponential:-( to generate all subsets

//Assume: The exclusion rules are converted into a vector of numbers where each number's binary representation tells us which numbers are in the exclusion set
e.g: {(a1,a3,a5), (a1,a2)} = {00010101, 00000011)
// Assume: We have n distinct numbers

vector<vector<int>> Subsets(int n, vector<int> E)
     {
          vector<vector<int>> subsets;

          //Generate all subsets 
          for(int i=0;i< 1<<n;i++)
          {
               int violate = 0;
              // Check if it violates an exclusion set
               for(int j=0; j< E.size(); j++)
               {
                    if(i&E[j] != 1)
                    {
                         violate = 1;
                         break;
                    }
               }

               if(!violate)
               {
                  // i represents a valid subset
                   vector<int> sub; 
                   for(int k=0;k<n;k++)
                   {
                     if(i & 1<<k == 1)
                      {
                        sub.push_back(k);
                      }
                   }
                   
                  subsets.push_back(subset)
               }  
          }

        return subsets;
     }

We can imagine the set {a1,a2,a3,..} like a graph where initially all nodes are connected with each other.This means that initially this is a complete graph. Now we check the exclusion set, and for all 2 nodes in the same exclusion set, we remove the edge that connects them.Now, the remaining graph is full with nodes that are connected only and only if they can be in the same graph. Now, in order to find a valid subset, we can run a Depth First search to find all connected components.Every connected component will be a valid subset according to the way we created the graph. Now, for any of this subsets, we must generate the subsets to find all the solutions. Final complexity O(2^N). I think this solution is more interesting than raw backtracking.

I don't think it's possible to have (a1,a2,a3) a valid subset and (a1,a2) an exclusion rule..

How about this sol.

Treat all points as nodes of graph. For each exclusion rule add edges between all elements of the exclusion set. Now run BFS and collect nodes into different components. Suppose number of Components = N. Now run a for loop of i between 1 to 2^N-1. This would give us a Bit Vector to generate different subsets. In the for loop look at the bit pattern of the i, i'th bit signifies that it includes the an element from i'th component. Iterate and print all the different subsets.

bogdan.cebere, your solution is correct. Just that insted of looking for strongly connected components, look out for cliques in the remaining graph. All the cliques will go into one valid set and then we can create subsets out of it. If there is no clique, then all the edges would correspond to valid subsets.

1, Treat the exclusion rules as the elements b1 ={a1, a3},b2= {a2, a4, a10} , find all non-null subsets {b1} {b2} {b1,b2}, O(2^|R|)
2, for each subsets, substitute b1 with every possible specific number, b1 => {a1}, {a2}, |b1| x |b2| ...
3. add {} empty set to the answer, which I think a valid subset.

how about this?

Start with 00000(of length of number of characters), print all permutations of it
Start with 10000, print all permutations.
and so on.
so you start with 2^i+1 and shift it to length of the string and call permutations on that.

For excluding just convert them to bit representation and directly compare them.

I think we cannot get rid of creating subsets for all integers of size N. So we are looking at a size of O(2^n).
The real trick is to help detect the wrong subsets.
1. Assign a prime number to each number in the given subset (a1->2, a2->3, a3->5 etc)
2. Create a product of the exclusion sets. Each product of unique prime numbers is unique.
3. When creating subsets, calculate the product of the items in the subset. If the product is divisible by any of the products of the exclusion sets, then it is invalid.

The extra complexity is of K where K is the number of exclusion sets.

@deveffort: The third step is not correct. It should be
3. When creating subsets, calculate the product of the items in the subset. If the LCD of the product and any of the products of the exclusion sets is not a prime number, then it is invalid.

static void
generate_valid_subset(int *a, int n, int curr_loc, int *form, int form_len, struct list_node **applicable_rules, int *exclusion_refs, struct exclusion_rule *rules)
{
    struct list_node *curr;
    int i, j;

    for (;curr_loc < n; ++curr_loc) {
        if (exclusion_refs[curr_loc] == 0) {
            form[form_len++] = a[curr_loc];
            
            // Output form 0..form_len-1
            for (i = 0; i < form_len; ++i) {
                printf("%d ", form[i]);
            }
            printf("\n");

            curr = applicable_rules[curr_loc];
            while (curr != NULL) {
                i = curr->data;
                curr = curr->next;
                for (j = 0; j < rules[i].n; ++j) {
                    ++exclusion_refs[rules[i].rule_elements[j]];
                }
            }

            /* Recursive call can be done via stack. */
            generate_valid_subset(a, n, curr_loc + 1, form, form_len, applicable_rules, exclusion_refs, rules);

            /* clean-up*/
            form_len--;
            curr = applicable_rules[curr_loc];
            while (curr != NULL) {
                i = curr->data;
                curr = curr->next;
                for (j = 0; j < rules[i].n; ++j) {
                    --exclusion_refs[rules[i].rule_elements[j]];
                }
            }
        }
    }
}

int valid_subsets(int *a, int n, struct exclusion_rule *rules, int rules_count)
{
    struct list_node **applicable_rule;
    struct list_node *prealloc_nodes, *next_free;
    int *exclusion_refs;
    int *form;

    int total_exclusions = 0, i, j, k;

    applicable_rule = (struct list_node **)malloc(sizeof(struct list_node *) * n);
    memset(applicable_rule, 0, sizeof(struct list_node *) * n);

    exclusion_refs = (int *)malloc(sizeof(int) * n);
    memset(exclusion_refs, 0, sizeof(int) * n);

    form = (int *)malloc(sizeof(int) * n);

    for (i = 0; i < rules_count; ++i) {
        total_exclusions += rules[i].n;
    }

    prealloc_nodes = next_free = (struct list_node*)malloc(sizeof(struct list_node) * total_exclusions);
    for (i = 0; i < rules_count; ++i) {
        for (j = 0; j < rules[i].n; ++j) {
            k = rules[i].rule_elements[j];
            next_free->data = i;
            next_free->next = applicable_rule[k];
            applicable_rule[k] = next_free++;
        }
    }

    generate_valid_subset(a, n, 0, form, 0, applicable_rule, exclusion_refs, rules);

    free(applicable_rule);
    free(exclusion_refs);
    free(form);
    free(prealloc_nodes);
}