Anonymous user
Sorting algorithms/Permutation sort: Difference between revisions
rearranges in order of the language.
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
(rearranges in order of the language.) |
||
Line 231:
}
</lang>
=={{header|C++}}==
Since <tt>next_permutation</tt> already returns whether the resulting sequence is sorted, the code is quite simple:
<lang cpp>#include <algorithm>
template<typename ForwardIterator>
void permutation_sort(ForwardIterator begin, ForwardIterator end)
{
while (std::next_permutation(begin, end))
{
// -- this block intentionally left empty --
}
}</lang>
=={{header|Clojure}}==
Line 379 ⟶ 393:
(1 2 3 4 5 6 7 8 9 10)</lang>
=={{header|D}}==
Line 655:
|( l := permute(l) & sorted(l)) \1 & every writes(" ",!l)
end</lang>
=={{header|J}}==
Line 973 ⟶ 852:
</lang>
Warning: This algorithm is very inefficient and Max will crash very quickly with bigger arrays.
=={{header|NetRexx}}==
Uses the permutation iterator '''<tt>RPermutationIterator</tt>''' at [[Permutations#NetRexx|Permutations]] to generate the permutations.
<lang NetRexx>/* NetRexx */
options replace format comments java crossref symbols nobinary
import java.util.List
import java.util.ArrayList
numeric digits 20
class RSortingPermutationsort public
properties private static
iterations
maxIterations
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method permutationSort(vlist = List) public static returns List
perm = RPermutationIterator(vlist)
iterations = 0
maxIterations = RPermutationIterator.factorial(vlist.size())
loop while perm.hasNext()
iterations = iterations + 1
pl = List perm.next()
if isSorted(pl) then leave
else pl = null
end
return pl
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method isSorted(ss = List) private static returns boolean
status = isTrue
loop ix = 1 while ix < ss.size()
vleft = Rexx ss.get(ix - 1)
vright = Rexx ss.get(ix)
if vleft.datatype('N') & vright.datatype('N')
then vtest = vleft > vright -- For numeric types we must use regular comparison.
else vtest = vleft >> vright -- For non-numeric/mixed types we must do strict comparison.
if vtest then do
status = isFalse
leave ix
end
end ix
return status
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
placesList = -
"UK London, US New York, US Boston, US Washington" -
"UK Washington, US Birmingham, UK Birmingham, UK Boston"
anotherList = 'Alpha, Beta, Gamma, Beta'
reversed = '7, 6, 5, 4, 3, 2, 1'
unsorted = '734, 3, 1, 24, 324, -1024, -666, -1, 0, 324, 99999999'
lists = [makeList(placesList), makeList(anotherList), makeList(reversed), makeList(unsorted)]
loop il = 0 while il < lists.length
vlist = lists[il]
say vlist
runtime = System.nanoTime()
rlist = permutationSort(vlist)
runtime = System.nanoTime() - runtime
if rlist \= null then say rlist
else say 'sort failed'
say 'This permutation sort of' vlist.size() 'elements took' iterations 'passes (of' maxIterations') to complete. \-'
say 'Elapsed time:' (runtime / 10 ** 9)'s.'
say
end il
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method makeList(in) public static returns List
lst = ArrayList()
loop while in > ''
parse in val ',' in
lst.add(val.strip())
end
return lst
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method main(args = String[]) public static
runSample(Rexx(args))
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method isTrue() public static returns boolean
return (1 == 1)
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method isFalse() public static returns boolean
return (1 == 0)
</lang>
{{out}}
<pre>
[UK London, US New York, US Boston, US Washington UK Washington, US Birmingham, UK Birmingham, UK Boston]
[UK Birmingham, UK Boston, UK London, US Birmingham, US Boston, US New York, US Washington UK Washington]
This permutation sort of 7 elements took 4221 passes (of 5040) to complete. Elapsed time: 0.361959s.
[Alpha, Beta, Gamma, Beta]
[Alpha, Beta, Beta, Gamma]
This permutation sort of 4 elements took 2 passes (of 24) to complete. Elapsed time: 0.000113s.
[7, 6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7]
This permutation sort of 7 elements took 5040 passes (of 5040) to complete. Elapsed time: 0.267956s.
[734, 3, 1, 24, 324, -1024, -666, -1, 0, 324, 99999999]
[-1024, -666, -1, 0, 1, 3, 24, 324, 324, 734, 99999999]
This permutation sort of 11 elements took 20186793 passes (of 39916800) to complete. Elapsed time: 141.461863s.
</pre>
=={{header|Nim}}==
Line 1,015 ⟶ 1,000:
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|OCaml}}==
Like the Haskell version, except not evaluated lazily. So it always computes all the permutations, before searching through them for a sorted one; which is more expensive than necessary; unlike the Haskell version, which stops generating at the first sorted permutation.
<lang ocaml>let rec sorted = function
| e1 :: e2 :: r -> e1 <= e2 && sorted (e2 :: r)
| _ -> true
let rec insert e = function
| [] -> [[e]]
| h :: t as l -> (e :: l) :: List.map (fun t' -> h :: t') (insert e t)
let permute xs = List.fold_right (fun h z -> List.concat (List.map (insert h) z))
xs [[]]
let permutation_sort l = List.find sorted (permute l)</lang>
=={{header|PARI/GP}}==
| |||