|
I was going to suggest using pointers until I saw your last paragraph. It seems to me this is a language-specific question with regard to C# rather than an algorithm question, per se. Thus, you could try the C# forum[^]. (I have zero experience with C#.)
|
|
|
|
|
If you could store both arrays in the same dictionary it would solve your problem. So for each index, the dictionary item would be a PAIR of ints (one from each array).
Then you go through each element, and get the difference between the pair of values at that index. This structure would also use less memory than two dictionaries.
Using a struct for the pair of ints would avoid the implicit use of a pointer that would result from a class/reference.
|
|
|
|
|
SortedDictionary might help here. Theres also SortedList which is very similar. Check the API notes. SortedDictionary IIRC is quicker but uses more memory. Main speedup is in adhoc query by key, which isn't what you are doing if you iterate the keys collection.
Probably SortedList will help you out. The actual algorithm could be as you said, quite simple.
|
|
|
|
|
Mark Churchill wrote: Main speedup is in adhoc query by key, which isn't what you are doing if you iterate the keys collection.
There are two approaches I can see. If what you want is to produce a new dictionary containing the differences, then your best bet is probably something like:
if dict1reader.eof then
output dict2reader
advance dict2reader
else if dict2reader.eof then
output dict1reader
advance dict1reader
elseif dict1reader.key = dict2reader.key then
output(dict1reader.key, dict1reader.value-dict2reader.value)
advance dict1reader
advance dict2reader
elseif dict1reader.key < dict2reader.key then
output(dict1reader.index, dict1reader.value)
advance dict1reader
else
output(dict2reader.index, dict2reader.value)
advance dict2reader
endif
Iterate that until both readers report eof.
|
|
|
|
|
I have a slight maths problem - Maybe you guys can help me out 
I have 94 unique placeholders, with a possible digit on the end.
I have 16581375 total possibilities.
I'm wondering for a way to calculate which placeholder goes with which possibility.
Eg:
Possibility 1 - PlaceHolder 1 (With a 0)
Possibility 95 - PlaceHolder 1 (With 1)
Possibility 189 - PlaceHolder 1 (With a 2)
- Reelix
-= Reelix =-
|
|
|
|
|
Reelix wrote: I have 94 unique placeholders, with a possible digit on the end.
With a single digit ? Then it means that you have 10 choices for each unique placeholder. So, a total of 940 combinations.
Reelix wrote: I have 16581375 total possibilities.
It's a bit more than 940, don't you think ? So, you cannot fit all your possibilities in your 940 combinations.
|
|
|
|
|
Sorry, my mistake
Multiple Digits
-= Reelix =-
|
|
|
|
|
It's not clear what your problem is. You need to define it better if you want some help with it.
For example, what's the relationship between "placeholders" and "possibilities"? What are your constraints? How is the digit related to the other items?
|
|
|
|
|
Please elaborate (maybe you too will gain some insight).
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
|
|
|
|
|
Reelix wrote: I'm wondering for a way to calculate which placeholder goes with which possibility.
Then you will need a relationship between placeholders and possibilities. Do you have such a relationship?
|
|
|
|
|
Hi all. I've been working on a model in Excel that I'm considering porting into C/C++. I've been using the "Goal Seek" function in Excel to find a value in one cell that causes the results in another cell to equal some target value.
Is there an existing numerical recipe/algorithm to perform a similar function in C without reinventing the wheel?
Thanks for any help!
|
|
|
|
|
Not in C/C++, but this is a custom implementation in VB:
http://www.bmsltd.ie/DLCount/DLCount.asp?file=GoalSeek.zip[^]
Goal seeking is based on linear interpolation, perhaps you can adapt the VB code to C++?
I'm not too familiar with COM, etc. so I don't know the details but I do know that you can make calls to Excel from C++, maybe you can call the Excel Goal Seek function using COM (by loading the Excel .dll)?
|
|
|
|
|
"...but I do know that you can make calls to Excel from C++..."
Well, THAT would solve my problem! I've been doing a lot of processing in Excel (nicer, because I can see the numbers all laid out), then saving data to a text file, reading it into my C program and continuing my model that way. If I could just make calls right into a spreadsheet I could save myself a lot of dumb grunt labor. I'll check into that. Thanks!
|
|
|
|
|
Here[^] is a Microsoft knowledge-base article that provides some explanation. I think you have to use MFC to do it.
If you want to use Managed C++, here's a nice CP article:
Link[^].
I don't know a whole lot about COM, etc...so you might want to try asking for more details in the C++ forums here. Somebody can probably give you more assistance there.
|
|
|
|
|
KimN wrote: Is there an existing numerical recipe
There is a famous book called "Numerical Recipes", the original editions are available online for free. See here[^]. I think you need some adobe plugin to view the books - it is well worthwhile.
What you are interested in is optimisation of functions. The way this is typically done is you define a function that you want to minimize, e.g.
double func(double* x)
which takes N variables in the array 'x' and returns a single value. An optimization routine will attempt to find the values of 'x' that minimize the function. A very simple workhorse is called the downhill simplex method in multidimensions, but to you it is simply a function Amoeba to which you pass mainly a pointer to your function, the number of variables and starting values.
If you want to solve f(x) = c, make func(x) = (f(x) - c)^2
You will find a listing for amoeba in section 10.4 of Numerical Recipes in C.
If you know more about the function you are trying to minimize then there are probably better routines available, but I'd suspect that amoeba will work as well as excel (and be much faster in native code).
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."
|
|
|
|
|
Good answer, nicely explained.
|
|
|
|
|
Hi,
I am looking for the best way to sort multiple lists of unique items so none of the list items match at the same index.
Here is an example of what I want to do.
Original lists:
List 1: A, B, E, F
List 2: A, C, D, E
List 3: A, C, E, F
List 4: A, D, F, G
Should be sorted to:
List 1: A, B, E, F
List 2: C, A, D, E
List 3: E, F, A, C
List 4: D, G, F, A
Can anyone see a good way to solve this? Let me know if the above doesn't make sense.
Thanks
J
|
|
|
|
|
If the elements of the list can be completely random, then it seems to me you'd have to do this brute-force style. I don't see an obvious algorithm for speeding this up.
I do know that genetic algorithms are used to generate Sudoku tables (which is a similar problem to the above), but GA's are rather non-trivial to implement. It's probably easier to brute-force it for small lists.
|
|
|
|
|
Thanks, yeah I was thinking that I might need to do something pretty ugly to get this working. I've potentially got 5 sets of 42 items to sort so it could turn into alot of cycles to get 5 unique sets.
J
|
|
|
|
|
jrg2000 wrote: I've potentially got 5 sets of 42 items to sort
As a matter of interest, how many different items can there be in each set of 42 and do you have repeats? e.g. the sets are collections of different elements from a set of 80 elements, with no repeats OR the sets are collections from 10 elements with arbitrary numbers of repeats.
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."
|
|
|
|
|
I think this is really a form of a timetable problem, for which there are a number of references and algorithms on the web. Genetic algorithms are one common approach.
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."
|
|
|
|
|
Thanks I didn't think of timetables but that is exactly what I am trying to do. I'll definately look into that.
J
|
|
|
|
|
I would assume the best way, is the following.
1. Assume the first list will not be sorted.
2. Move down the first list, verifying that each subsequent list doesn't have the matching item.
3. If an item matches in that list with the current item in the first list, push it to the end.
4. Iterate till the end.
5. Once at the end, you look over the last items, if any match the final element of the first list, then you must swap that item with one of the items in the list that doesn't conflict with the first list's item.
Basically, once you're at the end, you're down to a single lookup for each list. That should be as simple as you can get it.
Does that make sense?
|
|
|
|
|
Andrew Rissing wrote: I would assume the best way, is the following.
This is a way, it may not be the best way. The reason is that it there is no guarantee that it will work. When you find a clash you make a decision as to what swap to make to resolve it. There are probably many ways to resolve each clash - you choose one. If you make the wrong choice your algorithm may get stuck (i.e you end up with a clash that you cannot resolve - all the elements you have left to swap with clash as well) - there is no way of backtracking in your algorithm to change those earlier choices. If you include backtracking to try all the choices you can make - then you have a simple exhaustive search.
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."
|
|
|
|
|
Ah, this should be easy.
Assume you have list1 fully filled.
list2 = new list<char>();
for (int i = 1; i < list1.size(); i++)
{
list2.push_back(list1.at(i));
}
list2.push_back(list1.at(0);
</char>
Basically, you're shifting indices by one, and keep doing it for every index. The theoretical maximum number of lists you can make is the size of the initial list, since you can only shift indices that much before they repeat again (informal proof). I can demonstrate this more formally, but I won't write it here.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
