|
if I were needing that, this[^] is one of the places that I would look at; it holds lots of links.
|
|
|
|
|
|
Anyone knows of any math software that has unlimited precision (i.e., 123^123,456,789 mod 987,654,321)? I'm looking into Mathematica Home Edition, but I'm not sure if it does that. I know Maple could calculate PI to as many digits as you want if you were willing to wait, but I'm not sure if that applied to all functions in general or just built-in ones.
|
|
|
|
|
Most, if not all, of the Mathematica/Maple/Mathcad type packages have an arbitrary precision integer and/or rational number capability. Check their online docco and/or user forums. If you're looking for a language to write your own code, Java has BigInteger built in, and there are free packages for other popular languages. (I have used a couple of the C++ ones - the quality does tend to vary a bit, but the good ones are good.)
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
Thanks, forgot about MathCad which I used to love. Does the BigInteger support ridiculously large numbers (i.e., unlimitedly large)? You know any for C#? I downloaded VS2010 to check it out but that think sucks big time.
|
|
|
|
|
Java BigInteger (and any other reasonable implememntation) will grow until you run out of memory (or patience  ). I don't play C#, but a quick google found C# BigInteger Class[^] right here on CP. Re VS2010: I've seen so much suckage reported here I'm not going anywhere near it!
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
That article describes a private BigInteger attempt on an old .NET version (which did not come with a built-in one); since 4.0 .NET has its own, pretty good, BigInteger class, probably very comparable to the venerable Java one.
|
|
|
|
|
Since .NET 4.0 C# has BigInteger too.
|
|
|
|
|
Thanks, Luc. As I noted above, I don't inhabit those realms!
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
Great, now if only VS2010 would play nice.
|
|
|
|
|
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.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
