|
Mathematica from Wolfram should do it.
|
|
|
|
|
You're a few months late. 
Thanks, but I ended up using Visual C# Dot Net 4.0 BigInteger class.
|
|
|
|
|
here is a problem. I've got an array of records with 2 fields: ID and ParentID. This array represents a hierarchical tree, where each node can have multiple children.
What I need is to convert it to a more compact form, like this (code is in C#)
public class TreeBranch
{
int ID;
List<TreeBranch> Children;
.........................
}
................
List<TreeBranch> MainTree; // a collection that contains the whole tree
I've came up with a dizzy solution, but I don't like it since it is O (n^2).
Any ideas will be appreciated )
|
|
|
|
|
What was your solution?
Anyway, that way I might do this would be like this: while you are building the tree, also keep an array of your tree nodes, indexable by ID. Then when you want to add a node to its parent's Children, you can just index into that array to get the parent object.
edit: if the nodes are in pre-order you can build the array while you process the items, otherwise you'd need two passes: one to fill the array, and one to build the tree (that is, of course, still O(n) )
modified on Thursday, July 29, 2010 7:21 AM
|
|
|
|
|
Hi & thanks for reply&interest.
Nevermind my previous thought - that idea was not working )
What I need to do is to write a recursive method, so it will be able to work at any depth.
Not that great with recursion, but job needs to be done.
Once I'll finish that, I'll post an answer to share with others.
|
|
|
|
|
Why would you need recursion here? A simple loop over all items would do.. unless there's something you haven't told us yet?
|
|
|
|
|
Partly my fault:
original message has been parsed and it dropped the fact, that the field Children is a generic of type TreeBranch - it contains children of a certain node. Each of those children can have its own List of children, and so on. Anyways, it's all about converting an array of objects which have ID and ParentID into a tree hierarchy. Consider a case
an array: (ParentID;ID)
-,1
1,2
1,3
2,4
4,5
should look something like
1-
2-
3 4-
5
Because the depth of the tree is unknown, recursion is the only option - we have no idea about the nodes, that are inhereted from the current.
For some dumb security reasons of my job I can't post the code here, but I'll do that later, since the task is very real life
|
|
|
|
|
Your diagram is a bit confusing, what do you really mean?
Btw, the depth of the resulting tree has no relevance - in fact the algorithm I described works for directed graphs in general (trees or not) even if they have disjunct subgraphs or cycles or both (making the "depth" undefined).
|
|
|
|
|
|
Add each node to a HashTable using the ID as the key.
Loop through the nodes and yourHash[this.ParentID].AddNode(this);
I don't know O notation, but I think that would be 2n instead of n^2.
|
|
|
|
|
T M Gray wrote: I don't know O notation, but I think that would be 2n instead of n^2.
That's O(n) instead of O(n2)
(fyi, that's what I said, but with a HashTable instead of an array)
|
|
|
|
|
<br />
public interface IHierarchy<T><br />
{<br />
string Name { get; set; }<br />
List<T> Relations { get; set; }<br />
}<br />
<br />
public class Employee : IHierarchy<Employee><br />
{<br />
private string name;<br />
<br />
public string Name<br />
{<br />
get { return name; }<br />
set { name = value; }<br />
}<br />
private List<Employee> relations;<br />
<br />
public List<Employee> Relations<br />
{<br />
get { return relations; }<br />
set { relations = value; }<br />
}<br />
<br />
}<br />
<br />
public class Hierarchy<T> where T : IHierarchy<T><br />
{<br />
private List<T> hierarchylist;<br />
public Hierarchy(List<T> list)<br />
{<br />
hierarchylist = list;<br />
}<br />
<br />
<br />
private string Replicate(string s, int count)<br />
{<br />
string output = string.Empty;<br />
for (int i = 0; i < count; i++)<br />
{<br />
output += s;<br />
}<br />
return output;<br />
}<br />
public void Render()<br />
{<br />
Render(hierarchylist, 0);<br />
}<br />
private void Render(List<T> list, int Level)<br />
{<br />
<br />
foreach (T emp in list)<br />
{<br />
<br />
Console.WriteLine(Replicate("-", Level) + emp.Name);<br />
if (emp.Relations != null)<br />
{<br />
int NextLevel = Level + 1;<br />
Render(emp.Relations, NextLevel);<br />
}<br />
<br />
}<br />
<br />
}<br />
<br />
<br />
}<br />
private void button1_Click(object sender, EventArgs e)<br />
{<br />
<br />
#region Heirarchy<br />
List<Employee> c4 = new List<Employee>();<br />
c4.Add(new Employee { Name = "C41", Relations = null });<br />
c4.Add(new Employee { Name = "C42", Relations = null });<br />
<br />
List<Employee> c1 = new List<Employee>();<br />
c1.Add(new Employee { Name = "C11", Relations = null });<br />
c1.Add(new Employee { Name = "C12", Relations = null });<br />
<br />
<br />
List<Employee> p1 = new List<Employee>();<br />
p1.Add(new Employee { Name = "C1", Relations = c1 });<br />
p1.Add(new Employee { Name = "C2", Relations = null });<br />
List<Employee> p3 = new List<Employee>();<br />
p3.Add(new Employee { Name = "C3", Relations = null });<br />
p3.Add(new Employee { Name = "C4", Relations = c4 });<br />
<br />
List<Employee> employees1 = new List<Employee>();<br />
employees1.Add(new Employee { Name = "P1", Relations = p1 });<br />
employees1.Add(new Employee { Name = "P2", Relations = null });<br />
employees1.Add(new Employee { Name = "P3", Relations = p3 });<br />
Hierarchy<Employee> empH = new Hierarchy<Employee>(employees1);<br />
empH.Render();<br />
#endregion<br />
<br />
<br />
<br />
<br />
}<br />
|
|
|
|
|
Borrowing from SQL, you might want to look at this: Modified Preorder Tree Traversal Algorithm[^]
It's intended for non-cyclic trees and is optimized for reading. It's a little complicated to setup, but is quite efficient (O(n)) for recursive lookups.
I don't have a C# implementation, but it could easily be done in a DataTable and retrieved from there. You could also add a depth to the table allowing for recursive pulls that would stop after X levels down.
Anyways, see if that helps.
|
|
|
|
|
I am designing a conference management system in C#. Part of the functionality involves automatic assignment of papers to conference reviewers. Now the authors of the papers specify keywords while they upload their papers to a database. The reviewers specify areas of interest while the register. I am trying to find ideas for an algorithm that can perform automatic assignment of the papers in a database table to reviewers in another table. The criteria for selection is comparison of the keywords to interests and deciding which reviewer (based on his interests) is most suitable for a paper or set of papers.
Thanks
|
|
|
|
|
for each paper you could consider each reviewer, calculate the number of matching keywords, then pick the one with the highest match.
potential problem: a reviewer with more keywords is likely to get (much) more papers assigned.
refinement 1:
calculate the the full matrix of paper-reviewer affinity as above, then pick the one article and reviewer that have the largest drop in affinity from the top to the second; that is the one where a specific reviewer is much more preferred than anywhere else. Now discard the article, and repeat this step again. and again. when a reviewer is getting too much work, discard him from the matrix and continue.
refinement 2:
take the order of the keywords into account: rather than just counting the matches, give them a weight that corresponds to their position in the list for article and reviewer respectively (say article keywords A,B,C,D and reviewer keyword A,E,F,B then A yields much more than B.
|
|
|
|
|
Is there any way you can translate this into C# code? That is the part I am confused about.....
|
|
|
|
|
I use a PC with a keyboard; and Visual Studio most often. Do you have a specific question?
|
|
|
|
|
alkowarizmi wrote: Is there any way you can translate this into C# code?
Yes he can. Is he going to do it for you? I don't think so. 
|
|
|
|
|
<br />
public class Paper<br />
{<br />
private string _name;<br />
<br />
public string Name<br />
{<br />
get { return _name; }<br />
set { _name = value; }<br />
}<br />
private List<string> keywords;<br />
<br />
public List<string> Keywords<br />
{<br />
get { return keywords; }<br />
set { keywords = value; }<br />
}<br />
<br />
private Reviewer _paperreviewer;<br />
<br />
public Reviewer PaperReviewer<br />
{<br />
get { return _paperreviewer; }<br />
set { _paperreviewer = value; }<br />
}<br />
}<br />
<br />
public class Reviewer<br />
{<br />
private string _name;<br />
<br />
public string Name<br />
{<br />
get { return _name; }<br />
set { _name = value; }<br />
}<br />
private List<string> keywords;<br />
<br />
public List<string> Keywords<br />
{<br />
get { return keywords; }<br />
set { keywords = value; }<br />
}<br />
<br />
private int reviewCount;<br />
<br />
public int ReviewCount<br />
{<br />
get { return reviewCount; }<br />
set { reviewCount = value; }<br />
}<br />
}<br />
<br />
<br />
class PaperList<br />
<br />
{<br />
private List<Reviewer> _reviewers = new List<Reviewer>();<br />
private List<Paper> _papers = new List<Paper>();<br />
private IReviewStrategy _reviewstrategy;<br />
<br />
public PaperList(List<Paper> papers, List<Reviewer> reviewers)<br />
{<br />
_papers = papers;<br />
_reviewers = reviewers;<br />
}<br />
<br />
public void SetReviewStrategy(IReviewStrategy reviewstrategy)<br />
{<br />
this._reviewstrategy = reviewstrategy;<br />
}<br />
<br />
public void Review()<br />
{<br />
_papers=_reviewstrategy.FindReviewer(_papers, _reviewers);<br />
foreach (Paper p in _papers)<br />
{<br />
string reviewername=string.Empty;<br />
if (p.PaperReviewer != null)<br />
reviewername = p.PaperReviewer.Name;<br />
else<br />
reviewername = "None";<br />
Console.WriteLine(p.Name + " is reviewed by " + reviewername);<br />
}<br />
}<br />
<br />
}<br />
<br />
public interface IReviewStrategy<br />
{<br />
List<Paper> FindReviewer(List<Paper> papers, List<Reviewer> reviewers); <br />
}<br />
<br />
public class SimpleReviewStrategy:IReviewStrategy<br />
{<br />
public List<Paper> FindReviewer(List<Paper> papers, List<Reviewer> reviewers)<br />
{<br />
int KeyWordMatch=0;<br />
Reviewer bestReviewer = null;<br />
int bestKeyWordCount=0;<br />
foreach (Paper p in papers)<br />
{<br />
bestReviewer = null;<br />
bestKeyWordCount=0;<br />
foreach (Reviewer r in reviewers)<br />
{<br />
KeyWordMatch = CountKeyWordOccurences(p.Keywords, r.Keywords);<br />
if (KeyWordMatch > 0 && KeyWordMatch >= bestKeyWordCount)<br />
{<br />
if (KeyWordMatch > bestKeyWordCount)<br />
{<br />
bestKeyWordCount = KeyWordMatch;<br />
bestReviewer = r;<br />
}<br />
else<br />
{<br />
if (r.ReviewCount < bestReviewer.ReviewCount)<br />
{<br />
bestKeyWordCount = KeyWordMatch;<br />
bestReviewer = r;<br />
}<br />
}<br />
}<br />
<br />
}<br />
if (bestReviewer != null)<br />
p.PaperReviewer = bestReviewer;<br />
}<br />
return papers;<br />
}<br />
private int CountKeyWordOccurences(List<string> list1, List<string> list2)<br />
{<br />
int counter = 0;<br />
foreach (string l1 in list1)<br />
{<br />
if (list2.Contains(l1))<br />
counter++;<br />
}<br />
return counter;<br />
}<br />
}<br />
<br />
private void button1_Click(object sender, EventArgs e)<br />
{<br />
<br />
List<string> keywordset1=new List<string>();<br />
keywordset1.Add("music");<br />
List<string> keywordset2=new List<string>();<br />
keywordset2.Add("music");<br />
keywordset2.Add("science");<br />
List<string> keywordset3=new List<string>();<br />
keywordset3.Add("animal");<br />
keywordset3.Add("bird");<br />
keywordset3.Add("trees");<br />
List<string> keywordset4=new List<string>();<br />
keywordset4.Add("men");<br />
keywordset4.Add("women");<br />
<br />
List<string> keywordset5=new List<string>();<br />
keywordset5.Add("men");<br />
keywordset5.Add("animal");<br />
keywordset5.Add("music");<br />
keywordset5.Add("women");<br />
<br />
List<string> keywordset6=new List<string>();<br />
keywordset6.Add("love");<br />
keywordset6.Add("music");<br />
<br />
List<string> keywordset7 = new List<string>();<br />
keywordset7.Add("sex");<br />
<br />
<br />
List<Reviewer> reviewers = new List<Reviewer>();<br />
reviewers.Add(new Reviewer { Name = "Roshan", Keywords = keywordset2, ReviewCount = 0 });<br />
reviewers.Add(new Reviewer { Name = "Alice", Keywords = keywordset4, ReviewCount = 0 });<br />
<br />
List<Paper> papers = new List<Paper>();<br />
papers.Add(new Paper { Name = "P1", Keywords = keywordset5, PaperReviewer = null });<br />
papers.Add(new Paper { Name = "P2", Keywords = keywordset6, PaperReviewer = null });<br />
papers.Add(new Paper { Name = "P21", Keywords = keywordset7, PaperReviewer = null });<br />
<br />
PaperList simple = new PaperList(papers, reviewers);<br />
simple.SetReviewStrategy(new SimpleReviewStrategy());<br />
simple.Review();<br />
<br />
<br />
}<br />
|
|
|
|
|
I apologize in advance if this is the wrong forum for this post. It is definitely algorithm-related, though it may classify just as much as a personal RFP:
I am looking for a programmer who is looking for an algorithmic challenge. While I am a business applications developer by day, my hobby/pet-project has been the development of a railroad simulator/"video game". (Check out this series of screen shots.) Most of my endeavor has been very successful. However, where I feel totally defeated is in programming of the brake systems, which deal with the flow of compressed air.
I do not believe you need to be an expert in either brake systems or fluid dynamics. You just have to be good at solving algorithms. I can give you enough of a crash course to know what you need regarding trains. Regarding fluid dynamics, one has to remember this is a real-time video game. I don't want to waste lots of CPU power performing excessively accurate calculations. In fact, as long as the desired behavior is achieved, I don't really care how realistic the underlying algorithm is.
"What is the 'desired behavior'," you ask? Take a look at this article, which describes in detail what I'm trying to simulate. If you have general questions about what I am asking, please post those publicly on this thread so others can read the responses. However, I have also enabled private responses to this message for those who would like to proceed with this and therefore need to take the discussion outside of this thread.
As I said before, this is a pet project. It is not commercially funded. Therefore I do not have resources to pay -- at least not a lot. I might be able to contribute a little something for your time if you come up with the winning algorithm. But primarily you should only take this on if you're in it for the interesting challenge. Based on my experience, it's guaranteed to give you hours of hair-pulling frustration and nightmares in between.
Thanks for reading.
|
|
|
|
|
|
Doesn't look much like a game to me. But Choo-Choo!, what are you using to develop the GUI? I'm in to massivly parallel SIMD, OpenCL development, and a but of Directcompute, but there is not much info on the topic yet. Let me look at the parper describing the problem and consult my prinston math book. ~brb
|
|
|
|
|
I have a hard time picking a term to define what this program is. It's not really a "simulation" because it isn't scientifically accurate or complex enough. It's not a "game" because there's no end objective.
What probably isn't clear from the screen shots is that you start with a "Tron"-like grid. You model all the landscape yourself. You add the engines and train cars yourself. It's basically a model train layout without space limitations. You're only limited by your computer's specs. But I also come from a disciplined C++ training from before you could get gigs of RAM for pennies. My data structures squeeze the most out of every byte so you don't have to have the worlds greatest gaming computer to get a lot of capacity out of the software.
It's very similar to "Trainz" by Auran Games. There are reasons that I went through the trouble to write my own program instead of just using my copy of "Trainz", but I'm not going to bore everyone with that explanation here.
|
|
|
|
|
It's really not an algorithm. It's linear algebra. You need to know the state of the charge in the brake in terms of PSI for n cars. Each car dissipates the correct amount of release to slow down the car, and then starts to recharge the reservoir. This can be event driven to start charging, you have to know the rate at which it recharges. The rest is a set of linear equations to find what the correct amount of release is for the set of cars in the system. There are some good videos at MIT for solving linear equations for computer programs, if you google lineal algebra and click on videos. I think it's a long set, but you should get the core fundamentals in the forest 3 lecture.
~PB
|
|
|
|
|
You make some good points. I do know the rates of release and recharge and have been able to successfully develop computations when the locomotive is the only control point. However, I run into problems adding to the process the conditions where by air can be released from or added to the main pipe at each individual car valve.
There's also the issue of rapid set/release action. From the railroading standpoint it would not be correct to jostle the brake lever rapidly. However, good practice as a programmer is of course to try to anticipate all possible user input. I haven't been able to successfully track the creation and dissipation of pressure waves that would result from a rapid jostling of the brake lever.
I'll look up the videos you mentioned. Having fought with this as much as I have, you may well be right that the source of my issues is lack of knowledge in the appropriate mathematics (and/or physics) rather than any inability to develop code.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
