Sorting algorithms/Permutation sort: Difference between revisions

 

Pseudocode:

nextPermutation(list)

'''done'''

 

=={{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|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|C}}==

#include <string.h>

 

 

{

 

 

 

}

 

 

{

 

 

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

public static class PermutationSorter

{

}

}

 

=={{header|Clojure}}==

 

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

 

 

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

 

=={{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|D}}==

 

 

 

 

}

 

void main() {

auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1];

 

=={{header|E}}==

{{trans|C++}}

 

def temp := container[ixA]

container[ixA] := container[ixB]

def permutationSort(flexList) {

while (nextPermutation(flexList)) {}

 

=={{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)

 

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

 

 

 

 

 

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

end

 

 

Sample Usage:

 

ans =

 

 

 

 

 

 

}

 

 

 

=={{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 )

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

-> (82 120 160 168 205 226 408 708 719)

 

=={{header|PowerShell}}==

{

$data = $indata.Clone()

}

}

 

=={{header|Prolog}}==

 

sorted([]).

 

permutation([],[]).

=={{header|PureBasic}}==

first = firstIndex

last = lastIndex

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

CloseConsole()

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

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

=={{header|Python}}==

{{works with|Python|2.6}}

 

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

 

=={{header|R}}==

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

}

 

=={{header|Ruby}}==

{{works with|Ruby|1.8.7+}}

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

def permutationsort

end

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|Tcl}}==

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

 

 

<pre><'dwj','ejw','hhp','oao','ock','oqh','pmf'></pre>