I am trying to solv a problem and I got it to a part which I can't solv and it is realy complicated because it has to be eficient.
I have M number of objects, they have a variable with N number of flags, which show which of N elements are in it, and another variable which knows how many elements (flags-1 in the other variable) are in it. They also have a member function ok which takes as parameter another of those objects and tells if it is ok (1) or not (0) to combine those 2 objects.
ADDED: If you need you can make a new CombinationOption object for every posible combination and I could make a function to check are all of it's flags up.
So to make it simple, I need to know the least number of objects whose combined flags are all up (1), you can check if you can combine those 2 objects with ok function.
Example:
p1 0101
p2 0110
p3 1000
p4 1010
When p1 and p4 are combined you get 1111, you cannot combine p1 and p2 because they both have the second flag.
Hope you understanded this and that someone knows a solution to this problem.
how is my following attempt? ofcourse it needs to be refined and debugged but may give you a direction.
1 2 3 4 5 6 7 8 9
for (int i=0;i<M;i++) {
for (int j=0;j<M;j++) { // compare all piece-wise combinations of objects
if (i>j) { // to ensure two distinct objects get compared only once
if (numOfFlags(Mi) + numOfFlags(Mj) == N) { // if their flags add up to total number of elements
if (ok(Mi,Mj)) count++; // if its ok to combine them
}
}
}
}
You could use bitmasks, that is defining one (or several) bytes in which each individual bit would be used as a flag.
The benefit of this is that you can then use bitwise operators.
For example the AND operator : given two sequences of bits of the same size, it outputs a sequence of bits of the same size where bits are at 1 only when the corresponding bits in the input sequences are both at 1.
In your case, it would indicate if both lists share a flag.
Checking that 2 lists do not share a flag simply becomes apply the AND operator and checking that there is no bit at 1 in the result (in other words, the result is equal to 0).
1 2 3 4 5
bool ok( int FlagsList1, int FlagsList2 )
{
// in C/C++, "AND(a,b)" can also be written "a&b"
return ( FlagsList1 & FlagsList2 ) == 0;
}
Arghh, yet another thing I already knew.
I am using that already, I use unsigned long long and have an array of those, enough for all elements.
Although I did at first fulishly tryed to do do it the noob way.
You didn't do it the way it is in my code, but I can understand it's logic...
I think if you start with j=i; you will not need to do the first comparision.
But I don't think that will work, because you are incrementing count only if 2 objects combined have all flags, what is correct on the example I gived, but is wery unlikely to actualy happen since the objects can have a big number of posible flags what means many of the objects will have to be combined. Not to mention you didn't showed where you initialized the count variable.
You should explain your problem properly.
¿how do you `combine' k objects?
¿what does the `ok' function do?
¿what is the program supposed to do?
¿what are the limits for `M' and `N'?
sorry zoran, i missunderstood your question.. hmmm scary problem!
seems like theoretically you'll have to check for all the possible 2^{M} combinations.
ne555;
When you combine 2 elements you combine their flags. You are sapoust to have all flags up (1).
Function ok tells if you can (1) or not (0) combine 2 objects. Because you cannot combine objects that bouth have 1 or more of same fags.
The program is for calculating something but I got it to this: You have a lot of objects and you need to know the least number of objects which combined have all of the flags.
N is the number of elements (flags), it is 300>=N>=2; M is the number of objects and it is always bigger than N, because I have 1 object for each of the elements (flags) and every time I add new flag I make a new element, so I would be able to use any of the combinations, but it would be good if someone would make analgorithm wich would if only 1 flag is missing then include it automaticaly, so I would have less objects.
abhishekm71;
Yes, I got that idea too, but the problem is how to check all of the combinations?
If you need you can make a new CombinationOption object for every posible combination and I could make a function to check are all of it's flags up.
You've got N sets. The set k have all the objects which its highest active flag is the k.
By instance the set 1 have the objects that start with 1
the set 2 have the objects that start with 01
the set 3 have the objects that start with 001
Now you traverse the sets, looking for a solution and backtracking if necessary.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
flags are the N sets
K is the set we are working on
result is the combination so far
*/
int magic(flags, K, result) //returns the minimum number of objects to combine
if( K>N ) return 0;
if( result[K] ) //already active
return magic(flags, K+1, result)
better = INF
for( object in flags[K] )
if( valid(object, result) )
better = min(
1+magic(flags, K+1, result+object) //combine
better
)
return better
C++ dose not have for in loop and I don't realy understand this code.
What is INF? What kind of arrays are flags and result? How dose the function valid work?
C++ dose not have for in loop and I don't realy understand this code.
ne555 is giving psuedo code.
I'm having a hard time understanding your description of the problem, but I'd like to make an attempt at it. If this isn't what you want, you're going to need to describe your problem more clearly.
#include <bitset>
#include <vector>
#include <iostream>
usingnamespace std;
constint N = 300; // maximum number of flags
class Object
{ bitset<N> flags;
public:
Object();
bool ok (const Object & obj2);
};
Object::Object ()
{ // Initialize instance somehow
}
bool Object::ok (const Object & obj2)
{ // Compare the two flag arrays
for (int i=0; i<N; i++)
{ if (flags[i] && obj2.flags[i])
returnfalse; // Both 1 - can't combine
// Apply any other rules here
}
returntrue; // All rules applied
}
int main ()
{ vector<Object> objects;
// Load and initialize the objects somehow
if (objects.size() < 2)
{ cout << "Not enough objects to compare" << endl;
exit (1);
}
// Compare each object with every subsequent object
for (int i=0; i<objects.size(); i++)
{ for (int j=i+1; j<objects.size(); j++)
{ if objects[i].ok (objects[j]))
{ // Objects can be combined
}
else
{ // objects can't be combined
}
}
}
}
O, I got it now, flags are my objects (sets of flags).
I'll try to combine this with my code...
There is something wrong.
I don't think it will be nessesery to check is if a falg set is already used "if( result[K] ) //already active", because if it is used then the validation function will return false anyway.
Another thing, "for( object in flags[K] )" if flags are my objects with set of flags, then flags[K] will be just a sinble object and object in flags[K] would be a single fag, shouldn't it be "for( object in flags )"?
And I have a global pointer to my objects (flag sets), so dose that mean I don't have to send flags as parameter?
> if flags are my objects with set of flags, then flags[K] will be just a sinble object
As I said, the set k have all the objects which its highest active flag is the k.
`flags[K]' is a set of objects
> I don't think it will be nessesery to check is if a falg set is already used "if( result[K] ) //already active", > because if it is used then the validation function will return false anyway.
And you will return infinity.