Algorithm for a problem

[zoran404]

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.

[Smac89]

Check each object, if object1 has same number (N) of elements in position i as object2, then they can't be combined

[zoran404]

Look, I have tryed hard to solv this problem and this reply isn't telling me anything.
And what dose "Check each object" mean anyway?

Can someone try to make an algorithm for solving this problem?
Or at least give me an idea how to solv this.

[abhishekm71]

how is my following attempt? ofcourse it needs to be refined and debugged but may give you a direction.

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
         }
      }
   }
}

[toum]

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).

bool ok( int FlagsList1, int FlagsList2 )
{
    // in C/C++, "AND(a,b)" can also be written "a&b"
    return ( FlagsList1 & FlagsList2 ) == 0;
}

This is also very computationally efficient.

[Script Coder]

This should work:

#include <string>
#include <iostream>
using namespace std;

inline bool sXor(string s1, string s2) {
	for(int i=0; i<s1.size(); ++i)
		if(s1[i]==s2[i]) return(false);
	return(true);
}

int main() {		//This program assumes that input will always be in the correct format
	string *vs;
	int M;
	cin>>M;
	vs=new string[M];
	for(int i=0; i<M; ++i) cin>>vs[i];
	
	for(int i=0; i<M; ++i)
		for(int j=i+1; j<M; ++j)
			if(sXor(vs[i], vs[j]))
				cout<<i<<' '<<j<<'\n';
	return(0);
}

[zoran404]

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.

Here is the ok function

bool ok(unsigned long long tt[])
    {
        for(bb=0; bb!=size; bb++)
            if(tt[bb] & t[bb]) return 0;
        return 1;
    }

[zoran404]

O and there is a reply before yours...

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.

[ne555]

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'?

[abhishekm71]

sorry zoran, i missunderstood your question.. hmmm scary problem!
seems like theoretically you'll have to check for all the possible 2^M combinations.

[zoran404]

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.

[ne555]

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.

/*
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

Sorry, I cannot figure out the order

[zoran404]

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?

[AbstractionAnon]

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>

using namespace std;

const int 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])
            return false;	// Both 1 - can't combine
        //  Apply any other rules here
    }
    return true;	//  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
             }
         }
    }
}

[ne555]

> What is INF?
infinite. It means that it is not possible to have all the flags up.

> What kind of arrays are flags and result?
`flags' is described in the first paragraph
`result' is just the combined object (the or of the selected)

> How dose the function valid work?
As you describe it

you cannot combine objects that bouth have 1 or more of same fags.

[zoran404]

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?

[ne555]

> 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.

[Script Coder]

does my code not work?

[ne555]

Of course not, you are not solving the problem.

[Script Coder]

After having read descriptions of the problem, i still do not understand what it is, would someone kindly explain is simply?