Sorting algorithms/Permutation sort: Difference between revisions
jq
(Nimrod -> Nim) |
(jq) |
||
Line 805:
Sorted: [1, 2, 3, 4, 6, 8, 9]
</pre>
=={{header|jq}}==
'''Infrastructure''':
The following function generates a stream of permutations of an arbitrary JSON array:
<lang jq>def permutations:
if length == 0 then []
else
. as $in | range(0;length) | . as $i
| ($in|del(.[$i])|permutations)
| [$in[$i]] + .
end ;</lang>
Next is a generic function for checking whether the input array is non-decreasing.
If your jq has until/2 then its definition here can be removed.
<lang jq>def sorted:
def until(cond; next):
def _until: if cond then . else (next|_until) end;
_until;
length as $length
| if $length <= 1 then true
else . as $in
| 1 | until( . == $length or $in[.-1] > $in[.] ; .+1) == $length
end;</lang>
'''Permutation-sort''':
The first permutation-sort solution presented here works with jq 1.4 but is slower than the subsequent solution,
which uses the "foreach" construct introduced after the release of jq 1.4.
"foreach" allows a stream generator to be interrupted.
{{works with|jq|1.4}}
<lang jq>def permutation_sort_slow:
reduce permutations as $p (null; if . then . elif ($p | sorted) then $p else . end);</lang>
{{works with|jq|with foreach}}
<lang jq>def permutation_sort:
# emit the first item in stream that satisfies the condition
def first(stream; cond):
label $out
| foreach stream as $item
( [false, null];
if .[0] then break $out else [($item | cond), $item] end;
if .[0] then .[1] else empty end );
first(permutations; sorted);</lang>
'''Example''':
<lang jq>["too", true, 1, 0, {"a":1}, {"a":0} ] | permutation_sort</lang>
{{out}}
<lang sh>$ jq -c -n -f Permutation_sort.jq
[true,0,1,"too",{"a":0},{"a":1}]</lang>
=={{header|Mathematica}}==
| |||