C
chetan.falcon
PLEASE SOS
I need something that needs to be done by this 12th or 13th May . I
want a C/c++ program for this problem. There are some sets of numbers
given in the text files I have attached. I need to divide these sets
into subsets (each set into max of 2 subsets).i.e. there can be max of
2 subsets for a given set.(either two subsets containing numbers or
the set itself and a null subset)that is options can be
Say for example in snort_13_dfa-nfa file,
1 indicates the index or serial number of number of sets in the file.
You can ignore this.
Now consider the first set [0 1]. This can be split into the subsets
[0] and [1]
Or
[01] and [null].Here you see that there are two options for splitting
the same set [0 1]. Now consider the serial number 169.
Here you see the set contains [0 1 169].
If we split this into two subsets [01]and [169],
[01] can be used from the first sets answer.
Since we can use the second option in set1 here (like [01] and
[null]), there is re usability. So the main idea is to split the sets
into subsets in such a way that the subsets can be used again and
again. I want the number of subsets to be as small as possible.
CLEARER PICTURE:I wanted the following in the code. Input is the file
that I have attached..I wanted the program to output the total number
of subsets and the values of the subsets.
Say for example (a general one=>not the one in the file)Say You have
sets {1} =>{1}and{null}{1,2} =>{1,2}and{null}
{1,2,3 } =>{1,2,3}and{null}{1,2,3,4} =>{1,2,3,4}and{null}
{1,2,1} =>{1}and{1,2}
Then the subsets can be {1}{1,2}{1,2,3}{1,2,3,4}The number of subsets
is the output along with the values.
Though this is not the only solution, there can be other solutions as
well. The main thing is that while splitting the sets into subsets,
you need to split the sets in such a way that you can use the previous
subsets for the current set. In the above example, we can use the
result of set 1 and result of set 2 in set 5.Therefore the number of
entries are reduced. This is the main concept. You need to reduce the
number of entries by making use of the common ones.
INPUT: Text file
OUTPUT:The number of subsets used in the text file.
The values of the each subsets used.
APPROACH that I thought of :
If you have the a set of n elements, a valid mask would be an array of
n boolean (true/false; 1/0) elements. When you apply a mask to a set,
you check each element (e) in the set and the corresponding one in the
mask (m): if m is true(1), you add e to the result, otherwise, you
ignore it. After applying the mask (0, 1, 0, 0, 1) to {1, 2, 3, 4, 5},
you get {2, 5}.
So, to generate all the subsets of a set of n elements, you first have
to generate all the possible 2n masks of the set and then apply them.
Basically, you just have to implement a binary counter, i.e. something
that generates:
000
001
010
011
100
101
110
111
Here is the code in C :
----------------------------------------------------------------------------------------------------------
#include <stdio.h>
/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
int i;
printf("{ ");
for (i = 0; i < n; ++i)
if (mask)
printf("%d ", i + 1); /*i+1 is part of the subset*/
printf("\\b }\\n");
}
/* Generates the next mask*/
int next(int mask[], int n) {
int i;
for (i = 0; (i < n) && mask; ++i)
mask = 0;
if (i < n) {
mask = 1;
return 1;
}
return 0;
}
int main(int argc, char *argv[]) {
int n = 3;
int mask[16]; /* Guess what this is */
int i;
for (i = 0; i < n; ++i)
mask = 0;
/* Print the first set */
printv(mask, n);
/* Print all the others */
while (next(mask, n))
printv(mask, n);
return 0;
}
I need something that needs to be done by this 12th or 13th May . I
want a C/c++ program for this problem. There are some sets of numbers
given in the text files I have attached. I need to divide these sets
into subsets (each set into max of 2 subsets).i.e. there can be max of
2 subsets for a given set.(either two subsets containing numbers or
the set itself and a null subset)that is options can be
Say for example in snort_13_dfa-nfa file,
1 indicates the index or serial number of number of sets in the file.
You can ignore this.
Now consider the first set [0 1]. This can be split into the subsets
[0] and [1]
Or
[01] and [null].Here you see that there are two options for splitting
the same set [0 1]. Now consider the serial number 169.
Here you see the set contains [0 1 169].
If we split this into two subsets [01]and [169],
[01] can be used from the first sets answer.
Since we can use the second option in set1 here (like [01] and
[null]), there is re usability. So the main idea is to split the sets
into subsets in such a way that the subsets can be used again and
again. I want the number of subsets to be as small as possible.
CLEARER PICTURE:I wanted the following in the code. Input is the file
that I have attached..I wanted the program to output the total number
of subsets and the values of the subsets.
Say for example (a general one=>not the one in the file)Say You have
sets {1} =>{1}and{null}{1,2} =>{1,2}and{null}
{1,2,3 } =>{1,2,3}and{null}{1,2,3,4} =>{1,2,3,4}and{null}
{1,2,1} =>{1}and{1,2}
Then the subsets can be {1}{1,2}{1,2,3}{1,2,3,4}The number of subsets
is the output along with the values.
Though this is not the only solution, there can be other solutions as
well. The main thing is that while splitting the sets into subsets,
you need to split the sets in such a way that you can use the previous
subsets for the current set. In the above example, we can use the
result of set 1 and result of set 2 in set 5.Therefore the number of
entries are reduced. This is the main concept. You need to reduce the
number of entries by making use of the common ones.
INPUT: Text file
OUTPUT:The number of subsets used in the text file.
The values of the each subsets used.
APPROACH that I thought of :
If you have the a set of n elements, a valid mask would be an array of
n boolean (true/false; 1/0) elements. When you apply a mask to a set,
you check each element (e) in the set and the corresponding one in the
mask (m): if m is true(1), you add e to the result, otherwise, you
ignore it. After applying the mask (0, 1, 0, 0, 1) to {1, 2, 3, 4, 5},
you get {2, 5}.
So, to generate all the subsets of a set of n elements, you first have
to generate all the possible 2n masks of the set and then apply them.
Basically, you just have to implement a binary counter, i.e. something
that generates:
000
001
010
011
100
101
110
111
Here is the code in C :
----------------------------------------------------------------------------------------------------------
#include <stdio.h>
/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
int i;
printf("{ ");
for (i = 0; i < n; ++i)
if (mask)
printf("%d ", i + 1); /*i+1 is part of the subset*/
printf("\\b }\\n");
}
/* Generates the next mask*/
int next(int mask[], int n) {
int i;
for (i = 0; (i < n) && mask; ++i)
mask = 0;
if (i < n) {
mask = 1;
return 1;
}
return 0;
}
int main(int argc, char *argv[]) {
int n = 3;
int mask[16]; /* Guess what this is */
int i;
for (i = 0; i < n; ++i)
mask = 0;
/* Print the first set */
printv(mask, n);
/* Print all the others */
while (next(mask, n))
printv(mask, n);
return 0;
}