Sorting algorithms/Permutation sort: Difference between revisions
Content added Content deleted
(Added Crystal implementation.) |
(→{{header|Python}}: Added cleaner Python 3 version, with more_itertools.window) |
||
Line 1,530: | Line 1,530: | ||
in_order = lambda s: all(x <= s[i+1] for i,x in enumerate(s[:-1])) |
in_order = lambda s: all(x <= s[i+1] for i,x in enumerate(s[:-1])) |
||
perm_sort = lambda s: (p for p in permutations(s) if in_order(p)).next()</lang> |
perm_sort = lambda s: (p for p in permutations(s) if in_order(p)).next()</lang> |
||
<br/> |
|||
The <code>more_itertools</code> package contains many useful functions, such as <code>windowed</code>. This function gives us a sliding window of chosen size over an iterable. We can use this window, among other things, to check if the iterable is sorted. |
|||
{{works with|Python|3.7}} |
|||
<lang python>from itertools import permutations |
|||
from more_itertools import windowed |
|||
def is_sorted(seq): |
|||
return all( |
|||
v1 <= v2 |
|||
for v1, v2 in windowed(seq, 2) |
|||
) |
|||
def permutation_sort(seq): |
|||
return next( |
|||
permutation |
|||
for permutation in permutations(seq) |
|||
if is_sorted(permutation) |
|||
) |
|||
=={{header|R}}== |
=={{header|R}}== |