When I was doing topo sort, it was for a sort tree that did one
comparison per node. You were asking about comparisons that are more
complex than simple numeric comparison.
For the topo sort, the comparison was essentially the sign of the volume
of a pyramid after a 3D rotation.
For pruning
For toposort, though, you'd presumably want a cleverer strategy than just
sorting the nodes, doing a full graph traversal on each comparison.
Alpha-beta pruning I don't know about.
On Thu, 21 Dec 2023, Henry Rich wrote:
Topological sorting was a big topic in graphics back in the day.
I can i
Topological sorting was a big topic in graphics back in the day.
I can imagine that during alpha -beta pruning you might run into some
ordering requirements that require more than simple keys.
Henry Rich
On Thu, Dec 21, 2023, 9:56 PM Elijah Stone wrote:
> > The problem it has is that if elemen
Oh yeah, unicode collation! That's a fun time.
Floats is annoying. You should probably get a choice of invalid operation
exception on nan or straight sign-magnitude interpretation (which is
consistent with ieee total order). But I do concede that either way you
probably want special code fo
> I am curious what applications there are that really need a user-specified
> comparison function (rather than just a sort key, like dyadic /: takes).
There must some applications out there with some sort of smart string
ordering that couldn't be reduced to array ordering. And of course in a
lang
On Thu, 21 Dec 2023, Marshall Lochbaum wrote:
This is a stable algorithm
Yeah--it's the naive in-place version that's unstable.
--
For information about J forums see http://www.jsoftware.com/forums.htm
The problem it has is that if elements compare equal but don't match then
it'll never get down to an array where ~.y has length 1.
Right, of course. Shame on me for being lazy and not bothering to write out
*./2 u/\y.
Modern quicksort hybrids ... always use one bit at a time.
I am curious
This is a stable algorithm because it only ever changes the order of
elements if one's less than the pivot and the other isn't. The problem
it has is that if elements compare equal but don't match then it'll
never get down to an array where ~.y has length 1. You get a stack error
on (<&:*qs _1 2 3)
You can get a three-result comparison from a boolean c by using it
twice, (c-c~). See https://www.jsoftware.com/papers/50/50_00.htm . If
this fails to distinguish elements then they are equivalent under the
ordering, so a stable algorithm has to maintain their input order.
It's my opinion that sor
The same output of your quoted "program"
\:~ _10 1 10 20 _30 15 25 30 0
30 25 20 15 10 1 0 _10 _30
I may have misunderstood your original question, based on subject line. You
appear to want to sort card hands.
You would want to encode cards as integers, where 2-A maps to 0-13. It is a
good
Yeah, I was talking about a stable quicksort, like we see at
https://code.jsoftware.com/wiki/Essays/Quicksort
I guess if you don't care about search stability you can eliminate the
equality test against the pivot value.
Thanks,
--
Raul
On Thu, Dec 21, 2023 at 5:07 PM Elijah Stone wrote:
>
> T
The quicksort I know does not care whether elements are out of order.
Example:
qs=. {{ NB.quicksort adverb; u compare, y array
if. 1>:#~.y do. y return. end. NB.ignore ~.
p=. y{~?#y
s=. y u"_1 _ p
(u qs s#y) , (u qs (-.s)#y) }}
It is unstable, but that is to be expected. And it can be mad
It's probably worth noting here that (for example) the quicksort
algorithm relies on being able to tell whether items are equal. And a
0 1 result can't distinguish between ordering and equality. Many
sorting implementations rely on a _1, 0, 1 result, as a consequence.
That said, you could implemen
(/: verb-to-put-cards-in-order) table-of-hands
For poker, verb-to-put-cards-in-order is
vtpcio =. '23456789TJQKA'&i.
(/: vtpcio) _5 ]\ 'A22345323452'
23452
23453
2
A
Henry Rich
On 12/21/2023 10:29 AM, 'Viktor Grigorov' via Programming wrote:
The first example is lesser, m
The first example is lesser, my bad!
Dec 21, 2023, 15:27 by programm...@jsoftware.com:
> I have a list that I would like to sort using a verb that outputs 0 or 1,
> depending on the two items compared. Since there are length-1 factorial
> possible pairings and hence booleans, I'd thought of th
I have a list that I would like to sort using a verb that outputs 0 or 1,
depending on the two items compared. Since there are length-1 factorial
possible pairings and hence booleans, I'd thought of the table.
Here, the items are hands of playing cards. One hand is greater than another,
if at a
I don't understand the problem statement.
Henry Rich
On 12/21/2023 10:17 AM, 'Viktor Grigorov' via Programming wrote:
Maybe a table, summation and a sort using that:
(/: ([:+/(>/]))) _10 1 10 20 _30 15 25 30 0
Can't imagine that being efficient, but it's better than nothing. The verb I'd
Maybe a table, summation and a sort using that:
(/: ([:+/(>/]))) _10 1 10 20 _30 15 25 30 0
Can't imagine that being efficient, but it's better than nothing. The verb I'd
defined can't deal with rank 2 nouns anyways.
Dec 21, 2023, 14:21 by programm...@jsoftware.com:
> Not quite though. Had I
Not quite though. Had I 5 hands, that'd be !4 booleans.
Dec 21, 2023, 14:11 by programm...@jsoftware.com:
>
> 1 0 0 1 0 /:~ i.5
>
> 1 2 4 0 3
>
>
> On Thursday, December 21, 2023 at 09:03:34 a.m. EST, 'Viktor Grigorov' via
> Programming wrote:
>
> Hey,
>
> Is there an easy way to sort an
1 0 0 1 0 /:~ i.5
1 2 4 0 3
On Thursday, December 21, 2023 at 09:03:34 a.m. EST, 'Viktor Grigorov' via
Programming wrote:
Hey,
Is there an easy way to sort an array with verb returning either 0 or 1, like
the comparison primitives?
The verb that I'd in mind relates to the 2023'
20 matches
Mail list logo
