|
I have a problem of choosing subsets. I wonder if anyone have any idea about it.
We have n sets each having k m-tuple subsets of a known set. I want how to know to find the maximum n-tuple sets each having one and only one member from each of n given sets. These sets also should be non-overlapping. To clarify it I make an example:
n=3, k=4, m=2
set 1: {{1,8}, {2,6}, {5,7}, {2,9}}
set 2: {{3,6}, {1,4}, {2,9}, {5,6}}
set 3: {{2,3}, {1,8}, {7,8}, {3,5}}
Now we are looking for maximum 4 (k) sets that are non-overlapping. Each set have a member from set 1, set 2 and set 3.
a solution can be:{{5,7}, {3,6}, {1,8}} -- {{2,9}, {1,4}, {3,5}} but this solution has 2 sets, can we find solution with 3 or 4 sets (to cover the maximum number of 3*4 members)?
|
|
|
|
|
Assign each subset an integer and make random draws from a uniform distribution to choose subsets randomly deleting them from the set as they are selected.
|
|
|
|
|
Hi All,
can anyone provide me related information or urls for calculation time complexities for algorithms
Thanks
vijay
|
|
|
|
|
Why don't you use Google?
|
|
|
|
|
Thanks for the reply,
i just want to check out , Expert people will suggest me good information.
|
|
|
|
|
What kind of time resolution do you want? If you want sensitive microsecond timing you'll have to look into alternatives for the Unix gettimeofday() function on Windows. Or perhaps there are other high-resolution timer classes available...depends what you want, exactly.
|
|
|
|
|
Anyone know how to *extract* the shear X and shear Y values from a 2D (3x3) affine transform matrix? I've got code extracts the rotation, translation, and scale values, but not shear. So far google isn't turning up much, other than tons of stuff on how to apply a shear to the matrix (I already have that in place).
¡El diablo está en mis pantalones! ¡Mire, mire!
Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)!
SELECT * FROM User WHERE Clue > 0
0 rows returned
Save an Orange - Use the VCF!
VCF Blog
|
|
|
|
|
Well, the ShearX and ShearY values would be here:
1, Y, 0,
X, 1, 0,
0, 0, 1
If you already know how to apply shear to a matrix, whats so hard about getting the values? Am i completely missing something?
Infact, how are you getting the other values? If i were to scale along the x-axis by 2, and the y-axis by 3. Then translate by (5,3) i would end up with this matrix:
2, 0, 0
0, 3, 0
10,9, 1
But if i translate then scale we just get:
2, 0, 0
0, 3, 0
5, 3, 1
So how can you know what order transformations where done in, without knowing what transformations where applied and vice versa?
My current favourite word is: I'm starting to run out of fav. words!
-SK Genius
Game Programming articles start - here[ ^]-
|
|
|
|
|
SK Genius wrote: Infact, how are you getting the other values?
Good question!
Here's the code for extracting the values. Note I got this from another lib, so I'm not 100% clear on all the math - I *think* I understand the idea behind it though.
double matrix_[3][3];
double Matrix2D::getRotation() const
{
double x1 = 0.0;
double y1 = 0.0;
double x2 = 1.0;
double y2 = 0.0;
apply(x1, y1);
apply(x2, y2);
return atan2(y2-y1, x2-x1);
}
void Matrix2D::getScale( double& x, double& y ) const
{
double x1 = 0.0;
double y1 = 0.0;
double x2 = 1.0;
double y2 = 1.0;
Matrix2D rot;
rot.rotate( -getRotation() );
rot.multiply( *this );
rot.apply(x1, y1);
rot.apply(x2, y2);
x = x2 - x1;
y = y2 - y1;
}
note that apply() simply transforms the (x,y) values by whatever is in the matrix_ array.
¡El diablo está en mis pantalones! ¡Mire, mire!
Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)!
SELECT * FROM User WHERE Clue > 0
0 rows returned
Save an Orange - Use the VCF!
VCF Blog
|
|
|
|
|
I see, so you can get the rotation without worrying about scale or translate etc, because the rotation is completely separate. To get the scale you have to undo the rotation, so you can pretty much just get the values of X and Y here:
X, 0, 0
0, Y, 0
0, 0, 1
Shear and translate are in different parts of the matrix.
The problem is, both shear and translate are affected by Scale, so you'd have to know if the matrix was scaled before or after a shear or translate was applied (if at all).
Rotation isn't affected by scale because the angle remains the same, and the points just get further from the origin. So, the best you can do is to undo the rotation like you have in getScale() and just get the values from the matrix, even thought they may have been scaled.
So, using the apply method (rather than just using the array, i don't know if you have direct access to it):
void Matrix2D::getShear( double& x, double& y ) const
{
double x1 = 1.0;
double y1 = 1.0;
Matrix2D rot;
rot.rotate( -getRotation() );
rot.multiply( *this );
rot.apply(x1, y1);
x = x1-1;
y = y1-1;
}
I think...
My current favourite word is: I'm starting to run out of fav. words!
-SK Genius
Game Programming articles start - here[ ^]-
|
|
|
|
|
Jim,
SK is right, you should just be able to get these from inspection. Perhaps I don't understand what you want to extract. Do you want the shear equations?
|
|
|
|
|
|
Hi Guys. I posted this in the C# forum but I can't seem to get any help with finding something that can return a 16 digit number. I have a list of numbers that I need to sum up but the problem is that it totals to a 16 digit number or more. Problem is that currently I can't find anything that can do this in C# unless somebody here knows of anything else I can use.
Does anybody have any ideas??
Thanks in advance
Excellence is doing ordinary things extraordinarily well.
|
|
|
|
|
If what you're totaling is overflowing a 16-bit number then you cannot return a 16 bit number without losing precision. You'd have to return at least a 32 bit number with the result of the summation.
For example:
short[] numbers = new short[] { short.MaxValue, short.MaxValue, short.MaxValue, short.MaxValue };
short total = 0;
foreach (short number in numbers)
total += number;
Console.WriteLine(total);
Returns -4 as the result, obviously not what you want, this is because you've overflowed and the number has rolled back to zero. If you change total to an int then you get the correct result.
I doubt it. If it isn't intuitive then we need to fix it. - Chris Maunder
|
|
|
|
|
Well, a 16-digit number is a 16-bit one only in base 2.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
I doubt it. If it isn't intuitive then we need to fix it. - Chris Maunder
|
|
|
|
|
You could just make your own class that deals with the numbers in binary?
|
|
|
|
|
I'm not a C# user, but a few moments with google threw up:
Int64[^]
and
Big Integer Class[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
UInt64 tops out at 2^64, which is around 20 digits in base 10.
Theres an article on the MSDN on "integral types in .Net" (from the top of my head) which gives all the details. Decimal is quite a bit bigger, similar to the SQL currency type. Decimal is usually large enough for most purposes.
- Anyone with enough things that you need bigger than decimal to count them can afford to have a bigint library written for them 
|
|
|
|
|
|
If you can't find the equivalent of int__64 (ULONGLONG for me) in C# you can break your sum into a set of essentially 'multi-digit' digits.
That is: an accumulator for 0-999, another for 1,000-999,000, another for 1,000,000-999,000,000, etc. Now, every time your 0-999 accumulator goes greater than 1000, subtract the 1,000's off that accum and add 1 to the 1,000-999,000 accum.
Do you see it?
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
Hi everyone,
I have a small question, for my school project i need to make a program for counting brick in image.
So I have a picture with nothing but bricks on it, and i need to count them,
the idea i have is to use Sobel algorithm, blur, binaryzation and region search, something like that.
Is is the right way to go, or is there any better one?
Thank you all for your help!
|
|
|
|
|
I would say you have it spot on... filter the image and then apply a region counting algorithm.
The filtering is relatively simple... but the region finding could be harder (I've never used/made one).
If you get the original image down to just the outlines of the bricks (via the filters), then you could use a Monte-Carlo based search to look for borders surrounding each point.
[I wish I had a school project as interesting as yours!]
Matthew Butler
|
|
|
|
|
Hmm ya all i need is some guidance where i can get this algorithms implemented in C#.
Thnx for your reply.
|
|
|
|
|
Member 3897207 wrote: all i need is some guidance where i can get this algorithms implemented in C#.
First, you ask for some advice on if your approach to the problem, which is fine. But now you respond to Mathew's advice saying you just want help on how to cheat to do your homework. I was going add a litte to his advice but now I won't and you'll probably not get any further help.
2 75 22 6
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
