On Jul 28, 2009, at 11:06 AM, Sittampalam, Ganesh wrote:
perms = sortByM (const [True,False])
This doesn't seem right, since the comparison function is inconsistent
I was also wary about this point, e.g. QuickSort depends on
transitivity.
and moreover the results will depend on the sorting algorithm chosen.
Is it only that different sorting algorithms enumerate all
permutations in different orders or is there a sorting algorithm, such
that the above definition does not enumerate all permutations?
Here is some shirt-sleeved reasoning:
Every sorting algorithm :: [Int] -> [Int] that actually sorts can
describe every possible permutation (if there is a permutation that
cannot be realised by the sorting algorithm then there is an input
list that cannot be sorted). Hence, if this sorting algorithm is
`sortBy p` for some predicate p then there are possible decisions of p
to produce every possible permutation. If p makes *every* decision non-
deterministically then certainly the specific decisions necessary for
any specific permutation are also made.
Hence, perm as defined above can yield a list that contains all
permutations of the input (at least once) regardless of the sorting
algorithm.
Where is the hitch?
Sebastian
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
