Permutations: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Tailspin}}: add omitted line) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 14:
=={{header|11l}}==
<
L
print(a)
I !a.next_permutation()
L.break</
{{out}}
Line 32:
=={{header|360 Assembly}}==
{{trans|Liberty BASIC}}
<
PERMUTE CSECT
USING PERMUTE,R15 set base register
Line 92:
PG DC CL80' ' buffer
YREGS
END PERMUTE</
{{out}}
<pre style="height:40ex;overflow:scroll">
Line 123:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program permutation64.s */
Line 275:
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value : +1
Line 304:
</pre>
=={{header|ABAP}}==
<
lv_number type i,
lt_numbers type table of i.
Line 403:
modify iv_set index lv_perm from lv_temp_2.
modify iv_set index lv_len from lv_temp.
endform.</
{{out}}
<pre>
Line 418:
=={{header|Action!}}==
<
BYTE i
Line 477:
RMARGIN=oldRMARGIN ;restore right margin on the screen
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Permutations.png Screenshot from Atari 8-bit computer]
Line 509:
===The generic package Generic_Perm===
When given N, this package defines the Element and Permutation types and exports procedures to set a permutation P to the first one, and to change P into the next one:
<
N: positive;
package Generic_Perm is
Line 517:
procedure Set_To_First(P: out Permutation; Is_Last: out Boolean);
procedure Go_To_Next(P: in out Permutation; Is_Last: out Boolean);
end Generic_Perm;</
Here is the implementation of the package:
<
Line 590:
end Go_To_Next;
end Generic_Perm;</
===The procedure Print_Perms===
<
procedure Print_Perms is
Line 622:
when Constraint_Error
=> TIO.Put_Line ("*** Error: enter one numerical argument n with n >= 1");
end Print_Perms;</
{{out}}
Line 635:
=={{header|Aime}}==
<
f1(record r, ...)
{
Line 658:
0;
}</
{{Out}}
<pre>aime permutations -a Aaa Bb C
Line 672:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.6 algol68g-2.6].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
'''File: prelude_permutations.a68'''<
COMMENT REQUIRED BY "prelude_permutations.a68"
Line 704:
);
SKIP</
# -*- coding: utf-8 -*- #
Line 727:
# OD #))
)</
<pre>
(1, 22, 333, 44444)
Line 757:
=={{header|Amazing Hopper}}==
{{trans|AWK}}
<syntaxhighlight lang="amazing hopper">
/* hopper-JAMBO - a flavour of Amazing Hopper! */
Line 793:
Set(c), [ leng ] Cput(lista)
Return
</syntaxhighlight>
{{out}}
<pre>
Line 806:
=={{header|APL}}==
For Dyalog APL(assumes index origin ⎕IO←1):
<syntaxhighlight lang="apl">
⍝ Builtin version, takes a vector:
⎕CY'dfns'
Line 814:
dpmat←{1=⍵:,⊂,0 ⋄ (⊃,/)¨(⍳⍵)⌽¨⊂(⊂(!⍵-1)⍴⍵-1),⍨∇⍵-1}
perms2←{↓⍵[1+⍉↑dpmat ≢⍵]}
</syntaxhighlight>
<pre>
Line 833:
Recursively, in terms of concatMap and delete:
<
-- permutations :: [a] -> [[a]]
Line 919:
missing value
end if
end uncons</
{{Out}}
<pre>{{"aardvarks", "eat", "ants"}, {"aardvarks", "ants", "eat"},
Line 927:
{{trans|Pseudocode}}
(Fast recursive Heap's algorithm)
<
--> Heaps's algorithm (Permutation by interchanging pairs)
if n = 1 then
Line 968:
DoPermutations(SourceList, SourceList's length)
--> result (value of Permlist)
{"123", "213", "312", "132", "231", "321"}</
===Non-recursive===
As a right fold (which turns out to be significantly faster than recurse + delete):
<
-- permutations :: [a] -> [[a]]
Line 1,104:
{}
end if
end take</
{{Out}}
<pre>{{1, 2, 3}, {2, 1, 3}, {2, 3, 1}, {1, 3, 2}, {3, 1, 2}, {3, 2, 1}}</pre>
Line 1,113:
This is marginally faster even than the Pseudocode translation above and doesn't demarcate lists with square brackets, which don't officially exist in AppleScript. It now features tail call elimination and a rethink of way the results list is built which, on my machine, reduces the time taken to return the 362,880 permutations of a 9-item list from a minute to a second and a half. It'll even return the 3,628,800 permutations of a 10-item list without seizing up, in about 17 seconds. But make sure Script Editor doesn't attempt to display such large results or you'll need to force-quit it!
<
-- found in Robert Sedgewick's PDF document "Permutation Generation Methods"
-- <https://www.cs.princeton.edu/~rs/talks/perms.pdf>
Line 1,212:
end allPermutations
return allPermutations({1, 2, "cat", "dog"})</
{{output}}
<
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program permutation.s */
Line 1,363:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
Value : +1
Line 1,392:
</pre>
=={{header|Arturo}}==
<
{{out}}
<pre>[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]</pre>
Line 1,398:
=={{header|AutoHotkey}}==
from the forum topic http://www.autohotkey.com/forum/viewtopic.php?t=77959
<
StringCaseSense On
Line 1,446:
o := A_LoopField o
return o
}</
{{out}}
<pre style="height:40ex;overflow:scroll">Hello
Line 1,511:
===Alternate Version===
Alternate version to produce numerical permutations of combinations.
<
;1..n = range, or delimited list, or string to parse
; to process with a different min index, pass a delimited list, e.g. "0`n1`n2"
Line 1,543:
. P(n,k-1,opt,delim,str . A_LoopField . delim)
Return s
}</
{{out}}
<syntaxhighlight lang
<pre style="height:40ex;overflow:scroll">---------------------------
permute.ahk
Line 1,558:
OK
---------------------------</pre>
<
<pre style="height:40ex;overflow:scroll">---------------------------
permute.ahk
Line 1,607:
OK
---------------------------</pre>
<
<pre style="height:40ex;overflow:scroll">---------------------------
permute.ahk
Line 1,635:
OK
---------------------------</pre>
<
<pre style="height:40ex;overflow:scroll">---------------------------
permute.ahk
Line 1,704:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f PERMUTATIONS.AWK [-v sep=x] [word]
#
Line 1,751:
arr[leng-1] = c
}
</syntaxhighlight>
<p>sample command:</p>
GAWK -f PERMUTATIONS.AWK Gwen
Line 1,761:
=={{header|BASIC256}}==
{{trans|Liberty BASIC}}
<
n = 4 : cont = 0
dim a(n)
Line 1,803:
end if
until i = 0
end</
=={{header|Batch File}}==
Recursive permutation generator.
<syntaxhighlight lang="batch file">
@echo off
setlocal enabledelayedexpansion
Line 1,841:
endlocal & set %3=%arr%
exit /b
</syntaxhighlight>
{{out}}
<pre>
Line 1,872:
=={{header|BBC BASIC}}==
The procedure PROC_NextPermutation() will give the next lexicographic permutation of an integer array.
<
List%() = 1, 2, 3, 4
FOR perm% = 1 TO 24
Line 1,909:
last -= 1
ENDWHILE
ENDPROC</
'''Output:'''
<pre>
Line 1,939:
=={{header|Bracmat}}==
<
= prefix List result original A Z
. !arg:(?.)
Line 1,951:
& !result
)
& out$(perm$(.a 2 "]" u+z);</
Output:
<pre> (a 2 ] u+z.)
Line 1,981:
===version 1===
Non-recursive algorithm to generate all permutations. It prints objects in lexicographical order.
<syntaxhighlight lang="c">
#include <stdio.h>
int main (int argc, char *argv[]) {
Line 2,036:
}
}
</syntaxhighlight>
===version 2===
Non-recursive algorithm to generate all permutations. It prints them from right to left.
<syntaxhighlight lang="c">
#include <stdio.h>
Line 2,066:
}
</syntaxhighlight>
===version 3===
See [[wp:Permutation#Systematic_generation_of_all_permutations|lexicographic generation]] of permutations.
<
#include <stdlib.h>
Line 2,170:
return 0;
}
</syntaxhighlight>
===version 4===
See [[wp:Permutation#Systematic_generation_of_all_permutations|lexicographic generation]] of permutations.
<
#include <stdlib.h>
Line 2,274:
return 0;
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
Recursive Linq
{{works with|C sharp|C#|7}}
<
{
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> values) where T : IComparable<T>
Line 2,287:
return values.SelectMany(v => Permutations(values.Where(x => x.CompareTo(v) != 0)), (v, p) => p.Prepend(v));
}
}</
Usage
<
A recursive Iterator. Runs under C#2 (VS2005), i.e. no `var`, no lambdas,...
<
{
public static System.Collections.Generic.IEnumerable<T[]> AllFor(T[] array)
Line 2,321:
}
}
}</
Usage:
<
{
class Program
Line 2,336:
}
}
}</
Line 2,342:
Recursive version
<
class Permutations
{
Line 2,369:
}
}
}</
Alternate recursive version
<
using System;
class Permutations
Line 2,400:
}
}
</syntaxhighlight>
=={{header|C++}}==
The C++ standard library provides for this in the form of <code>std::next_permutation</code> and <code>std::prev_permutation</code>.
<
#include <string>
#include <vector>
Line 2,443:
return 0;
}</
{{out}}
<pre>
Line 2,523:
In an REPL:
<
user=> (require 'clojure.contrib.combinatorics)
nil
user=> (clojure.contrib.combinatorics/permutations [1 2 3])
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))</
===Explicit===
Replacing the call to the combinatorics library function by its real implementation.
<
(defn- iter-perm [v]
(let [len (count v),
Line 2,568:
(println (permutations [1 2 3]))
</syntaxhighlight>
=={{header|CoffeeScript}}==
<
# removed from it.
arrayExcept = (arr, idx) ->
Line 2,588:
# Flatten the array before returning it.
[].concat permutations...</
This implementation utilises the fact that the permutations of an array could be defined recursively, with the fixed point being the permutations of an empty array.
{{out|Usage}}
<
1,2,3
1,3,2
Line 2,597:
2,3,1
3,1,2
3,2,1</
=={{header|Common Lisp}}==
<
(if list
(mapcan #'(lambda (x)
Line 2,608:
'(()))) ; else
(print (permute '(A B Z)))</
{{out}}
<pre>((A B Z) (A Z B) (B A Z) (B Z A) (Z A B) (Z B A))</pre>
Lexicographic next permutation:
<
(declare (type (simple-array * (*)) vec))
(macrolet ((el (i) `(aref vec ,i))
Line 2,629:
;;; test code
(loop for a = "1234" then (next-perm a #'char<) while a do
(write-line a))</
Recursive implementation of Heap's algorithm:
<
(let ((permutations nil))
(labels ((permute (seq k)
Line 2,644:
(permute seq (1- k)))))))
(permute seq (length seq))
permutations)))</
=={{header|Crystal}}==
<
{{out}}
<pre>[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]</pre>
Line 2,653:
=={{header|Curry}}==
<
insert :: a -> [a] -> [a]
insert x xs = x : xs
Line 2,661:
permutation [] = []
permutation (x:xs) = insert x $ permutation xs
</syntaxhighlight>
=={{header|D}}==
===Simple Eager version===
Compile with -version=permutations1_main to see the output.
<
T[][] result;
Line 2,686:
writefln("%(%s\n%)", [1, 2, 3].permutations);
}
}</
{{out}}
<pre>[1, 2, 3]
Line 2,697:
===Fast Lazy Version===
Compiled with <code>-version=permutations2_main</code> produces its output.
<
struct Permutations(bool doCopy=true, T) if (isMutable!T) {
Line 2,784:
[B(1), B(2), B(3)].permutations!false.writeln;
}
}</
===Standard Version===
<
import std.stdio, std.algorithm;
Line 2,794:
items.writeln;
while (items.nextPermutation);
}</
=={{header|Delphi}}==
<
{$APPTYPE CONSOLE}
Line 2,854:
if Length(S) > 0 then Writeln(S);
Readln;
end.</
{{out}}
<pre>
Line 2,868:
(2) Return the next permutation in lexicographic order, or set a flag to indicate there are no more permutations.
The algorithm for (2) is the same as in the Wikipedia article "Permutation".
<
[Permutations task for Rosetta Code.]
[EDSAC program, Initial Orders 2.]
Line 3,076:
PF [enter with acc = 0]
[end]
</syntaxhighlight>
{{out}}
<pre>
Line 3,092:
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 3,141:
end
</syntaxhighlight>
{{out}}
<pre>
Line 3,154:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def permute([]), do: [[]]
def permute(list) do
Line 3,161:
end
IO.inspect RC.permute([1, 2, 3])</
{{out}}
Line 3,170:
=={{header|Erlang}}==
Shortest form:
<
-export([permute/1]).
permute([]) -> [[]];
permute(L) -> [[X|Y] || X<-L, Y<-permute(L--[X])].</
Y-combinator (for shell):
<
More efficient zipper implementation:
<
-export([permute/1]).
Line 3,195:
prepend(_, [], T, R, Acc) -> zipper(T, R, Acc); % continue in zipper
prepend(X, [H|T], ZT, ZR, Acc) -> prepend(X, T, ZT, ZR, [[X|H]|Acc]).</
Demonstration (escript):
<
{{out}}
<pre>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]</pre>
Line 3,203:
=={{header|Euphoria}}==
{{trans|PureBasic}}
<
object x
while first < last do
Line 3,250:
end if
puts(1, s & '\t')
end while</
{{out}}
<pre>abcd abdc acbd acdb adbc adcb bacd badc bcad bcda
Line 3,257:
=={{header|F Sharp|F#}}==
<
let rec insert left x right = seq {
match right with
Line 3,278:
|> Seq.iter (fun x -> printf "%A\n" x)
0
</syntaxhighlight>
<pre>
Line 3,291:
Translation of Haskell "insertion-based approach" (last version)
<
let permutations xs =
let rec insert x = function
Line 3,297:
| head :: tail -> (x :: (head :: tail)) :: (List.map (fun l -> head :: l) (insert x tail))
List.fold (fun s e -> List.collect (insert e) s) [[]] xs
</syntaxhighlight>
=={{header|Factor}}==
Line 3,303:
=={{header|Fortran}}==
<
implicit none
Line 3,335:
end subroutine generate
end program permutations</
{{out}}
<pre> 1 2 3
Line 3,349:
The values need to be "swapped back" after the recursive call.
<
implicit none
integer :: n, i
Line 3,375:
end if
end subroutine
end program</
Line 3,383:
Here below is the speed test for a couple of algorithms of permutation. We can add more algorithms into this frame-work. When they work in the same circumstance, we can see which is the fastest one.
<
implicit none
Line 3,743:
!=====
end program</
An example of performance:
Line 3,798:
Here is an alternate, iterative version in Fortran 77.
{{trans|Ada}}
<
integer n,i,a
logical nextp
Line 3,838:
a(j)=t
nextp=.true.
end</
=== Ratfor 77 ===
Line 3,844:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 3,895:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>1234 2134 3124 1324 2314 3214 4213 2413 1423 4123 2143 1243
Line 3,902:
=={{header|Frink}}==
Frink's array class has built-in methods <CODE>permute[]</CODE> and <CODE>lexicographicPermute[]</CODE> which permute the elements of an array in reflected Gray code order and lexicographic order respectively.
<
println[formatTable[a.lexicographicPermute[]]]</
{{out}}
Line 3,936:
compute the images of 1 .. n by p. As an alternative, List(SymmetricGroup(n)) would yield the permutations as GAP ''Permutation'' objects,
which would probably be more manageable in later computations.
<
perms(4);
[ [ 1, 2, 3, 4 ], [ 4, 2, 3, 1 ], [ 2, 4, 3, 1 ], [ 3, 2, 4, 1 ], [ 1, 4, 3, 2 ], [ 4, 1, 3, 2 ], [ 2, 1, 3, 4 ],
[ 3, 1, 4, 2 ], [ 1, 3, 4, 2 ], [ 4, 3, 1, 2 ], [ 2, 3, 1, 4 ], [ 3, 4, 1, 2 ], [ 1, 2, 4, 3 ], [ 4, 2, 1, 3 ],
[ 2, 4, 1, 3 ], [ 3, 2, 1, 4 ], [ 1, 4, 2, 3 ], [ 4, 1, 2, 3 ], [ 2, 1, 4, 3 ], [ 3, 1, 2, 4 ], [ 1, 3, 2, 4 ],
[ 4, 3, 2, 1 ], [ 2, 3, 4, 1 ], [ 3, 4, 2, 1 ] ]</
GAP has also built-in functions to get permutations
<
Arrangements([1 .. 4], 4);
# All permutations of 1 .. 4
PermutationsList([1 .. 4]);</
Here is an implementation using a function to compute next permutation in lexicographic order:
<
local i, j, k, n, t;
n := Length(a);
Line 3,991:
[ [ 1, 2, 3 ], [ 1, 3, 2 ],
[ 2, 1, 3 ], [ 2, 3, 1 ],
[ 3, 1, 2 ], [ 3, 2, 1 ] ]</
=={{header|Glee}}==
<
$$ #s monadic: number of elements in s
$$ ,, monadic: expose with space-lf separators
Line 4,000:
'Hello' 123 7.9 '•'=>s;
s[s# !! (s#)],,</
Result:
<
Hello 123 • 7.9
Hello 7.9 123 •
Line 4,026:
• 123 7.9 Hello
• 7.9 Hello 123
• 7.9 123 Hello</
=={{header|GNU make}}==
Line 4,032:
Recursive on unique elements
<
#delimiter should not occur inside elements
delimiter=;
Line 4,046:
delimiter_separated_output=$(call permutations,a b c d)
$(info $(delimiter_separated_output))
</syntaxhighlight>
{{out}}
Line 4,055:
=== recursive ===
<
import "fmt"
Line 4,106:
}
rc(len(s))
}</
{{out}}
<pre>[1 2 3]
Line 4,117:
=== non-recursive, lexicographical order ===
<
import "fmt"
Line 4,145:
fmt.Println(a)
}
}</
{{out}}
Line 4,158:
=={{header|Groovy}}==
Solution:
<
Test:
<
def permutations = makePermutations(list)
assert permutations.size() == (1..<(list.size()+1)).inject(1) { prod, i -> prod*i }
permutations.each { println it }</
{{out}}
<pre style="height:30ex;overflow:scroll;">[Young, Crosby, Stills, Nash]
Line 4,192:
=={{header|Haskell}}==
<
main = mapM_ print (permutations [1,2,3])</
A simple implementation, that assumes elements are unique and support equality:
<
permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ x:ys | x <- xs, ys <- permutations (delete x xs)]</
A slightly more efficient implementation that doesn't have the above restrictions:
<
permutations [] = [[]]
permutations xs = [ y:zs | (y,ys) <- select xs, zs <- permutations ys]
where select [] = []
select (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- select xs ]</
The above are all selection-based approaches. The following is an insertion-based approach:
<
permutations = foldr (concatMap . insertEverywhere) [[]]
where insertEverywhere :: a -> [a] -> [[a]]
insertEverywhere x [] = [[x]]
insertEverywhere x l@(y:ys) = (x:l) : map (y:) (insertEverywhere x ys)</
A serialized version:
{{Trans|Mathematica}}
<
permutations :: [a] -> [[a]]
Line 4,232:
main :: IO ()
main = print $ permutations [1, 2, 3]</
{{Out}}
<pre>[[1,2,3],[2,3,1],[3,1,2],[2,1,3],[1,3,2],[3,2,1]]</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
every p := permute(A) do every writes((!p||" ")|"\n")
end
Line 4,244:
if *A <= 1 then return A
suspend [(A[1]<->A[i := 1 to *A])] ||| permute(A[2:0])
end</
{{out}}
<pre>->permute Aardvarks eat ants
Line 4,256:
=={{header|IS-BASIC}}==
<
110 LET N=4 ! Number of elements
120 NUMERIC T(1 TO N)
Line 4,281:
330 NEXT
340 END IF
350 END DEF</
=={{header|J}}==
<
{{out|Example use}}
<
0 1
1 0
Line 4,295:
random text some
text some random
text random some</
=={{header|Java}}==
Using the code of Michael Gilleland.
<
private int[] array;
private int firstNum;
Line 4,381:
}
} // class</
{{out}}
<pre>
Line 4,394:
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]]
<
public static void main(String[] args) {
System.out.println(Utils.Permutations(Utils.mRange(1, 3)));
}
}</
{{out}}
<pre>[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]</pre>
Line 4,407:
Copy the following as an HTML file and load in a browser.
<
<body><pre id="result"></pre>
<script type="text/javascript">
Line 4,429:
perm([1, 2, 'A', 4], []);
</script></body></html></
Alternatively: 'Genuine' js code, assuming no duplicate.
<syntaxhighlight lang="javascript">
function perm(a) {
if (a.length < 2) return [a];
Line 4,446:
console.log(perm(['Aardvarks', 'eat', 'ants']).join("\n"));
</syntaxhighlight>
{{Out}}
<
Aardvarks,ants,eat
eat,Aardvarks,ants
eat,ants,Aardvarks
ants,Aardvarks,eat
ants,eat,Aardvarks</
====Functional composition====
Line 4,462:
(Simple version – assuming a unique list of objects comparable by the JS === operator)
<
'use strict';
Line 4,496:
// TEST
return permutations(['Aardvarks', 'eat', 'ants']);
})();</
{{Out}}
<
["eat", "Aardvarks", "ants"], ["eat", "ants", "Aardvarks"],
["ants", "Aardvarks", "eat"], ["ants", "eat", "Aardvarks"]]</
===ES6===
Recursively, in terms of concatMap and delete:
<
'use strict';
Line 4,543:
permutations(['Aardvarks', 'eat', 'ants'])
);
})();</
{{Out}}
<
["eat", "Aardvarks", "ants"], ["eat", "ants", "Aardvarks"],
["ants", "Aardvarks", "eat"], ["ants", "eat", "Aardvarks"]]</
Or, without recursion, in terms of concatMap and reduce:
<
'use strict';
Line 4,592:
permutations([1, 2, 3])
);
})();</
{{Out}}
<pre>[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]</pre>
Line 4,598:
=={{header|jq}}==
"permutations" generates a stream of the permutations of the input array.
<
if length == 0 then []
else
Line 4,604:
| [.[$i]] + (del(.[$i])|permutations)
end ;
</syntaxhighlight>
'''Example 1''': list them
[range(0;3)] | permutations
Line 4,631:
=={{header|Julia}}==
<syntaxhighlight lang="julia">
julia> perms(l) = isempty(l) ? [l] : [[x; y] for x in l for y in perms(setdiff(l, x))]
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="julia">
julia> perms([1,2,3])
6-element Vector{Vector{Int64}}:
Line 4,644:
[3, 1, 2]
[3, 2, 1]
</syntaxhighlight>
Further support for permutation creation and processing is available in the <tt>Combinatorics.jl</tt> package.
<tt>permutations(v)</tt> creates an iterator over all permutations of <tt>v</tt>. Julia 0.7 and 1.0+ require the line global i inside the for to update the i variable.
<syntaxhighlight lang="julia">
using Combinatorics
Line 4,663:
end
println()
</syntaxhighlight>
{{out}}
Line 4,680:
</pre>
<syntaxhighlight lang="text">
# Generate all permutations of size t from an array a with possibly duplicated elements.
collect(Combinatorics.multiset_permutations([1,1,0,0,0],3))
</syntaxhighlight>
{{out}}
<pre>
Line 4,698:
=={{header|K}}==
{{trans|J}}
<
perm 2
(0 1
Line 4,709:
random text some
text some random
text random some</
Alternative:
<syntaxhighlight lang="k">
perm:{x@m@&n=(#?:)'m:!n#n:#x}
Line 4,738:
text some random
text random some
</syntaxhighlight>
=={{header|Kotlin}}==
Translation of C# recursive 'insert' solution in Wikipedia article on Permutations:
<
fun <T> permute(input: List<T>): List<List<T>> {
Line 4,763:
println("There are ${perms.size} permutations of $input, namely:\n")
for (perm in perms) println(perm)
}</
{{out}}
Line 4,797:
=={{header|Lambdatalk}}==
<
{def inject
{lambda {:x :a}
Line 4,823:
->
[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[1,3,2,4],[3,1,2,4],[3,2,1,4],[3,2,4,1],[1,3,4,2],[3,1,4,2],[3,4,1,2],[3,4,2,1],[1,2,4,3],[2,1,4,3],[2,4,1,3],[2,4,3,1],[1,4,2,3],[4,1,2,3],[4,2,1,3],[4,2,3,1],[1,4,3,2],[4,1,3,2],[4,3,1,2],[4,3,2,1]]
</syntaxhighlight>
And this is an illustration of the way lambdatalk builds an interface for javascript functions (the first one is given in this page):
<
1) permutations on sentences
Line 4,898:
321
</syntaxhighlight>
=={{header|langur}}==
Line 4,907:
Prior to 0.10, multi-variable declaration/assignment would use parentheses around variable names and values. 0.10 also parses the increment section of a for loop as a multi-variable assignment, not as a list of assignments.
<
val .permute = f(.arr) {
Line 4,945:
for .e in .permute([1, 3.14, 7]) {
writeln .e
}</
{{out}}
Line 4,957:
=={{header|LFE}}==
<
(defun permute
(('())
Line 4,965:
(<- y (permute (-- l `(,x)))))
(cons x y))))
</syntaxhighlight>
REPL usage:
<
> (permute '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
</syntaxhighlight>
=={{header|Liberty BASIC}}==
Permuting numerical array (non-recursive):
{{trans|PowerBASIC}}
<syntaxhighlight lang="lb">
n=3
dim a(n+1) '+1 needed due to bug in LB that checks loop condition
Line 5,004:
end if
loop until i=0
</syntaxhighlight>
{{out}}
Line 5,016:
</pre>
Permuting string (recursive):
<syntaxhighlight lang="lb">
n = 3
Line 5,037:
End Function
</syntaxhighlight>
{{out}}
Line 5,050:
=={{header|Lobster}}==
<syntaxhighlight lang="lobster">
// Lobster implementation of the (very fast) Go example
// http://rosettacode.org/wiki/Permutations#Go
Line 5,183:
permi(se): print(_)
</syntaxhighlight>
{{out}}
<pre>
Line 5,289:
=={{header|Logtalk}}==
<
:- public(permutation/2).
Line 5,310:
select(Head, Tail, Tail2).
:- end_object.</
{{out|Usage example}}
<
[1,2,3]
Line 5,320:
[3,1,2]
[3,2,1]
yes</
=={{header|Lua}}==
<
local function permutation(a, n, cb)
if n == 0 then
Line 5,342:
end
permutation({1,2,3}, 3, callback)
</syntaxhighlight>
{{out}}
<pre>
Line 5,353:
</pre>
<
-- Iterative version
Line 5,386:
ipermutations(3, 3)
</syntaxhighlight>
<pre>
Line 5,398:
=== fast, iterative with coroutine to use as a generator ===
<
#!/usr/bin/env luajit
-- Iterative version
Line 5,440:
print(table.concat(p, " "))
end
</syntaxhighlight>
{{out}}
Line 5,455:
=={{header|M2000 Interpreter}}==
===All permutations in one module===
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Global a$
Line 5,500:
}
Checkit
</syntaxhighlight>
===Step by step Generator===
<syntaxhighlight lang="m2000 interpreter">
Module StepByStep {
Function PermutationStep (a) {
Line 5,547:
StepByStep
</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
Line 5,617:
A peculiarity of this implementation is my use of arithmetic rather than branching to compute Sedgewick’s ‘k’. (I use arithmetic similarly in my Ratfor 77 implementation.)
<
# 1-based indexing of a string's characters.
Line 5,651:
divert`'dnl
permutations(`123')
permutations(`abcd')</
{{out}}
Line 5,689:
=={{header|Maple}}==
<
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
combinat:-permute([a,b,c]);
[[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]</
An implementation based on Mathematica solution:
<
insert:=(v,a,n)->`if`(n>nops(v),[op(v),a],subsop(n=(a,v[n]),v)):
perm:=s->fold((a,b)->map(u->seq(insert(u,b,k+1),k=0..nops(u)),a),[[]],s):
perm([$1..3]);
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Line 5,708:
===Version from scratch===
<syntaxhighlight lang="mathematica">
(***Standard list functions:*)
fold[f_, x_, {}] := x
Line 5,720:
Table[insert[L, #2, k + 1], {k, 0, Length[L]}]] /@ #1) &, {{}},
S]
</syntaxhighlight>
{{out}}
Line 5,731:
===Built-in version===
<
{{out}}
<pre>{{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2}, {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 3,
Line 5,738:
=={{header|MATLAB}} / {{header|Octave}}==
<
{{out}}
<pre>4321
Line 5,766:
=={{header|Maxima}}==
<
n: length(v), i: 0,
for k: n - 1 thru 1 step -1 do (if v[k] < v[k + 1] then (i: k, return())),
Line 5,789:
[2, 3, 1]
[3, 1, 2]
[3, 2, 1] */</
===Builtin version===
<
(%i1) permutations([1, 2, 3]);
(%o1) {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}
</syntaxhighlight>
=={{header|Mercury}}==
<
:- module permutations2.
:- interface.
Line 5,836:
nl(!IO),
print(all_permutations2([1,2,3,4]),!IO).
</syntaxhighlight>
{{out}}
Line 5,847:
=={{header|Microsoft Small Basic}}==
{{trans|vba}}
<
n=4
printem = "True"
Line 5,891:
p[j] = t
EndWhile
TextWindow.WriteLine("Number of permutations: "+count) </
{{out}}
<pre>
Line 5,923:
=={{header|Modula-2}}==
{{works with|ADW Modula-2 (1.6.291)}}
<
FROM Terminal
Line 5,982:
IF n > 0 THEN permute(n) END;
(*Wait*)
END Permute.</
=={{header|Modula-3}}==
Line 5,989:
This implementation merely prints out the orbit of the list (1, 2, ..., n) under the action of <i>S<sub>n</sub></i>. It shows off Modula-3's built-in <code>Set</code> type and uses the standard <code>IntSeq</code> library module.
<
IMPORT IO, IntSeq;
Line 6,046:
GeneratePermutations(chosen, values);
END Permutations.</
{{out}}
Line 6,067:
Suppose that <code>D</code> is the domain of elements to be permuted. This module requires a <code>DomainSeq</code> (<code>Sequence</code> of <code>D</code>), a <code>DomainSet</code> (<code>Set</code> of <code>D</code>), and a <code>DomainSeqSeq</code> (<code>Sequence</code> of <code>Sequence</code>s of <code>Domain</code>).
<
(*
Line 6,094:
*)
END GenericPermutations.</
;implementation
Line 6,100:
In addition to the interface's specifications, this requires a generic <code>Domain</code>. Some implementations of a set are not safe to iterate over while modifying (e.g., a tree), so this copies the values and iterates over them.
<
(*
Line 6,170:
BEGIN
END GenericPermutations.</
;Sample Usage
Line 6,176:
Here the domain is <code>Integer</code>, but the interface doesn't require that, so we "merely" need <code>IntSeq</code> (a <code>Sequence</code> of <code>Integer</code>), <code>IntSetTree</code> (a set type I use, but you could use <code>SetDef</code> or <code>SetList</code> if you prefer; I've tested it and it works), <code>IntSeqSeq</code> (a <code>Sequence</code> of <code>Sequence</code>s of <code>Integer</code>), and <code>IntPermutations</code>, which is <code>GenericPermutations</code> instantiated for <code>Integer</code>.
<
IMPORT IO, IntSeq, IntSetTree, IntSeqSeq, IntPermutations;
Line 6,218:
END;
END GPermutations.</
{{out}} (somewhat edited!)
Line 6,232:
=={{header|NetRexx}}==
<
options replace format comments java crossref symbols nobinary
Line 6,380:
end thing
return
</syntaxhighlight>
{{out}}
<pre style="height:55ex;overflow:scroll">
Line 6,428:
===Using the standard library===
<
var v = [1, 2, 3] # List has to start sorted
echo v
while v.nextPermutation():
echo v</
{{out}}
Line 6,445:
===Single yield iterator===
<
iterator inplacePermutations[T](xs: var seq[T]): var seq[T] =
assert xs.len <= 24, "permutation of array longer than 24 is not supported"
Line 6,469:
c[i] = int8(t)
i = t
</syntaxhighlight>
verification
<
import intsets
from math import fac
Line 6,503:
# check exactly l! unique number of permutations
assert len(s) == fac(l)
</syntaxhighlight>
===Translation of C===
{{trans|C}}
<
iterator permutations[T](ys: openarray[T]): seq[T] =
var
Line 6,533:
for i in permutations(x):
echo i</
Output:
<pre>@[1, 2, 3]
Line 6,544:
===Translation of Go===
{{trans|Go}}
<
# http://rosettacode.org/wiki/Permutations#Go
# implementing a recursive https://en.wikipedia.org/wiki/Steinhaus–Johnson–Trotter_algorithm
Line 6,576:
var se = @[0, 1, 2, 3] #, 4, 5, 6, 7, 8, 9, 10]
perm(se, proc(s: openArray[int])= echo s)</
=={{header|OCaml}}==
<
Translation of Ada version. *)
let next_perm p =
Line 6,623:
2 3 1
3 1 2
3 2 1 *)</
Permutations can also be defined on lists recursively:
<
let n = List.length l in
if n = 1 then [l] else
Line 6,639:
let print l = List.iter (Printf.printf " %d") l; print_newline() in
List.iter print (permutations [1;2;3;4])</
or permutations indexed independently:
<
let a, b = let c = k/n in c, k-(n*c) in
let e = List.nth l b in
Line 6,657:
done
let () = show_perms [1;2;3;4]</
=={{header|ooRexx}}==
Essentially derived fom the program shown under rexx.
This program works also with Regina (and other REXX implementations?)
<
/* REXX Compute bunch permutations of things elements */
Parse Arg bunch things
Line 6,748:
Say 'rexx perm 2 4 -> Permutations of 1 2 3 4 in 2 positions'
Say 'rexx perm 2 a b c d -> Permutations of a b c d in 2 positions'
Exit</
{{out}}
<pre>H:\>rexx perm 2 U V W X
Line 6,773:
=={{header|OpenEdge/Progress}}==
<syntaxhighlight lang="openedge/progress">
DEFINE VARIABLE charArray AS CHARACTER EXTENT 3 INITIAL ["A","B","C"].
DEFINE VARIABLE sizeofArray AS INTEGER.
Line 6,808:
charArray[a] = charArray[b].
charArray[b] = temp.
END PROCEDURE. </
{{out}}
<pre>ABC
Line 6,818:
=={{header|PARI/GP}}==
<
=={{header|Pascal}}==
<
var
Line 6,891:
next;
until is_last;
end.</
===alternative===
a little bit more speed.I take n = 12.
Line 6,897:
But you have to use the integers [1..n] directly or as Index to your data.
1 to n are in lexicographic order.
<
{$MODE DELPHI}
{$ELSE}
Line 6,967:
writeln(permcnt);
writeln(FormatDateTime('HH:NN:SS.zzz',T1-T0));
end.</
{{Out}}
{fpc 2.64/3.0 32Bit or 3.1 64 Bit i4330 3.5 Ghz same timings.
Line 6,976:
===Permutations from integers===
A console application in Free Pascal, created with the Lazarus IDE.
<
program Permutations;
(*
Line 7,096:
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Line 7,128:
=={{header|Perl}}==
A simple recursive implementation.
<
my ($perm,@set) = @_;
print "$perm\n" || return unless (@set);
Line 7,134:
}
my @input = (qw/a b c d/);
permutation('',@input);</
{{out}}
<pre>abcd
Line 7,163:
For better performance, use a module like <code>ntheory</code> or <code>Algorithm::Permute</code>.
{{libheader|ntheory}}
<
my @tasks = (qw/party sleep study/);
forperm {
print "@tasks[@_]\n";
} @tasks;</
{{out}}
<pre>
Line 7,179:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">permutes</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"abcd"</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"elements"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 7,191:
=={{header|Phixmonti}}==
<
def save
Line 7,214:
( ) >ps
( ) ( 1 2 3 4 ) permute
ps> sort print</
=={{header|Picat}}==
Line 7,223:
===Recursion===
Use <code>findall/2</code> to find all permutations. See example below.
<
permutation_rec1(Y,W),
select(X,Z,W).
Line 7,234:
append(L1, L2, H1),
append(L1, [T], X1),
append(X1, L2, X).</
===Constraint modelling===
Line 7,240:
<code>permutation_cp_list(L)</code> permutes a list via <code>permutation_cp2/1</code>.
<
% Returns all permutations
Line 7,257:
% Use the cp approach on a list L.
permutation_cp_list(L) = Perms =>
Perms = [ [L[I] : I in P] : P in permutation_cp1(L.len)].</
===Tests===
Here is a test of the different approaches, including the two built-ins.
<
main =>
N = 3,
Line 7,270:
println(permutation_cp1=permutation_cp1(N)),
println(permutation_cp2=findall(P,permutation_cp2(N,P))),
println(permutation_cp_list=permutation_cp_list("abc")).</
{{out}}
Line 7,283:
=={{header|PicoLisp}}==
<
(permute (1 2 3))</
{{out}}
<pre>-> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))</pre>
Line 7,291:
=={{header|PowerBASIC}}==
{{works with|PowerBASIC|10.00+}}
<
#DIM ALL
GLOBAL a, i, j, k, n AS INTEGER
Line 7,326:
END IF
LOOP UNTIL i = 0
END FUNCTION</
{{out}}
<pre>
Line 7,338:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function permutation ($array) {
function generate($n, $array, $A) {
Line 7,365:
}
permutation @('A','B','C')
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 7,378:
=={{header|Prolog}}==
Works with SWI-Prolog and library clpfd,
<
permut_clpfd(L, N) :-
Line 7,384:
L ins 1..N,
all_different(L),
label(L).</
{{out}}
<
[1,2,3]
[1,3,2]
Line 7,394:
[3,2,1]
false.
</syntaxhighlight>
A declarative way of fetching permutations:
<
% P is a permutation of L
Line 7,402:
permut_Prolog([H | T], NL) :-
select(H, NL, NL1),
permut_Prolog(T, NL1).</
{{out}}
<
[ab,cd,ef]
[ab,ef,cd]
Line 7,411:
[ef,ab,cd]
[ef,cd,ab]
false.</
{{Trans|Curry}}
<syntaxhighlight lang="prolog">
insert(X, L, [X|L]).
insert(X, [Y|Ys], [Y|L2]) :- insert(X, Ys, L2).
Line 7,419:
permutation([], []).
permutation([X|Xs], P) :- permutation(Xs, L), insert(X, L, P).
</syntaxhighlight>
{{Out}}
<pre>
Line 7,436:
The integer elements could be the addresses of objects that are pointed at instead. In this case the addresses will be permuted without respect to what they are pointing to (i.e. strings, or structures) and the lexicographic order will be that of the addresses themselves.
<
first = firstIndex
last = lastIndex
Line 7,492:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</
{{out}}
<pre>1, 2, 3
Line 7,505:
===Standard library function===
{{works with|Python|2.6+}}
<
for values in itertools.permutations([1,2,3]):
print (values)</
{{out}}
<pre>
Line 7,522:
The follwing functions start from a list [0 ... n-1] and exchange elements to always have a valid permutation. This is done recursively: first exchange a[0] with all the other elements, then a[1] with a[2] ... a[n-1], etc. thus yielding all permutations.
<
a = list(range(n))
def sub(i):
Line 7,547:
a[k - 1] = a[k]
a[n - 1] = x
yield from sub(0)</
These two solutions make use of a generator, and "yield from" introduced in [https://www.python.org/dev/peps/pep-0380/ PEP-380]. They are slightly different: the latter produces permutations in lexicographic order, because the "remaining" part of a (that is, a[i+1:]) is always sorted, whereas the former always reverses the exchange just after the recursive call.
Line 7,553:
On three elements, the difference can be seen on the last two permutations:
<
(0, 1, 2)
(0, 2, 1)
Line 7,567:
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)</
=== Iterative implementation ===
Line 7,573:
Given a permutation, one can easily compute the ''next'' permutation in some order, for example lexicographic order, here. Then to get all permutations, it's enough to start from [0, 1, ... n-1], and store the next permutation until [n-1, n-2, ... 0], which is the last in lexicographic order.
<
n = len(a)
i = n - 1
Line 7,611:
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)</
=== Implementation using destructive list updates ===
<
def permutations(xs):
ac = [[]]
Line 7,628:
print(permutations([1,2,3,4]))
</syntaxhighlight>
===Functional :: type-preserving===
Line 7,636:
{{Works with|Python|3.7}}
<
from functools import (reduce)
Line 7,721:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>[1, 2, 3] -> [[1,2,3],[2,3,1],[3,1,2],[2,1,3],[1,3,2],[3,2,1]]
Line 7,731:
{{works with|QuickBasic|4.5}}
{{trans|FreeBASIC}}
<
DIM a(0 TO n - 1), c(0 TO n - 1)
Line 7,761:
END SUB
perms(4)</
=={{header|Qi}}==
{{trans|Erlang}}
<syntaxhighlight lang="qi">
(define insert
L 0 E -> [E|L]
Line 7,784:
(insert P N H))
(seq 0 (length P))))
(permute T))))</
Line 7,792:
The word ''perms'' solves a more general task; generate permutations of between ''a'' and ''b'' items (inclusive) from the specified nest.
<
[ stack ] is perms.max ( --> [ )
Line 7,823:
' [ 1 2 3 ] permutations echo cr
$ "quack" permutations 60 wrap$
$ "quack" 3 4 perms 46 wrap$</
'''Output:'''
Line 7,894:
<code>nested join</code> adds a nest to the end of a nest as its last item.
<
[ [] i rot witheach
[ dup size 1+ times
Line 7,901:
unrot ] drop ] drop ] ] is perms ( n --> [ )
4 perms witheach [ echo cr ]</
{{out}}
Line 7,933:
=={{header|R}}==
===Iterative version===
<
n <- length(a)
i <- n
Line 7,967:
}
unname(e)
}</
'''Example'''
<syntaxhighlight lang="text">> perm(3)
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 1 2 2 3 3
[2,] 2 3 1 3 1 2
[3,] 3 2 3 1 2 1</
===Recursive version===
<
linsert <- function(x,s) lapply(0:length(s), function(k) append(s,x,k))
Line 7,989:
# permutations of a vector s
permutation <- function(s) lapply(perm(length(s)), function(i) s[i])
</syntaxhighlight>
Output:
<
[[1]]
[1] "c" "b" "a"
Line 8,009:
[[6]]
[1] "a" "b" "c"</
=={{header|Racket}}==
<
#lang racket
Line 8,073:
(next-perm (permuter))))))
;; -> (A B C)(A C B)(B A C)(B C A)(C A B)(C B A)
</syntaxhighlight>
=={{header|Raku}}==
Line 8,079:
{{works with|rakudo|2018.10}}
First, you can just use the built-in method on any list type.
<syntaxhighlight lang="raku"
{{out}}
<pre>a b c
Line 8,089:
Here is some generic code that works with any ordered type. To force lexicographic ordering, change <tt>after</tt> to <tt>gt</tt>. To force numeric order, replace it with <tt>></tt>.
<syntaxhighlight lang="raku"
my $j = @a.end - 1;
return Nil if --$j < 0 while @a[$j] after @a[$j+1];
Line 8,104:
}
.say for [<a b c>], &next_perm ...^ !*;</
{{out}}
<pre>a b c
Line 8,114:
</pre>
Here is another non-recursive implementation, which returns a lazy list. It also works with any type.
<syntaxhighlight lang="raku"
my @seq := 1..+@items;
gather for (^[*] @seq) -> $n is copy {
Line 8,126:
}
}
.say for permute( 'a'..'c' )</
{{out}}
<pre>(a b c)
Line 8,135:
(c b a)</pre>
Finally, if you just want zero-based numbers, you can call the built-in function:
<syntaxhighlight lang="raku"
{{out}}
<pre>0 1 2
Line 8,147:
For translation to FORTRAN 77 with the public domain ratfor77 preprocessor.
<
# Robert Sedgewick, 1977. Permutation generation methods. ACM
# Comput. Surv. 9, 2 (June 1977), 137-164.
Line 8,193:
}
end</
Here is what the generated FORTRAN 77 code looks like:
<
implicit none
integer a(1: 3)
Line 8,229:
endif
23005 continue
end</
{{out}}
Line 8,243:
This program could be simplified quite a bit if the "things" were just restricted to numbers (numerals),
<br>but that would make it specific to numbers and not "things" or objects.
<
parse arg things bunch inbetweenChars names /*obtain optional arguments from the CL*/
if things=='' | things=="," then things= 3 /*Not specified? Then use the default.*/
Line 8,281:
@.?= $.q; call .permSet ?+1
end /*q*/
return</
{{out|output|text= when the following was used for input: <tt> 3 3 </tt>}}
<pre>
Line 8,347:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 8,395:
last -= 1
end
</syntaxhighlight>
Output:
<pre>
Line 8,426:
=={{header|Ring}}==
<
Another Solution
Line 8,479:
</syntaxhighlight>
Output:
<pre>
Line 8,517:
=={{header|Ruby}}==
<
{{out}}
<pre>
Line 8,525:
=={{header|Run BASIC}}==
Works with Run BASIC, Liberty BASIC and Just BASIC
<
while word$(list$,d+1,",") <> "" 'Count how many in the list
Line 8,549:
next j
next i
end</
<pre>hello
ehllo
Line 8,572:
===Iterative===
Uses Heap's algorithm. An in-place version is possible but is incompatible with <code>Iterator</code>.
<
Permutations { idxs: (0..size).collect(), swaps: vec![0; size], i: 0 }
}
Line 8,611:
vec![2, 1, 0],
]);
}</
===Recursive===
<
fn permute<T, F: Fn(&[T])>(used: &mut Vec<T>, unused: &mut VecDeque<T>, action: &F) {
Line 8,631:
let mut queue = (1..4).collect::<VecDeque<_>>();
permute(&mut Vec::new(), &mut queue, &|perm| println!("{:?}", perm));
}</
=={{header|SAS}}==
<!-- oh god this code -->
<
data perm;
n=6;
Line 8,676:
return;
keep p1-p6;
run;</
=={{header|Scala}}==
There is a built-in function in the Scala collections library, that is part of the language's standard library. The permutation function is available on any sequential collection. It could be used as follows given a list of numbers:
<
{{out}}
Line 8,694:
The following function returns all the permutations of a list:
<
case Nil => List(Nil)
case xs => {
Line 8,704:
}
}
}</
If you need the unique permutations, use <code>distinct</code> or <code>toSet</code> on either the result or on the input.
Line 8,710:
=={{header|Scheme}}==
{{trans|Erlang}}
<
(if (= 0 n)
(cons e l)
Line 8,728:
(insert p n (car l)))
(seq 0 (length p))))
(permute (cdr l))))))</
{{trans|OCaml}}
<
(define (vector-swap! v i j)
(let ((tmp (vector-ref v i)))
Line 8,790:
; 1 2 0
; 2 0 1
; 2 1 0</
Completely recursive on lists:
<
(cond ((null? s) '())
((null? (cdr s)) (list s))
Line 8,802:
(splice (cons m l) (car r) (cdr r))))))))
(display (perm '(1 2 3)))</
=={{header|Seed7}}==
<
const type: permutations is array array integer;
Line 8,841:
writeln;
end for;
end func;</
{{out}}
<pre>
Line 8,853:
=={{header|Shen}}==
<syntaxhighlight lang="shen">
(define permute
[] -> []
Line 8,872:
(permute [a b c d])
</syntaxhighlight>
{{out}}
<pre>
Line 8,878:
</pre>
For lexical order, make a small change:
<syntaxhighlight lang="shen">
(define permute-helper
_ [] -> []
Done [X|Rest] -> (append (prepend-all X (permute (append Done Rest))) (permute-helper (append Done [X]) Rest))
)
</syntaxhighlight>
=={{header|Sidef}}==
===Built-in===
<
say p
}</
===Iterative===
<
var idx = @^n
Line 8,912:
}
forperm({|p| say p }, 3)</
===Recursive===
<
set.is_empty && callback(perm)
for i in ^set {
Line 8,925:
}
permutations({|p| say p }, [0,1,2])</
{{out}}
<pre>
Line 8,939:
{{works with|Squeak}}
{{works with|Pharo}}
<
Transcript show: x printString; cr ].</
{{works with|GNU Smalltalk}}
<
ArrayedCollection extend [
Line 8,970:
[:g |
c map permuteAndDo: [g yield: (c copyFrom: 1 to: c size)]]]
</syntaxhighlight>
Use example:
<syntaxhighlight lang="smalltalk">
st> 'Abc' permutations contents
('bcA' 'cbA' 'cAb' 'Acb' 'bAc' 'Abc' )
</syntaxhighlight>
=={{header|Stata}}==
Line 8,983:
For instance:
<syntaxhighlight lang
'''Program'''
<
local n=`1'
local r=1
Line 9,027:
} while (i > 1)
}
end</
=={{header|Swift}}==
<
return heaps(&ar, ar.count)
}
Line 9,044:
}
perms([1, 2, 3]) // [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]</
=={{header|Tailspin}}==
This solution seems to be the same as the Kotlin solution. Permutations flow independently without being collected until the end.
<
templates permutations
when <=1> do [1] !
Line 9,063:
def alpha: ['ABCD'...];
[ $alpha::length -> permutations -> '$alpha($)...;' ] -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 9,070:
If we collect all the permutations of the next size down, we can output permutations in lexical order
<
templates lexicalPermutations
when <=1> do [1] !
Line 9,082:
def alpha: ['ABCD'...];
[ $alpha::length -> lexicalPermutations -> '$alpha($)...;' ] -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 9,089:
That algorithm can also be written from the bottom up to produce an infinite stream of sets of larger and larger permutations, until we stop
<
templates lexicalPermutations2
def N: $;
Line 9,104:
def alpha: ['ABCD'...];
[ $alpha::length -> lexicalPermutations2 -> '$alpha($)...;' ] -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 9,111:
The solutions above create a lot of new arrays at various stages. We can also use mutable state and just emit a copy for each generated solution.
<
templates perms
templates findPerms
Line 9,130:
def alpha: ['ABCD'...];
[4 -> perms -> '$alpha($)...;' ] -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 9,138:
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
# Make the sequence of digits to be permuted
Line 9,147:
struct::list foreachperm p $sequence {
puts $p
}</
Testing with <code>tclsh listPerms.tcl 3</code> produces this output:
<pre>
Line 9,160:
=={{header|True BASIC}}==
{{trans|Liberty BASIC}}
<
LET temp = vb1
LET vb1 = vb2
Line 9,199:
END IF
LOOP UNTIL i = 0
END</
=={{header|Ursala}}==
In practice there's no need to write this because it's in the standard library.
<
permutations =
Line 9,211:
~&a, # insert the head at the first position
~&ar&& ~&arh2falrtPXPRD), # if the rest is non-empty, recursively insert at all subsequent positions
~&aNC) # no, return the singleton list of the argument</
test program:
<
test = permutations <1,2,3></
{{out}}
<pre><
Line 9,227:
=={{header|VBA}}==
{{trans|Pascal}}
<
'Generate, count and print (if printem is not false) all permutations of first n integers
Line 9,308:
Debug.Print "Number of permutations: "; count
End Sub</
{{out|Sample dialogue}}
<pre>
Line 9,349:
=={{header|VBScript}}==
A recursive implementation. Arrays can contain anything, I stayed with with simple variables. (Elements could be arrays but then the printing routine should be recursive...)
<syntaxhighlight lang="vb">
'permutation ,recursive
a=array("Hello",1,True,3.141592)
Line 9,374:
next
end sub
</syntaxhighlight>
Output
<pre>
Line 9,408:
===Recursive===
{{trans|Kotlin}}
<
permute = Fn.new { |input|
if (input.count == 1) return [input]
Line 9,426:
var perms = permute.call(input)
System.print("There are %(perms.count) permutations of %(input), namely:\n")
perms.each { |perm| System.print(perm) }</
{{out}}
Line 9,444:
{{libheader|Wren-math}}
Output modified to follow the pattern of the recursive version.
<
var input = [1, 2, 3]
Line 9,470:
}
System.print("There are %(perms.count) permutations of %(input), namely:\n")
perms.each { |perm| System.print(perm) }</
{{out}}
Line 9,486:
===Library based===
{{libheader|Wren-perm}}
<
var a = [1, 2, 3]
System.print(Perm.list(a)) // not lexicographic
System.print()
System.print(Perm.listLex(a)) // lexicographic</
{{out}}
Line 9,501:
=={{header|XPL0}}==
<
def N=4; \number of objects (letters)
char S0, S1(N);
Line 9,525:
[S0:= "rose "; \N different objects (letters)
Permute(0); \(space char avoids MSb termination)
]</
Output:
Line 9,557:
=={{header|Yabasic}}==
{{trans|Liberty BASIC}}
<
dim a(n), c(n)
Line 9,583:
endif
until i = 0
end</
=={{header|zkl}}==
Using the solution from task [[Permutations by swapping#zkl]]:
<
L("rose","roes","reos","eros","erso","reso","rseo","rsoe","sroe","sreo",...)
Line 9,594:
zkl: Utils.Helpers.permute(T(1,2,3,4))
L(L(1,2,3,4),L(1,2,4,3),L(1,4,2,3),L(4,1,2,3),L(4,1,3,2),L(1,4,3,2),L(1,3,4,2),L(1,3,2,4),...)</
|