Sorting algorithms/Permutation sort: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
(rearranges in order of the language.) |
||
Line 231: | Line 231: | ||
} |
} |
||
</lang> |
</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}}== |
=={{header|Clojure}}== |
||
Line 379: | Line 393: | ||
(1 2 3 4 5 6 7 8 9 10)</lang> |
(1 2 3 4 5 6 7 8 9 10)</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|D}}== |
=={{header|D}}== |
||
Line 655: | Line 655: | ||
|( l := permute(l) & sorted(l)) \1 & every writes(" ",!l) |
|( l := permute(l) & sorted(l)) \1 & every writes(" ",!l) |
||
end</lang> |
end</lang> |
||
=={{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|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|J}}== |
=={{header|J}}== |
||
Line 973: | Line 852: | ||
</lang> |
</lang> |
||
Warning: This algorithm is very inefficient and Max will crash very quickly with bigger arrays. |
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}}== |
=={{header|Nim}}== |
||
Line 1,015: | Line 1,000: | ||
{{out}} |
{{out}} |
||
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre> |
<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}}== |
=={{header|PARI/GP}}== |