Sorting algorithms/Permutation sort: Difference between revisions

<br><br>

=={{header|11l}}==

L(i) 1..arr.len-1

I arr[i-1] > arr[i]

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

permutation_sort(&arr)

 

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program permutationSort64.s */

.include "../includeARM64.inc"

 

<pre>

Value : -5

 

=={{header|ActionScript}}==

function permutations(front:Array, permutable:Array):Array {

//If permutable has length 1, there is only one possible permutation. Check whether it's sorted

function permutationSort(array:Array):Array {

return permutations([],array);

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program permutationSort.s */

/***************************************************/

.include "../affichage.inc"

 

=={{header|Arturo}}==

 

previous: first arr

 

]

 

 

{{out}}

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/post-276680.html#276680 discussion]

MsgBox % PermSort("xxx")

MsgBox % PermSort("3,2,1")

While i < j

t := %v%%i%, %v%%i% := %v%%j%, %v%%j% := t, ++i, --j

 

=={{header|BBC BASIC}}==

test() = 4, 65, 2, 31, 0, 99, 2, 83, 782, 1

IF d(I%) < d(I%-1) THEN = FALSE

NEXT

{{out}}

<pre>

=={{header|C}}==

Just keep generating [[wp:Permutation#Systematic_generation_of_all_permutations|next lexicographic permutation]] until the last one; it's sorted by definition.

#include <stdlib.h>

#include <string.h>

printf("%s\n", strs[i]);

return 0;

 

=={{header|C sharp|C#}}==

public static class PermutationSorter

{

}

}

 

=={{header|C++}}==

Since <tt>next_permutation</tt> already returns whether the resulting sequence is sorted, the code is quite simple:

 

 

template<typename ForwardIterator>

// -- this block intentionally left empty --

}

 

=={{header|Clojure}}==

 

(use '[clojure.contrib.combinatorics :only (permutations)])

 

 

(permutation-sort [2 3 5 3 5])

 

=={{header|CoffeeScript}}==

# optimizes one part of it. Permutations are computed lazily.

 

console.log 'DONE!'

console.log 'sorted copy:', ans

{{out}}

> coffee permute_sort.coffee

input: [ 'c', 'b', 'a', 'd' ]

DONE!

sorted copy: [ 'a', 'b', 'c', 'd' ]

 

=={{header|Common Lisp}}==

The <code>nth-permutation</code> function is some classic algorithm from Wikipedia.

 

(loop for result = 1 then (* i result)

for i from 2 to n

for permutation = (nth-permutation i sequence)

when (sortedp fn permutation)

 

Evaluation took:

5.292 seconds of real time

611,094,240 bytes consed

 

=={{header|Crystal}}==

prev = items[0]

items.each do |item|

end

end

 

=={{header|D}}==

===Basic Version===

This uses the second (lazy) permutations from the Permutations Task.

 

void permutationSort(T)(T[] items) pure nothrow @safe @nogc {

data.permutationSort;

data.writeln;

{{out}}

<pre>[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>

===Alternative Version===

{{trans|C++}}

 

void permutationSort(T)(T[] items) pure nothrow @safe @nogc {

data.permutationSort;

data.writeln;

The output is the same.

Run-time about 1.04 seconds with ldc2 (the C++ entry with G++ takes about 0.4 seconds).

{{trans|C++}}

 

def temp := container[ixA]

container[ixA] := container[ixB]

def permutationSort(flexList) {

while (nextPermutation(flexList)) {}

 

=={{header|EchoLisp}}==

;; This efficient sort method uses the list library for permutations

 

 

→ (0 1 2 3 4 5)

 

=={{header|Elixir}}==

def permutation_sort([]), do: []

def permutation_sort(list) do

 

IO.inspect list = for _ <- 1..9, do: :rand.uniform(20)

 

{{out}}

[18, 2, 19, 10, 17, 10, 14, 8, 3]

[2, 3, 8, 10, 10, 14, 17, 18, 19]

</pre>

 

=={{header|Factor}}==

IN: rosetta-code.permutation-sort

 

{ 10 2 6 8 1 4 3 } permutation-sort .

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted array

=={{header|Go}}==

Not following the pseudocode, it seemed simpler to just test sorted at the bottom of a recursive permutation generator.

 

import "fmt"

}

return false

 

=={{header|Groovy}}==

 

I believe that this method of constructing permutations results in a stable sort, but I have not actually proven that assertion.

 

def makePermutation;

def pIndex = (0..<fact).find { print "."; sorted(permuteA(it)) }

permuteA(pIndex)

 

Test:

println ()

println permutationSort([10, 10.0, 10.00, 1])

println permutationSort([10.0, 10.00, 10, 1])

println permutationSort([10.00, 10, 10.0, 1])

The examples with distinct integer and decimal values that compare as equal are there to demonstrate, but not to prove, that the sort is stable.

 

 

=={{header|Haskell}}==

 

permutationSort l = head [p | p <- permute l, sorted p]

insert e [] = return [e]

insert e l@(h : t) = return (e : l) `mplus`

{{works with|GHC|6.10}}

 

permutationSort l = head [p | p <- permutations l, sorted p]

 

sorted (e1 : e2 : r) = e1 <= e2 && sorted (e2 : r)

 

=={{header|Icon}} and {{header|Unicon}}==

Partly from [http://infohost.nmt.edu/tcc/help/lang/icon/backtrack.html here]

if i >= n then

return l

l := [6,3,4,5,1]

|( l := permute(l) & sorted(l)) \1 & every writes(" ",!l)

 

=={{header|J}}==

{{eff note|J|/:~}}

A function to locate the permuation index, in the naive manner prescribed by the task:

Of course, this can be calculated much more directly (and efficiently):

Either way:

ps list

(A.~ps) list

 

=={{header|Java}}==

import java.util.ArrayList;

import java.util.Arrays;

arr[j]=temp;

}

 

{{out}}

'''Infrastructure''':

The following function generates a stream of permutations of an arbitrary JSON array:

if length == 0 then []

else

| ($in|del(.[$i])|permutations)

| [$in[$i]] + .

 

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.

def until(cond; next):

def _until: if cond then . else (next|_until) end;

else . as $in

| 1 | until( . == $length or $in[.-1] > $in[.] ; .+1) == $length

 

'''Permutation-sort''':

 

{{works with|jq|1.4}}

 

{{works with|jq|with foreach}}

# emit the first item in stream that satisfies the condition

def first(stream; cond):

if .[0] then break $out else [($item | cond), $item] end;

if .[0] then .[1] else empty end );

 

'''Example''':

{{out}}

 

=={{header|Julia}}==

 

using Combinatorics

 

x = randn(10)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun <T : Comparable<T>> isSorted(list: List<T>): Boolean {

val output2 = permutationSort(input2)

println("After sorting : $output2")

 

{{out}}

 

=={{header|Lua}}==

function permute (list)

local function perm (list, n)

list = nextPermutation() --/ for p in permute(list) do

end --/ stuffWith(p)

{{out}}

<pre>1 2 3</pre>

 

=={{header|Maple}}==

len := numelems(arr):

P := Iterator:-Permute(len):

break:

end if:

{{Out|Output}}

<pre>[-1,0,0,17,72]</pre>

Here is a one-line solution.

A custom order relation can be defined for the OrderedQ[] function.

 

=={{header|MATLAB}} / {{header|Octave}}==

 

 

permutations = perms(1:numel(list)); %Generate all permutations of the item indicies

end

 

 

Sample Usage:

 

ans =

 

 

=={{header|MAXScript}}==

(

if arr.count < 2 then return true

)

)

Output:

a = for i in 1 to 9 collect random 1 20

#(10, 20, 17, 15, 17, 15, 3, 11, 15)

permutations a

#(3, 10, 11, 15, 15, 15, 17, 17, 20)

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.

options replace format comments java crossref symbols nobinary

 

method isFalse() public static returns boolean

return (1 == 0)

{{out}}

<pre>

 

=={{header|Nim}}==

var

d = 1

 

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

{{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.

| e1 :: e2 :: r -> e1 <= e2 && sorted (e2 :: r)

| _ -> true

xs [[]]

 

 

=={{header|PARI/GP}}==

my(u);

for(k=1,(#v)!,

return(u)

)

 

=={{header|Perl}}==

Pass a list in by reference, and sort in situ.

my ($x, $d) = @_;

 

print "Before:\t@a\n";

psort(\@a);

 

{{out}}

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">permutationSort</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"dog"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15.545</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"cat"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"pile"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"abcde"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #008000;">"cat"</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

 

=={{header|PHP}}==

for($i=0;$i<count($arr);$i++){

if(isset($arr[$i+1])){

$arr = array( 8, 3, 10, 6, 1, 9, 7, 2, 5, 4);

$arr = permute($arr);

<pre>1,2,3,4,5,6,7,8,9,10</pre>

 

=={{header|PicoLisp}}==

(let L Lst

(recur (L) # Permute

(rot L)

NIL )

{{out}}

<pre>: (permutationSort (make (do 9 (link (rand 1 999)))))

 

=={{header|PowerShell}}==

{

$data = $indata.Clone()

}

}

 

=={{header|Prolog}}==

 

sorted([]).

 

permutation([],[]).

 

=={{header|PureBasic}}==

first = firstIndex

last = lastIndex

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

{{out}}

<pre>8, 3, 10, 6, 1, 9, 7, -4, 5, 3

=={{header|Python}}==

{{works with|Python|2.6}}

 

in_order = lambda s: all(x <= s[i+1] for i,x in enumerate(s[:-1]))

 

<br/>

 

{{works with|Python|3.7}}

from more_itertools import windowed

 

if is_sorted(permutation)

)

 

=={{header|Quackery}}==

 

 

[ [] unrot 1 - times

[ over size

factoradic inversion ] is nperm ( [ n --> [ )

[ true swap

behead swap

unrot 2drop ] is sort ( [ --> [ )

 

 

{{out}}

{{libheader|e1071}}

Warning: This function keeps all the possible permutations in memory at once, which becomes silly when x has 10 or more elements.

{

if(!require(e1071) stop("the package e1071 is required")

x

}

 

===RcppAlgos===

{{libheader|RcppAlgos}}

RcppAlgos lets us do this at the speed of C++ and with some very short code. The while loop with no body strikes me as poor taste, but I know of no better way.

permuSort <- function(list)

{

test <- sample(10)

print(test)

{{out}}

<pre>#Output

 

An alternative solution would be to replace the while loop with the following:

{

if(!is.unsorted(iter$nextIter())) break

This seems more explicit than the empty while loop, but also more complex.

 

=={{header|Racket}}==

 

#lang racket

(define (sort l)

(for/first ([p (in-permutations l)] #:when (apply <= p)) p))

(sort '(6 1 5 2 4 3)) ; => '(1 2 3 4 5 6)

 

=={{header|Raku}}==

(formerly Perl 6)

sub next_perm ( @a ) {

my $j = @a.end - 1;

say 'Input = ' ~ @data;

say 'Output = ' ~ @data.&permutation_sort;

 

{{out}}

 

=={{header|REXX}}==

call gen /*generate the array elements. */

call show 'before sort' /*show the before array elements. */

do ?=1 until isOrd($); $= /*find permutation.*/

do m=1 for #; _= word(#.?, m); $= $ @._; end /*m*/ /*build the $ list.*/

{{out|output|text=&nbsp; when using the default (internal) inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Sorting algorithms/Permutation sort

 

ok

return a

Output:

<pre>

{{works with|Ruby|1.8.7+}}

The Array class has a permutation method that, with no arguments, returns an enumerable object.

def permutationsort

permutation.each{|perm| return perm if perm.sorted?}

each_cons(2).all? {|a, b| a <= b}

end

 

=={{header|Scheme}}==

(if (null? list)

(cons (cons e list) list)

(if (sorted? (car permutations))

(car permutations)

 

=={{header|Sidef}}==

{{trans|Perl}}

 

if (d.is_zero) {

say "Before:\t#{a}";

psort(a);

{{out}}

<pre>

{{tcllib|struct::list}}

The <code>firstperm</code> procedure actually returns the lexicographically first permutation of the input list. However, to meet the letter of the problem, let's loop:

package require struct::list

 

}

return $list

 

=={{header|Ursala}}==

Standard library functions to generate permutations and test for ordering by a

given predicate are used.

 

permsort "p" = ~&ihB+ ordered"p"*~+ permutations

#cast %sL

 

 

{{out}}

{{trans|Go}}

{{libheader|Wren-sort}}

 

var a = [170, 45, 75, -90, -802, 24, 2, 66]

a[i] = a[last]

a[last] = t

if (recurse.call(last - 1)) return true

t = a[i]

var count = a.count

if (count > 1 && !recurse.call(count-1)) Fiber.abort("Sorted permutation not found!")

 

{{out}}

=={{header|zkl}}==

Performance is horrid

fcn psort(list){ len:=list.len(); cnt:=Ref(0);

foreach ns in (Utils.Helpers.permuteW(list)){ // lasy permutations

if(cnt.value==len) return(ns);

}

{{out}}

<pre>L(0,1,2,2,4,31,65,83,99,782)</pre>