Permutations/Derangements: Difference between revisions

{{trans|Python}}

[[Int]] r

V perm = Array(0 .< n)

n = 20

{{out}}

{{trans|BBC BASIC}}

Due to 32 bit integers !12 is the limit.

DERANGE CSECT

USING DERANGE,R13 base register

PG DC CL80' ' buffer

YREGS

{{out}}

<pre>

=={{header|Ada}}==

{{trans|C}}

procedure DePermute is

type U64 is mod 2**64;

end loop;

Put_Line ("!20 = " & U64'Image (sub_fact (20)));

{{out}}

<pre>Deranged 4:

=={{header|Arturo}}==

loop.with:'i s 'a [

if a = o\[i] -> return false

]

{{out}}

{{works with|AutoHotkey_L}}

Note that the permutations are generated in lexicographic order, from http://www.autohotkey.com/forum/topic77959.html

SetBatchLines -1

Process, Priority,, high

a *= A_Index

return a

{{out}}

<pre>Derangements for 1, 2, 3, 4:

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

{{works with|BBC BASIC for Windows}}

Count% = FN_Derangement_Generate(4,TRUE)

REM Or you could use:

{{out}}

Also the counter <code>count</code> is a global variable.

= memo answ

. (memo==)

& out$("!20 =" calculated-!n$20)

& lst$calculated-!n

{{out}}

<pre>Derangements of 1 2 3 4

=={{header|C}}==

typedef unsigned long long LONG;

return 0;

{{out}}

<pre>Deranged Four:

Recursive version

using System;

class Derangements

}

}

=={{header|Clojure}}==

Generating functions with no fixed point

(:require [clojure.set :as s]))

(range 10)))

(println (subfactorial 20))))

{{Out}}

<pre>[1 0 3 2]

=={{header|D}}==

===Iterative Version===

std.range, std.traits;

writefln("\n!20 = %s", 20L.subfact);

{{out}}

<pre>Derangements for n = 4:

Slightly slower but more compact recursive version of the derangements function, based on the [[Permutations#D|D entry]] of the permutations task.

Same output.

T factorial(T)(in T n) pure nothrow {

writefln("\n!20 = %s", 20L.subfact);

=={{header|EchoLisp}}==

(lib 'list) ;; in-permutations

(lib 'bigint)

(remember '!n #(1 0))

{{out}}

(derangements 4)

→ ((3 0 1 2) (2 0 3 1) (2 3 0 1) (3 2 0 1) (3 2 1 0) (2 3 1 0) (1 2 3 0) (1 3 0 2) (1 0 3 2))

(!n 20)

→ 895014631192902121

=={{header|Elixir}}==

{{trans|Ruby}}

def derangements(n) do

list = Enum.to_list(1..n)

Enum.each(10..20, fn n ->

:io.format "~2w :~19w~n", [n, Permutation.subfact(n)]

{{out}}

=={{header|F_Sharp|F#}}==

===The Function===

// Generate derangements. Nigel Galloway: July 9th., 2019

let derange n=

|_->()}

derange 0 [|1..n|] (n-1)

===The Task===

derange 4 |> Seq.iter(printfn "%A")

{{out}}

<pre>

[|4; 1; 2; 3|]

</pre>

let subFact n=let rec fN n g=match n with 0m->int64(round(g/2.7182818284590452353602874713526624978m))|_->fN (n-1m) (g*n) in if n=0 then 1L else fN (decimal n) 1m

[1..9] |> Seq.iter(fun n->printfn "items=%d !n=%d derangements=%d" n (subFact n) (derange n|>Seq.length))

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.98}}

prettyprint sequences ;

IN: rosetta-code.derangements

"%d%8d%8d\n" printf

] each nl

{{out}}

<pre>

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>permutations derangements for n = 4

=={{header|GAP}}==

Derangements([1 .. 4]);

# [ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ], [ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ],

# [ 7, 1854, 1854, 1854 ],

# [ 8, 14833, 14833, 14833 ],

=={{header|Go}}==

import (

// stretch (sic)

fmt.Println("\n!20 =", subFact(20))

{{out}}

<pre>

=={{header|Groovy}}==

Solution:

def subfact

subfact = { BigInteger n -> (n == 0) ? 1 : (n == 1) ? 0 : ((n-1) * (subfact(n-1) + subfact(n-2))) }

if (l) l.eachPermutation { p -> if ([p,l].transpose().every{ pp, ll -> pp != ll }) d << p }

d

Test:

assert d.size() == subfact(4)

d.each { println it }

println """

!20 == ${subfact(20)}

{{out}}

=={{header|Haskell}}==

import Data.List (permutations)

putStrLn ""

-- Print the number of derangements in a list of 20 items

{{Out}}

<pre>[[4,3,2,1],[3,4,2,1],[2,3,4,1],[4,1,2,3],[2,4,1,3],[2,1,4,3],[4,3,1,2],[3,4,1,2],[3,1,4,2]]

Alternatively, this is a backtracking method:

where loop [] [] = [[]]

Since the value <i>i</I> cannot occur in position <i>i</i>, we prefix <i>i</i> on all other derangements from 1 to <i>n</i> that do not include <i>i</i>. The first method of filtering permutations is significantly faster, in practice, however.

Note: <code>!n</code> in J denotes factorial (or gamma n+1), and not subfactorial.

Requested examples:

1 0 3 2

1 2 3 0

8.95015e17

subfactorial 20x NB. using extended precision

Note that derangement 10 was painfully slow (almost 3 seconds, about 10 times slower than derangement 9 and 100 times slower than derangement 8) -- this is a brute force approach. But brute force seems like an appropriate solution here, since factorial divided by subfactorial asymptotically approaches a value near 0.367879 (the reciprocal of e).

=={{header|Java}}==

{{trans|D}}

import java.util.Arrays;

import java.util.List;

return r;

}

<pre>derangements for n = 4

{{works with|jq|1.4}}

The following implementation of "derangements" generates the derangements directly, without generating all permutations. Since recent versions of jq have tail-call optimization (TCO) for arity-0 recursive functions, the workhorse inner function (deranged/0) is implemented as an arity-0 function.

# In order to reference the original array conveniently, define _derangements(ary):

# Avoid creating an array just to count the items in a stream:

'''Tasks''':

([range(1;5)] | derangements),

"",

(range(1;10) as $i | "\($i): \(count( [range(0;$i)] | derangements)) vs \($i|subfact)"),

"",

{{Out}}

jq -n -c -r -f derangements.jq

9: 133496 vs 133496

=={{header|Julia}}==

derangements(n::Int) = (perm for perm in permutations(1:n)

end

{{out}}

=={{header|Kotlin}}==

fun <T> permute(input: List<T>): List<List<T>> {

}

println("\n!20 = ${subFactorial(20)}")

{{out}}

=={{header|Lua}}==

function permute (list)

local function perm (list, n)

print("\t| " .. #derangements(listOneTo(i)))

end

{{out}}

<pre>Derangements of [1,2,3,4]

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Needs["Combinatorica`"]

derangements[n_] := Derangements[Range[n]]

derangements[4]

Table[{NumberOfDerangements[i], Subfactorial[i]}, {i, 9}] // TableForm

{{out}}

<pre>

=={{header|Nim}}==

iterator derangements[T](a: openArray[T]): seq[T] =

echo &"{n} {toSeq(derangements(toSeq(1..n))).len:>6} {!n:>6}"

{{out}}

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

derange(n)={

my(v=[[]],tmp);

derange(4)

for(n=0,9,print("!"n" = "#derange(n)" = "derangements(n)))

{{out}}

<pre>%1 = [[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2], [4, 3, 2, 1]]

=={{header|Pascal}}==

program Derangements_RC;

(*

WriteLn( 'Subfactorial(20) = ', Subfactorial(20));

end.

{{out}}

<pre>

=={{header|Perl}}==

===Traditional verbose version===

# compare this with the deranged() sub to see how to turn procedural

# code into functional one ('functional' as not in 'understandable')

print "\nNumber of derangements:\n";

{{out}}

===Using a module===

{{libheader|ntheory}}

# Count derangements using derangement iterator

printf "\n%3s %15s %15s\n","N","List count","!N";

printf "%3d %15d %15d %15d\n",$_,countderange($_),subfactorial1($_),subfactorial2($_) for 0..9;

{{out}}

<pre>

=={{header|Phix}}==

{{libheader|Phix/mpfr}}

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

<span style="color: #008080;">function</span> <span style="color: #000000;">deranged</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"!20=%s (mpfr)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">mpz_sub_factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)})</span>

{{out}}

<pre>

A more efficient method of calculating subfactorials (0 should be handled separately, or obviously prepend a 1 and extract with idx+1).<br>

Should you instead of string results want an array of mpz for further calculations, use the mpz_init_set() call as shown:

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

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">subfactorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>{"0","1","2","9","44","265","1854","14833","133496","895014631192902121"}</pre>

=={{header|Picat}}==

go =>

'!!'(N) = subfactorial(N).

{{out}}

=={{header|PicoLisp}}==

(de derangements (Lst)

(*

(dec N)

{{out}}

<pre>: (derangements (range 1 4))

=={{header|PureBasic}}==

Brute Force

Procedure.q Subfactoral(n)

If n=0:ProcedureReturn 1:EndIf

DeleteFile(tempFile.s)

Return

{{out}}

{{trans|C}}

Protected count, tmp, i

If depth = lenn

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

CloseConsole()

{{out}}

=={{header|Python}}==

Includes stretch goal.

import math

n = 20

{{out}}

{{trans|FreeBASIC}}

Error "Subscript out of scope" for n > 7

FUNCTION permsderange (n!, flag!)

IF n = 0 THEN permsderange = 1

FOR i = 0 TO 7

PRINT USING " ###: ######## ########"; i; permsderange(i, 1); subfac(i)

=={{header|Quackery}}==

[ stack ] is deranges.num ( --> [ )

i^ sub! echo cr ]

cr

{{out}}

=={{header|Racket}}==

#lang racket

(sub-fact 20)

;; -> 895014631192902121

=={{header|Raku}}==

Although not necessary for this task, I have used <code>eqv</code> instead of <code>==</code> so that the <code>derangements()</code> function also works with any set of arbitrary objects (eg. strings, lists, etc.)

@l.permutations.grep(-> @p { none(@p Zeqv @l) })

}

for 0 .. 9 -> $n {

say "!$n == { !$n } == { derangements(^$n).elems }"

{{out}}

<pre>

=={{header|REXX}}==

numeric digits 1000 /*be able to handle large subfactorials*/

parse arg N .; if N=='' | N=="," then N=4 /*Not specified? Then use the default.*/

if i==0 then return 0

do m=i+1 while @.m<@.i; end /*m*/ /* [↓] swap two values. */

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

<pre>

=={{header|Ruby}}==

ary = (1 .. n).to_a

ary.permutation.select do |perm|

(10..20).each do |n|

puts "#{n} : #{subfact(n)}"

{{out}}

=={{header|Scala}}==

{{trans|Ruby}}

(1 to n).permutations.filter(_.zipWithIndex.forall{case (a, b) => a - b != 1})

println("\n%2s%10s%10s".format("n", "derange", "subfact"))

(0 to 9).foreach(n => println("%2d%10d%10d".format(n, derangements(n).size, subfactorial(n))))

{{out}}

<pre>Derangements for n = 4

=={{header|SuperCollider}}==

d = { |array, n|

Routine {

x = f.(4);

x.all.do(_.postln); "";

Answers:

[ 3, 2, 1, 0 ]

[ 2, 3, 0, 1 ]

[ 2, 3, 1, 0 ]

[ 3, 0, 1, 2 ]

z = { |n|

case

"% % %\n".postf(i, p.(derangements.size), p.(subfactorial));

};

Answers:

n derangements subfactorial

0 1 1

8 14833 14833

9 133496 133496

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list; # for permutation enumerator

}

return $s

Demonstrating with the display parts of the task:

puts "derangement of 1..4: $d"

}

# Stretch goal

{{out}}

<pre>

{{libheader|Wren-fmt}}

{{libheader|Wren-big}}

import "/big" for BigInt

Fmt.print("$d $-9d $-9i", n, counted, subFactorial.call(n))

}

{{out}}

=={{header|zkl}}==

{{trans|Python}} mostly

if(n==0) return(1);

if(n==1) return(0);

sum + (perm.zipWith('==,enum).sum(0) == 0)

},0);

println("\nTable of n vs counted vs calculated derangements:");

foreach n in (10){

}

{{out}}

<pre>

</pre>

Lazy/iterators version:

enum:=[0..n-1].pump(List);

Utils.Helpers.permuteW(enum).tweak('wrap(perm){

fcn derangers(n){ // just count # of derangements, w/o saving them

derangements(n).reduce('+.fpM("10-",1),0); // ignore perm --> '+(1,sum)...