|
Member 6038196 wrote: I'm new to recurrent SOMs.
I.e. are you new to Turkic currency [^]?
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
[My articles]
|
|
|
|
|
lol I wish it was that simple. More like [^]
|
|
|
|
|
I posted this on C# and realized later this might be a more appropriate location for it.
Hi,
I have been searching around for a single elimination algorithm / pseudo code for tournament brackets and I haven't found a single site on it. The best I found was Wikipedia explaining single elimination. I have been reading code project articles for a while now and I know there are many experience and very knowledgeable developers here. Since this is fairly simple to code I was hoping if somebody could help me out with the code/pseudo code or an algorithm for it. I would appreciate it a lot. Looking forward to your replies.
|
|
|
|
|
You create a binary tree where the leaves represent the tournament's contestants. Each pair of contestants under an interior node play a match, and the winner then occupies that interior node.
Likewise, an interior node that has two other interior nodes under it represents the winner of the match between the winners corresponding to those two interior nodes.
The root of the binary tree represents the winner of the tournament.
Tree construction: One approach uses the Composite design pattern, an abstract Node class with two derived classes: Contestant and InteriorNode. Start with a list of Contestants. While that list has more than one element, combine two elements under a new InteriorNode, remove those elements from the list, and insert the new InteriorNode in the list. The list should be ordered by increasing depth, so that, for example, all Contestants are paired before any InteriorNodes are paired.
When the list is down to one element, that's the root of the tree.
modified on Friday, April 3, 2009 10:21 AM
|
|
|
|
|
Is there an algorithm that does a upside-down, upside-down tree. i.e, right side up(root on bottom). Thanks.
|
|
|
|
|
Tree algo:
1. Grasp page in both hands.
2. Turn page 180 degrees.
|
|
|
|
|
Very insightful. I see why your an expert now. Would have never figured that one out myself.
Quick question. If said tree isn't on paper but on my computer screen, do I grab the computer screen and flip it 180 degrees or the computer itself.
|
|
|
|
|
Seriously, it wasn't clear what your problem was. Do you just want to draw the tree upside down on the screen? If so, for a display of height H, substitute (H - y) for every y coordinate to flip the tree.
|
|
|
|
|
Sorry. I want to know if is something like treeview but where the root is on the bottom and everything goes up.
|
|
|
|
|
Oh, I thought you might be interested in an algorithm, since this is the Algorithms forum and your title was "Tree algo". Since you're looking for a suggestion on a graphics package, you might want to post your question in the Lounge.
|
|
|
|
|
Sorry. I'll try there. Thanks for your help.
|
|
|
|
|
Hello,
I have some 3d points (not self intersecting). the shape of the points is looking like / (forward slash) from profile, It is actually a slice of a 3d object, cut with a rotated plane.
I want to calculate the area of 3d points and its centre. For 2d case, i use the following
http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]
but, how can i extend the 2d case to 3d for area and its centre?
Thanks in advance.
Bekir.
|
|
|
|
|
If you could rotate the points so they all have the same Z coordinate, you could then ignore the Z coordinate and apply the 2D formulas for the area and centroid.
Rotation will not change the area. Apply the reverse rotation to the calculated centroid to get the centroid of the original 3D points.
|
|
|
|
|
Thank you,
i will try that and i think it will solve the problem but it will create a bit of overhead.
Bekir.
|
|
|
|
|
What you want is a 2D coordinate system in the plane of intersection, then you can use your equation for area.
Assume that your original points are represented as vectors {Vk} from some origin O (this is your original 3D coordinate system).
As you have the equation of the plane, choose one point on it as the new origin Op, and choose two orthogonal unit vectors (U1, U2) that lie in the plane as the new axes. (i.e. choose two orthogonal vectors orthogonal to the normal of the plane)
Then in your new coordinate system, the 2D coordinates of the point Vk are:
( (Vk-Op).U1, (Vk-Op).U2 )
i.e. you simply project the 3D vector from your new origin onto your new axes.
Note - this includes Alan's solution, the vectors U1 and U2 would be rows of his rotation matrix. It's just a different way of looking at things.
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."
|
|
|
|
|
Does anyone have a stable Quicksort? I have looked at many, and they all seem to have a problem in that they swap elements that are not equal to the pivot element before knowing whether the swapped elements match any other element. see the following example:
014447222563 where '3' is the pivot
You will swap the '4's and '2's leaving:
012227444563
and the final swap:
012223444567
however, the swaps of the '2's and '4's (done one at a time from the outside) put them out of order before you even get to see that they are duplicates.
The only way I know of is to supply an additional key element in the record (sorted along with the key) which contains the input record number of the key. This is time expensive, rebuilding the records just to sort them, only to unbuild them when the sort completes. It is easily done, however, with indirect sorting, where the indirect array is an array of structures containing both the pointer to the actual record and also the input record number. Swapping the indirect pointers as records keeps the original record number with its record definition where it can be checked when an equal comparison is encountered. Of course, indirect sorting is inefficient when huge arrays (> 2GB)are involved because the underlying data remains scattered in memory, and paging in huge blocks of memory to compare a small record is a terrible waste.
Dave Augustine
|
|
|
|
|
If you are sorting numbers then consider using a bucket sort which is stable. It's also faster than QuickSort in some circumstances.
Greetings - Gajatko
Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.
|
|
|
|
|
gajatko,
Thank you for the reply, but I was specifically interested in a Stable Quicksort.
Off topic, I see that you answered this over 3 hours ago. I checked the forums no more than 5 minutes ago and this message was not there, I got your reply on my Email and answered it from there. Guess I'll have to tell Chris.
Dave.
|
|
|
|
|
Have a look at STL's stable_sort[^]. Perhaps this is what you're after.
Steve
|
|
|
|
|
Steve,
Thank you for the reference. Turns out that StableSort is a merge sort. Of course it is stable. You are always comparing elements before you select one or the other to output. My contention, having read many of the Articles on quicksort and seen their algorithms, is that they attempt to be stable once the pivot and an element is compared, but totally ignore whatever has not been seen (between i and j) when swapping i and j elements to satisfy the sort conditions i < pivot, j >= pivot. Note that you have only compared i and pivot and j and pivot, (by the algorithm, i < j), but you know nothing about what lies between i and j. Swapping these two elements may cause an unstable sort as I demonstrated in my initial post.
My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.
Dave.
|
|
|
|
|
My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.
I'm unaware of any mathematical restriction on the ability to perform a stable sort without requiring either extra time or extra storage (insertion and selection sorts, e.g., require no extra storage, but a lot of extra time) but I am also unaware of any implementations that require neither extra time nor storage. That having been said, in many applications it is better to physically move around pointers than to move around data, and if one is shuffling pointers the extra storage isn't really a problem.
Incidentally, I've invented a sorting algorithm I've never seen elsewhere which performs slightly fewer than n*lg(n) comparisons (as does a good QuickSort implementation, btw) but yields the results in order (the first item will be made available after n-1 comparisons; the next item will be available after lg(n) comparisons, etc. The storage and time overhead for book-keeping (about 16 bytes/element on a 32-bit machine, and sub-logarithmic time but with a hefty constant) probably make the sort impractical, but having the sort yield the results in order is cute.
|
|
|
|
|
supercat9,
Thank you for the reply. I am aware that it will take more time or storage to stablize the sort. The question is how much more. I am already running into conditions that have sometimes forced me to go to an external sort, not enough virtual memory available. Especially under full memory condition, you do not want to swap by exchanging pointers, you will be paged to death the entire time. At least by scanning up or down in memory for adjacent records, you will stay in a small number of pages (3 to 6) the records in their original positions may result in a page fetch for each record.
If you include a tie-breaker element in the keys, it takes that extra room in each record, space that always must be swapped during exchanges, and sometimes must compared when the rest of the key matches. If the original record has another field that can be used as a tie-breaker, then the extra space and the exchange time already exist, and it is only a matter of comparing the tie-breaker if the rest of the key matches, but, this requires having to specify the parameters of the tie-breaker so the compare can be done and the type of element may not be the same as the original key. All of this is doable, just a matter of what is the "best".
Dave.
|
|
|
|
|
can someone tell me the O() of this:
struct pivot {
int l,r;
};
function partition( array, left, right ) {
pivot.l = pivot.r = left
for i = left to right
{
if (array[i] >= pivot.l)
pivot.r += 1
else
swap(pivot,i)
}
return pivot.l
}
swap_r (range, index) {
int t=range.r
while(range.l<=t)
swap_i(t--,index)
}
swap_i (index1, index2) {
}
function quicksort(array) {
int p = partition(array,0,length-1)
quicksort(array,0,p)
quicksort(array,p+1,length-1)
}
It is psuedo-code, but you get the idea. I think it's O(n2Log(n)) but I'm not sure. If you could figure out how to put 1 element in front of x elements better, it'd be what you want.
modified on Friday, April 3, 2009 8:29 PM
|
|
|
|
|
What's up with the copyright mind-virus? from the copy right act of 1976:
In no case does copyright protection for an original work of authorship
extend to any idea, procedure, process, system, method of operation,
concept, principle, or discovery, regardless of the form in which
it is described, explained, illustrated, or embodied in such work.
|
|
|
|
|
bulg,
Thank you for the replies. I would respond to your second response (I got an email notification), but it appears that you deleted the post. Do you have an actual algorithm for the "lazy quick sort"? Seems interesting.
For your algorithm in this post, it seems a bit strange and incomplete or inaccurate. How can you swap an integer and a structure of two integers swap(pivot,i) ?
As far as copyrights go , sure it is 25 years old, but has it been renewed? Is it still active? What constitutes "fair use"? This has been argued in the courts many times. I do not have deep pockets so I just refuse to quote an author. I did discuss the point he made about the requirement for the extra space required for the stable quicksort, a size equal to the original size of the piece being partitioned. Similar to a merge sort, but with the terrible disadvantage that merge sort put the elements in the correct sequence, stable quicksort only copies them in an unordered state to two buffers (less than and greater than the pivot) and requires that the two partitions still need to be sorted. What a waste.
Dave.
|
|
|
|
|