Eg: In a list of three items ("1", "2", "3") the user is asked which item is higher, 1 or 2. They select 1. They are then asked which is higher, 2 or 3. They select 3. The system then reasons: "1 is higher than 2. If 3 is lower than 2 it must logically be lower than 1 also." etc. (So that you can sort a list of items with the fewest theoretical comparisons possible.) Thanks!
Is there a program or app that will let you sort items using manual choices and deductive logic?
-
0Posted on cstheory: http://cstheory.stackexchange.com/questions/5615/is-there-a-program-app-algorithm-that-can-sort-items-using-manual-choices-and. – 2011-03-25
4 Answers
You can use any sorting algorithm. Whenever the sorting algorithm tries to compare two elements, you ask the user. If the sorting algorithm is valid (which it is, since it's a sorting algorithm), the result would be "logically sound".
Edit: It seems that you want your algorithm never to compare $x$ and $y$ if it can already deduce their relative order. Quicksort conforms to this demand. First a pivot is selected (randomly). Then all other elements are compared to it. Now we have two lists - elements smaller than the pivot, and elements larger than the pivot; that's all we know about the lists. Both lists are sorted recursively. So Quicksort is "thrifty".
Mergesort also conforms to this demand. The list is cut into two halves, which are sorted recursively. Then the two lists are merged, using the fact that they're sorted (look it up).
Insertion Sort also conforms to this demand. At stage $i$, we have a sorted list consisting of the first $i$ elements, and we insert element $i+1$ in the correct place by testing it against all elements.
You can check out other algorithm in Wikipedia - probably most of them are "thrifty". Heap Sort, for example, also seems to check.
A second possible aspect of your question is minimizing the number of comparisons. Finding the optimal sorting algorithm is a difficult problem, and you can't expect to solve it except for very small numbers. The asymptotics are well known - you need $\Theta(n\log n)$ comparisons; perhaps the constant is also known, although I'm not aware of this.
-
2The minim$u$m n$u$mber of comparisons is n lg n + O(n). The big-O 'constant' in front of n is greater than -1.4427; -1.329 is achievable. In particular it's possible to merge sort n elements with n lg n - 1.329n + O(log n) comparisons for all large n -- and actually, n doesn't need to be that large. – 2011-03-24
icarsystems.org - expert systems technology. You develop the logic behind data and it gives deduction from users answers.
If you only know a handful of comparisons (without having to compare everything), but you still want to ask about legal deductions (essentially of transitivity), then use 'topological sorting' of the directed graph, where the entities are the nodes, and the comparisons are the edges. (there are other mentions of topological sorting here at math.stackexchange that might give more perspective.
It's not a difficult algorithm to implement, but I don't think there's an off the shelf implementation (like Java's Collections.sort)
This sounds like a problem, made for Prolog. In prolog, you can define such rules (if a > b AND b > c THEN a > c), and you can start with some initial informations (a > b), and let the machine try to solve the question, and ask for more information (b > c) to answer a specific question (a > c).
How you would do extend it to a complete sort, how to do it in particular, I can't remember, I only had a few days contact to prolog, and it was in the mid 90thies. :)