|
Problem:
------------------------------------------------------------------------------------------------------
Let have a sequence of K positive finite integers, starting with 1 and ending with K (each element of this sequence represents a free slot) and an arbitrary multiset of L integers of size 1..K.
Using a greedy algorithm, try to fill slots of this sequence with multiset elements, so that the sequence will be the most similar to entered multiset. Similarity is defined as a minimal sum of
absolute values of subtraction of filled sequence slots and elements, which were put in sequence slots.
Examples:
K=3
Multiset = {1,1,1}
Filled_sequence= 1[1] 2[1] 3[1]
Minimal sum = abs(1-1) + abs(2-1) + abs(3-1)= 3
K=5
Multiset = {1,2,3,4,5}
Filled_sequence= 1[1] 2[2] 3[3] 4[4] 5[5]
Minimal sum = abs(1-1) + abs(2-2) + abs(3-3) + abs(4-4) + abs(5-5) = 0
K=7
Multiset = {2,2,4,4,6,6,6}
Filled_sequence= 1[2] 2[2] 3[4] 4[4] 5[6] 6[6] 7[6]
Minimal sum = abs(1-2) + abs(2-2) + abs(3-4) + abs(4-4) + abs(5-6) + abs(6-6) + abs(7-6) = 4
K=7
Multiset = {1,1,7,7}
Filled_sequence= 1[1] 2[1] 3[-] 4[-] 5[-] 6[7] 7[7]
Minimal sum = abs(1-1) + abs(2-1) + abs(6-7) + abs(7-7) = 2
------------------------------------------------------------------------------------------------------
I could think of some greedy approaches, but cannot really determine if they really work, or even if they really are greedy. Could you write me a way, or at least idea how to implement this?
|
|
|
|
|
In order to analyse this problem more deeply we need to create the following structure.
First for each set of equal elements there is one position that is the best. For 55555 it is 3[5]4[5]5[5]6[5]7[5] and similarity is 6. If the number of elements is even we have two possibilities 7777 is 5[7]6[7]7[7]8[7] or 6[7]7[7]8[7]9[7], similarity = 4.
Now if we place every group of equal elements into their best positions and it turns out that they do not overlap, that is the best solution. But they may overlap.
*******aaaaa
**********bbbbbbb
************ccccccccc
**************ddddddddd
In that case we have to slide and cross them around to avoid overlapping but still to get the best result regarding similarity.
Now each position has its similarity value regarding the distance from the optimal 0 valued position of an element. For example for 5 and 9 we have
1 2 3 4 5 6 7 8 9 position
4 3 2 1 0 1 2 3 4 = S[5]
8 7 6 5 4 3 2 1 0 = S[9]
Once you have these values you can create a table if you like, though the table content is obvious. Now assume that multiset has these elements a1 a2 a3 a4 ... ai, repeated n1 n2 n3 n4... ni times. The table is easy to create:
0102030405060708091011...
... = S[a1]
... = S[a2]
... = S[a3]
...
... = S[ai]
Now you go: select n1 positions for element a1, then another not yet selected n2 positions for a2, then another n3 not yet selected positions for a3... and finally ni for ai.
Calculate the similarity.
Keep controllably changing selected ni positions for element ai, then for a,i-1 a,i-2.... This is simply an extend algorithm for creating combinations. You will have to check
|n over n1|*|(n-n1) over n2|*|(n-n1-n2) over n3|*|(n-n1-n2-n3) over n4|*...|(n-n1-...) over ni|
This is quite a number!
I can create heuristics but for a precise algorithm you would probably need something at least as strong as knapsack problem.
Overlapping check is something I would start with, for sure.
Another related idea is not to select all positions for one element first, but rather to select one position for a1 then one position for a2.., and so on until ai. Then to select the position for the second a1 element (if we have it), the second a2 element... second ai element. If you start this way here then you might start with placing each first element into position with value 0.
This second solution can lead to some clever heuristics.
|
|
|
|
|
One of the easy heuristics to implement is to merge two overlapping sections this way:
1. we find two sections overlapping (generally they may have different elements)
******abcdefgh**********************
**********mnopqrstuvw***************
2. make room for insertion using the most optimal way for each section (they both may slide around or whatever looks easy to implement)
********abc*d*ef**g*h****************
***********m*n**op*q*rstuvw**********
3. merge
********abcmdnefopgqhrstuvw**********
An extended heuristic, which would lead to a greedy method, is to allow in step 2. to change the order of elements in each section.
The idea is coming from almost the same problem in 2- or 3-dimension which looks very interesting
circle 1
****************
********ooo*****
*******ooooo****
********ooo*****
****************
{merge with}
circle 2
****************
******yyyy******
*****yyyyyy*****
****yyyyyyyy****
*****yyyyyy*****
******yyyy******
****************
a possible good merge:
*******************
*****yyyy**********
***yyyyyoyoo*******
**yyyyyoyoyoyoo****
***yyyyyoyoo*******
*****yyyy**********
*******************
|
|
|
|
|
Floating point values don't support bitwise operations:
CS0019: Operator '&' cannot be applied to operands of type 'double' and 'double'
CS0019: Operator '|' cannot be applied to operands of type 'double' and 'double'
CS0019: Operator '^' cannot be applied to operands of type 'double' and 'double'
which makes sense in general. I'm working on an interface that I want to have support the built-in numeric types, inluding foating point, and I want to include bitwise operations.
I could simply have the bitwise methods for floating point types throw a NotImplementedException or some such. But I'd prefer to do the best I can, so at this point I have them cast to Int64 and back; so 5.0 | 2.0 ==> 7.0
Have any of you done anything like this? What did you do? Do you find this to be a reasonable solution?
|
|
|
|
|
Is that really what you get when doing a bitwise or of the float values? IIRC they're stored as 1.01 * 2^(01) and 1.00 * 2^(01); so doing a bitwise or you should get 1.01 * 2^(11) = 10.
(all assuming my brain isn't totally fried this morning)
Today's lesson is brought to you by the word "niggardly". Remember kids, don't attribute to racism what can be explained by Scandinavian language roots.
-- Robert Royall
|
|
|
|
|
IIRC they're stored as 1.01 * 2^(01) and 1.00 * 2^(01); so doing a bitwise or you should get 1.01 * 2^(11) = 10.
It would be more natural to treat floating-point numbers for Boolean operators the same as with arithmetic operators: line up the binary point and then process them bit-wise, keeping the most significant bits of the result. Thus, e.g., 1.5 xor 4.75 would be 5.25 (001.10 xor 100.11 is 101.01). Boolean and/or/xor/andNot operators would work as expected for integers that are within precision limits. Other operators involving inversion would be problematic, however.
The difficulty is that while leading 1's can be represented by negative numbers (thanks to the fact that sum[n=0..inf](2^n)=-1)  trailing 1's cannot be represented in floating-point in any manner that will persist. The floating-point value "not 0" should be "-epsilon", which should have all bits set to the left and right of the binary point. Any value--no matter how larger or small--that is and'ed with "not 0" should yield itself. The value "not 1" should have all bits set except for bit 0, and should be the same as "(not 0) - 1". And'ing any value (no matter the magnitude) with that quantity should leave all bits other than bit 0. Unfortunately, -1-epsilon is going to get rounded to -1, which will have all bits to the left of the binary point (including bit 0) set, and all bits to the right clear.
I think the Boolean operators and/or/xor/andNot could be sensibly applied to floating-point numbers, but I don't see any good way of handling the rest. Note that the normal equality (x and y)=(x andNot (-1-y)) which is applicable to integers would not apply with floats, however (with integers, 'not 0' is -1, but with floats it isn't).
|
|
|
|
|
I have to disagree. Bitwise operators should by definition be data agnostic and only look at the raw bits.
Today's lesson is brought to you by the word "niggardly". Remember kids, don't attribute to racism what can be explained by Scandinavian language roots.
-- Robert Royall
|
|
|
|
|
I have to disagree. Bitwise operators should by definition be data agnostic and only look at the raw bits.
In C, the bitwise operators are not data agnostic. Their particular behavior was chosen to match the behavior of many common architectures, but on architectures which store things differently, the behavior of bitwise operators is required to emulate the common hardware rather than operate on the actual stored bits.
For example, on many machines the 16-bit quantity -5 is represented as 1111111111111011. On some it would have been represented as 1000000000000101. On either type of machine, however, the C standard specifies that (-5 & 12)==8.
I can imagine scenarios where it would be useful to apply Boolean operators to fractional numbers using aligned-binary-point maths; I can't imagine any scenario where applying Boolean operators to the binary representation of floating-point numbers would yield anything of value except in cases aligned-binary-point math would be just as useful (indeed, just about the only scenario I can see having any use would be or'ing a bunch of numbers to see if any are negative or exceed some particular magnitude).
|
|
|
|
|
This response and it's thread point out why bitwise operators are not usually supported.
Yes, I could perform an actual bitwise operation on the underlying bytes, but I don't think the result would be what the user expects, and the resultant pattern of bits may not even be a valid value for its type.
Which is why I would rather have them match their integer counterparts. If someone has 5 and 2 in floating point variables, and is foolish enough to perform Or on them, wouldn't 7 be the expected result? If not, then I'd rather not implement them at all.
|
|
|
|
|
Hii
I used the code to calcalate the intersection if any between 2 lines, but how to do it between lines and arcs , and arcs to arcs ?
The time i did Math is already 20 years ago ....
Johan
|
|
|
|
|
These primitives are all simplexes as such can be represented in parametric form, where by the intersections are solutions to the parametric form equations, Dave Eberly's Geometric tools site has code and documentation explaining the concepts for each pair combination.
Geometric Tools[^]
A side note for regular arc to arc or line or line-segment intersections you can perform the intersections upon the basis circle of the arc (becoming circle-circle, circle-line, circle-line-segment) and then to determine if there is an intersection see if the computerd intersection(s) exists upon the arc itself. The following has some examples:
Wykobi Article[^]
|
|
|
|
|
Hi
Thanks, looks good, i will try to translate the ones i need to c# (cpp is not my stuff)
Johan
|
|
|
|
|
Hello, i am transfering a file from one machine to another in my code. Im using Sockets and TCP Protocol. Is there a way on the reciever's end or sender's that i can calculate the approximate time the file transfer is going to take? any tutorials or ideas will be helpful. Thank you
Regards,
Christian Pace MCAST Student
|
|
|
|
|
Hi,
assuming you know the total amount A of data (file size is easy at the sender, you could inform the target about it), you could measure the time T it has taken so far to transmit/receive an amount X of the data, and then use T*(A/X - 1) as a rough estimate for the remaining time, with some caveats:
- don't do this as long as T is very small and/or X is less than A/10, it would be completely wrong (and cause a divide-by-zero when X is zero)
- it is assuming a linear behavior; if you have reasons to expect something non-linear, you could and should compensate for that (say the file is larger than your filesystem's cache, then the first part might transfer much faster than the remainder, you could compensate for it).
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
Hello m8, I pated the reciever's code below do you think im implementing what you said correctly?
/
/Retrieve Stream from the socket that is connected to the client machine
NetworkStream incomingNetworkStream = new NetworkStream(clientsocket);
FileStream fsout = new FileStream(parser.TemporaryFilesPath + @"\database.zip", FileMode.OpenOrCreate, FileAccess.Write);
long size = Convert.ToInt64(incomigFileSize);
long rdby = 0;
int len = 0;
DateTime starttime = DateTime.Now;
bool isfirst = false;
if (incomingNetworkStream.DataAvailable)
{
while (rdby < size)
{
byte[] buffer = new byte[65535];
len = incomingNetworkStream.Read(buffer, 0, buffer.Length);
fsout.Write(buffer, 0, len);
rdby = rdby + len;
if (downloadpercentage > 10)
{
if (!isfirst)
{
EstimatedTransfertime = DateTime.Now.Subtract(starttime);
isfirst = true;
}
Minutes = EstimatedTransfertime.Minutes * (100 / size - 1);
Seconds = EstimatedTransfertime.Seconds * (100 / size - 1);
}
downloadpercentage = (int)(((double)rdby / (double)size) * 100.00);
}
fsout.Flush();
fsout.Close();
isReading = false;
}
else
{
}
THank you
|
|
|
|
|
Hi,
yeah, that's almost it although I have several comments:
1.
I would update downloadPercentage before the > 10 test, so the test uses the latest information.
That way you don't need isFirst at all.
2.
I explained using percentages for clarity, but you could as well use downloadFraction which would grow from zero to one, all it takes is to replace all the numbers 100 by 1 (and test for > 0.1).
3.
it does not make sense to handle minutes and seconds separately; the way you have it you are multiplying both minutes and seconds by a factor which initially is large (e.g. if you did 20% in 3 minutes 20 seconds, then the factor would be 4 and the estimate 12 minutes and 80 seconds). Choose one unit of time, probably seconds, and get the DateTime.Now.Subtract(starttime).TotalSeconds; after the multiplication you can have TimeSpan convert it back to minutes and seconds.
4.
new byte[65535] looks silly to me; in file I/O the underlying code favors powers of 2 (disk sectors and clusters are powers of 2 for a reason), so try and stick to those, use 65536 or 32768 or something similar (and write it as 0x00010000 or 0x8000 to make that clear). Chances are the stream does not care and will provide arbitrary amounts of data anyway, but when it happens to provide multiples of 512 bytes, the file I/O would benefit.
5.
there is no need to get a new byte[] for each iteration of the while loop, you could create it once
and reuse it.
6.
the sequence flush - close does not make much sense; close always implies flush; an explicit flush really only is useful when you want to make sure some data gets actually written to the file/stream
which you don't want to close yet, but might get lost if the app suddenly would crash.
7.
I am not sure what if (incomingNetworkStream.DataAvailable) is meant to do; I would hope your communication is event driven, or you use a separate thread and a blocking read...
8.
I suggest you use a big try-catch block, after all networking and file I/O sooner or later will fail for whatever peculiar reason a system can come up with.
That's all.
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
I think there's no "magic". Send the total size of the file first, so the receiver knows the size to calculate the remaining time, just like previous poster said.
I just have an extra: if you are transmitting large files through a non-linear network (like the Internet), maybe you should estimate the remaining time based just on the speed of last X bytes transmitted. Let's suppose you have a 100MB file to transmit. You calculate the average speed of the last 1MB received, and use this value to calculate the remaining time (RemainingMB / Speed). So, the remaining time will be adjusted according to the speed variation.
Regards,
Leonardo Muzzi
|
|
|
|
|
someone please help on the thinning algorithm used to identify a character .I am not being able to code the algorithm in c# though i have the whole logic and code written in C . can some1 please help me .
the c code is as follows ....how do i code the same in c# please help
http://pages.cpsc.ucalgary.ca/~parker/thin.c[^]
|
|
|
|
|
After a quick look through the code I think it just translates straight into C#.
The only tricky bit is the b parameter to t1a which must be called using ref.
I suggest you pick up an introductory C# book. If you understand the C you should have no problems translating it to C#.
As a side issue it's generally not a good idea to provide links to code. People will be wary of following them. Why not just copy and paste it - if it's not too long.
Regards
David R
|
|
|
|
|
Hello,
Did not run the C version of the algorithm you've pointed, but there are some already made implementation of thinning in C#, which are made in AForge.NET Framework[^]. One example is to use math morphology filters for this: [^]. Another is simple skeletonization filter[^].
|
|
|
|
|
Hi. I'm currently using AES Rijndael cryptography throught my system. Actually, I was making some tests and found an error. The thing is, when I try to encrypt/decrypt some specific texts, I loose some data in the end of the resulting string. For instance:
15ª Instância
13º lugar ªªAB
The above text, when encrypted/decrypted, results in loosing the two lasts chars "AB". I made some tests and figure out that any 4 characters after the "ªª" are lost. If you put 5 characters ("ABCDE"), then a new data block is created by the algorithm to seize the last letter and nothing is lost.
Aparently it has something to do with the "ª" and "º" characters. If the last block of information (a block has 16 chars, 128 bits, in Rijndael) has any of these special chars, then the last chars of the block are lost in the roundtrip. If there is "ª" or "º" in a block that is not the last one, then everything runs fine.
I'm using the code provided in MSDN site:
http://msdn.microsoft.com/en-us/library/system.security.cryptography.rijndaelmanaged.aspx[^]
and padding the string block myself (using PaddingMode.None in Rijndael object). Does anyone knows why these special chars causes this error?
|
|
|
|
|
Hi,
my guess would be you are mixing up character counts and byte counts somehow. In UTF8 your special characters would take 2 bytes each.
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
Thanks for the advice, that was the problem. In fact, the real problem is that PaddingMode.PKCS7 doesn't work properly. Using this mode, in the roundtrip, I always get the error "PKCS7 padding is invalid and cannot be removed.". That's why I tried to do the padding myself, but it is not possible to do it in the string, because of the special characters that takes more than one byte.
So, the solution was: I implemented the PKCS7 myself, in the byte array, right before the encryption, using PaddingMode.None for the RijndaelManaged. That worked fine. However, in the decryption, it was not necessary to implement it, the PaddingMode.PKCS7 worked correctly.
Thanks to this article, "Notes On Padding" section:
http://www.codeproject.com/KB/security/Cryptor.aspx[^]
|
|
|
|
|
Hello there,
I'm starting up a little personal project that I'm not too sure what the best way to tackle is. I'm hoping someone could give me a few pointers and/or some ideas on questions I should answer before I dig in.
The problem I'm trying to solve to determine file and project dependancies in a big sprawling codebase with tens of thousands of files in it. This codebase has evolved over time and can be quite unwieldy. There are many sub projects inside the build tree and lots of interdependancies between these projects. I want to be able to map these depenencies out.
I found a library that will allow me to moniotr file activity, for example file opens and creates. So my thought is if I run a full clean build and monitor and record all of the file activity of a build I can generate a dependency graph of the entire project. This will also allow me to be able to determine what I should build and in which order when I want to build a tiny piece of the tree. I'm sure there will be other interesting things I can do with this information. I'd also like to try and visualize the entire project and maybe create a file change heat map from it.
My quandry is how best to record the file activity so that I can build a depenecy tree. Ideally I'd like to be able to do this in a multi-threaded way, as our build system can utilize multi-proc machines and have multiple files building at once, and be able to tell which files need to be built before others and which files are grouped in a project and so on.
My current proposed approach is to record all file activity to a logfile and the post process it to generate the depenecy graphs. I'm still a little hazy about all the data that I need to record. I'm currently thinking I'll figure that out as I go when I find I'm missing some important information.
Any pointers or thoughts would be greatly appriciated. 
Thanxx,
Adam
|
|
|
|
|
wouldn't static code analyzation be a better choice by simply parsing all of the includes assuming its a c or c++ program.
or another option to have you project just output the result of the preprocessor in visual studio it will tell you which files it included.
a programmer traped in a thugs body
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
