Find the missing permutation: Difference between revisions
Added Easylang
(→{{header|Haskell}}: Plus an alternative, more statistical approach:) |
(Added Easylang) |
||
(80 intermediate revisions by 29 users not shown) | |||
Line 2:
<pre>
ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB
</pre>
Listed above are all-but-one of the permutations of the symbols '''A''', '''B''', '''C''', and '''D''', ''except'' for one permutation that's ''not'' listed.
Line 52 ⟶ 53:
* [[Permutations]])
<br><br>
=={{header|11l}}==
{{trans|C}}
<syntaxhighlight lang="11l">V perms = [‘ABCD’, ‘CABD’, ‘ACDB’, ‘DACB’, ‘BCDA’, ‘ACBD’, ‘ADCB’, ‘CDAB’,
‘DABC’, ‘BCAD’, ‘CADB’, ‘CDBA’, ‘CBAD’, ‘ABDC’, ‘ADBC’, ‘BDCA’,
‘DCBA’, ‘BACD’, ‘BADC’, ‘BDAC’, ‘CBDA’, ‘DBCA’, ‘DCAB’]
V missing = ‘’
L(i) 4
V cnt = [0] * 4
L(j) 0 .< perms.len
cnt[perms[j][i].code - ‘A’.code]++
L(j) 4
I cnt[j] != factorial(4-1)
missing ‘’= Char(code' ‘A’.code + j)
L.break
print(missing)</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
=={{header|360 Assembly}}==
{{trans|BBC BASIC}}
Very compact version, thanks to the clever [[#
<
PERMMISX CSECT
USING PERMMISX,R15 set base register
Line 84 ⟶ 109:
MISS DC 4XL1'00',C' is missing' buffer
YREGS
END PERMMISX</
{{out}}
<pre>DBAC is missing</pre>
=={{header|8080 Assembly}}==
<syntaxhighlight lang="asm">PRMLEN: equ 4 ; length of permutation string
puts: equ 9 ; CP/M print string
org 100h
lxi d,perms ; Start with first permutation
perm: lxi h,mperm ; Missing permutation
mvi b,PRMLEN ; Length of permutation
char: ldax d ; Load character
ora a ; Done?
jz done
xra m ; If not, XOR into missing permutation
mov m,a
inx h ; Increment pointers
inx d
dcr b ; Next character of current permutation
jnz char
jmp perm ; Next permutation
done: lxi d,msg ; Print the message and exit
mvi c,puts
jmp 5
msg: db 'Missing permutation: '
mperm: db 0,0,0,0,'$' ; placeholder
perms: db 'ABCD','CABD','ACDB','DACB','BCDA','ACBD','ADCB','CDAB'
db 'DABC','BCAD','CADB','CDBA','CBAD','ABDC','ADBC','BDCA'
db 'DCBA','BACD','BADC','BDAC','CBDA','DBCA','DCAB'
db 0 ; end marker </syntaxhighlight>
{{out}}
<pre>Missing permutation: DBAC</pre>
=={{header|8086 Assembly}}==
<syntaxhighlight lang="asm"> cpu 8086
org 100h
mov si,perms ; Start of permutations
xor bx,bx ; First word of permutation
xor dx,dx ; Second word of permutation
mov cx,23 ; There are 23 permutations given
perm: lodsw ; Load first word of permutation
xor bx,ax ; XOR with first word of missing
lodsw ; Load second word of permutation
xor dx,ax ; XOR with second word of missing
loop perm ; Get next permutation
mov [mperm],bx ; Store in placeholder
mov [mperm+2],dx
mov ah,9 ; Write output
mov dx,msg
int 21h
ret
msg: db 'Missing permutation: '
mperm: db 0,0,0,0,'$' ; Placeholder
perms: db 'ABCD','CABD','ACDB','DACB','BCDA','ACBD','ADCB','CDAB'
db 'DABC','BCAD','CADB','CDBA','CBAD','ABDC','ADBC','BDCA'
db 'DCBA','BACD','BADC','BDAC','CBDA','DBCA','DCAB'</syntaxhighlight>
{{out}}
<pre>Missing permutation: DBAC</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC Main()
DEFINE PTR="CARD"
DEFINE COUNT="23"
PTR ARRAY perm(COUNT)
CHAR ARRAY s,missing=[4 0 0 0 0]
BYTE i,j
perm(0)="ABCD" perm(1)="CABD"
perm(2)="ACDB" perm(3)="DACB"
perm(4)="BCDA" perm(5)="ACBD"
perm(6)="ADCB" perm(7)="CDAB"
perm(8)="DABC" perm(9)="BCAD"
perm(10)="CADB" perm(11)="CDBA"
perm(12)="CBAD" perm(13)="ABDC"
perm(14)="ADBC" perm(15)="BDCA"
perm(16)="DCBA" perm(17)="BACD"
perm(18)="BADC" perm(19)="BDAC"
perm(20)="CBDA" perm(21)="DBCA"
perm(22)="DCAB"
FOR i=0 TO COUNT-1
DO
s=perm(i)
FOR j=1 TO 4
DO
missing(j)==XOR s(j)
OD
OD
Print(missing)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Find_the_missing_permutation.png Screenshot from Atari 8-bit computer]
<pre>
DBAC
</pre>
=={{header|Ada}}==
<
procedure Missing_Permutations is
subtype Permutation_Character is Character range 'A' .. 'D';
Line 140 ⟶ 258:
Ada.Text_IO.Put_Line ("Missing Permutation:");
Put (Missing_Permutation);
end Missing_Permutations;</
=={{header|Aime}}==
<syntaxhighlight lang="aime">void
paste(record r, index x, text p, integer a)
{
p = insert(p, -1, a);
x.delete(a);
if (~x) {
x.vcall(paste, -1, r, x, p);
} else {
r[p] = 0;
}
x[a] = 0;
}
integer
main(void)
{
record r;
list l;
index x;
l.bill(0, "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB",
"CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB");
x['A'] = x['B'] = x['C'] = x['D'] = 0;
x.vcall(paste, -1, r, x, "");
l.ucall(r_delete, 1, r);
o_(r.low, "\n");
return 0;
}</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
=={{header|ALGOL 68}}==
Uses the XOR algorithm of the Raku sample.
<syntaxhighlight lang="algol68">BEGIN # find the missing permutation in a list using the XOR method of the Raku sample #
# the list to find the missing permutation of #
[]STRING list = ( "ABCD", "CABD", "ACDB", "DACB", "BCDA"
# sets b to b XOR v and returns b
PRIO XORAB =
OP XORAB = ( REF BITS b, BITS v )REF
# loop through each character of each element of the list #
FOR c pos FROM LWB list[ LWB list ] TO UPB list[ LWB list ] DO
# loop through each element of the list #
BITS m := 16r0;
FOR l pos FROM LWB list TO UPB list DO
m XORAB BIN ABS list[ l pos ][ c pos ]
OD;
print( ( REPR ABS m ) )
OD
END</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
=={{header|APL}}==
This is a function that takes a matrix where the rows are permutations,
and returns the missing permutation. It works by returning, for each column,
the letter that occurs least.
<syntaxhighlight lang="apl">missing ← ((⊂↓⍳¨⌊/) +⌿∘(⊢∘.=∪∘∊)) ⌷ ∪∘∊</syntaxhighlight>
{{out}}
<syntaxhighlight lang="apl"> perms←↑'ABCD' 'CABD' 'ACDB' 'DACB' 'BCDA' 'ACBD' 'ADCB' 'CDAB'
perms⍪←↑'DABC' 'BCAD' 'CADB' 'CDBA' 'CBAD' 'ABDC' 'ADBC' 'BDCA'
perms⍪←↑'DCBA' 'BACD' 'BADC' 'BDAC' 'CBDA' 'DBCA' 'DCAB'
missing perms
DBAC</syntaxhighlight>
=={{header|AppleScript}}==
{{Trans|JavaScript}}
{{Trans|Haskell}} (Statistical versions)
Taking the third approach from the task description, and composing with functional primitives:
Yosemite OS X onwards (uses NSString for sorting):
<syntaxhighlight lang="applescript">use framework "Foundation" -- ( sort )
--------------- RAREST LETTER IN EACH COLUMN -------------
on run
concat(map(composeList({¬
transpose(map(chars, ¬
"CBAD ABDC ADBC BDCA
"BADC BDAC CBDA DBCA DCAB")))))
--> "DBAC"
Line 229 ⟶ 368:
--------------------
-- chars :: String -> [String]
on chars(s)
characters of s
end chars
-- Ordering :: (-1 | 0 | 1)
-- compare :: a -> a -> Ordering
if a < b
else if a > b
else
end if
-- comparing :: (a -> b) -> (a -> a -> Ordering)
on comparing(f)
script
on |λ|(a, b)
tell mReturn(f) to compare(|λ|(a), |λ|(b))
end |λ|
end script
end comparing
--
on
script
on
script go
on
end
end script
end |λ|
end script
end
-- concat :: [[a]] -> [a]
-- concat :: [String] -> String
on concat(xs)
set lng to length of xs
if 0 < lng and string is class of (item 1 of xs) then
set acc to ""
else
set acc to {}
end if
repeat with i from 1 to lng
set acc to acc & item i of xs
end repeat
acc
end concat
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set
end repeat
return
end tell
end
-- foldr :: (b -> a -> a) -> a -> [b] -> a
on foldr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from
set v to
end repeat
return v
end tell
end
-- group :: Eq a => [a] -> [[a]]
on group(xs)
script eq
on |λ|(a, b)
a = b
end |λ|
end script
groupBy(eq, xs)
end group
-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
on groupBy(f, xs)
set mf to mReturn(f)
script enGroup
on |λ|(a, x)
if length of (active of a) > 0 then
set h to item 1 of active of a
else
set h to missing value
end if
if h is not missing value and mf's |λ|(h, x) then
{active:(active of a) & x, sofar:sofar of a}
else
{active:{x}, sofar:(sofar of a) & {active of a}}
end if
end |λ|
end script
if length of xs > 0 then
set dct to foldl(enGroup, {active:{item 1 of xs}, sofar:{}}, tail(xs))
if length of (active of dct) > 0 then
sofar of dct & {active of dct}
else
sofar of dct
end if
else
{}
end if
end groupBy
-- head :: [a] -> a
on head(xs)
if length of xs > 0 then
item 1 of xs
else
missing value
end if
end head
--
on
set {dlm, my text item delimiters} to {my text item delimiters,
set
set my text item delimiters to dlm
return
end
-- length :: [a] -> Int
on |length|(xs)
length of xs
end |length|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- minimumBy :: (a -> a -> Ordering) -> [a] -> a
on minimumBy(f)
script
on |λ|(xs)
if length of xs < 1 then return missing value
tell mReturn(f)
set v to item 1 of xs
repeat with x in xs
if |λ|(x, v) < 0 then set v to x
end repeat
return v
end tell
end |λ|
end script
end minimumBy
-- Lift 2nd class handler function into 1st class script wrapper
Line 307 ⟶ 563:
else
script
property
end script
end if
Line 313 ⟶ 569:
-- sort :: [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬
sortedArrayUsingSelector:"compare:") as list
end sort
--
on
items 2 thru -1 of xs
else
{}
end if
end tail
-- transpose :: [[a]] -> [[a]]
on transpose(xss)
script column
on |λ|(_, iCol)
script row
on |λ|(xs)
item iCol of xs
end |λ|
end script
map(row, xss)
end |λ|
end script
map(column, item 1 of xss)
end transpose
--
on
words of s
end |words|</syntaxhighlight>
{{Out}}
<pre>"DBAC"</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">perms: [
"ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC"
"BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD"
"BADC" "BDAC" "CBDA" "DBCA" "DCAB"
]
allPerms: map permutate split "ABCD" => join
print first difference allPerms perms</syntaxhighlight>
{{out}}
<pre>DBAC</pre>
=={{header|AutoHotkey}}==
<
CompleteList := Perm( "ABCD" )
Line 394 ⟶ 657:
}
return substr(L, 1, -1)
}</
=={{header|AWK}}==
Line 400 ⟶ 663:
This reads the list of permutations as standard input and outputs the missing one.
<
split($1,a,"");
for (i=1;i<=4;++i) {
Line 418 ⟶ 681:
}
print s[1]s[2]s[3]s[4]
}</
{{Out}}
Line 425 ⟶ 688:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \
\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \
Line 436 ⟶ 699:
NEXT
PRINT $$^miss&(0) " is missing"
END</
{{out}}
<pre>
Line 444 ⟶ 707:
=={{header|Burlesque}}==
<
ln"ABCD"r@\/\\
</syntaxhighlight>
(Feed permutations via STDIN. Uses the naive method).
Line 453 ⟶ 716:
the letters with the lowest frequency:
<
ln)XXtp)><)F:)<]u[/v\[
</syntaxhighlight>
=={{header|C}}==
<
#define N 4
Line 490 ⟶ 753:
return 0;
}</
{{out}}
<pre>Missing: DBAC</pre>
=={{header|C sharp|C#}}==
===By permutating===
{{works with|C sharp|C#|2+}}
<
using System.Collections.Generic;
Line 578 ⟶ 800:
}
}
}</
===By xor-ing the values===
{{works with|C sharp|C#|3+}}
<
using System.Linq;
Line 599 ⟶ 821:
Console.WriteLine(string.Join("", values.Select(i => (char)i)));
}
}</
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <algorithm>
#include <vector>
#include <set>
#include <iterator>
#include <iostream>
#include <string>
static const std::string GivenPermutations[] = {
"ABCD","CABD","ACDB","DACB",
"BCDA","ACBD","ADCB","CDAB",
"DABC","BCAD","CADB","CDBA",
"CBAD","ABDC","ADBC","BDCA",
"DCBA","BACD","BADC","BDAC",
"CBDA","DBCA","DCAB"
};
static const size_t NumGivenPermutations = sizeof(GivenPermutations) / sizeof(*GivenPermutations);
int main()
{
std::vector<std::string> permutations;
std::string initial = "ABCD";
permutations.push_back(initial);
while(true)
{
std::string p = permutations.back();
std::next_permutation(p.begin(), p.end());
if(p == permutations.front())
break;
permutations.push_back(p);
}
std::vector<std::string> missing;
std::set<std::string> given_permutations(GivenPermutations, GivenPermutations + NumGivenPermutations);
std::set_difference(permutations.begin(), permutations.end(), given_permutations.begin(),
given_permutations.end(), std::back_inserter(missing));
std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
return 0;
}</syntaxhighlight>
=={{header|Clojure}}==
<
(use 'clojure.math.combinatorics)
(use 'clojure.set)
Line 609 ⟶ 872:
(def s1 (apply hash-set (permutations "ABCD")))
(def missing (difference s1 given))
</syntaxhighlight>
Here's a version based on the hint in the description. ''freqs'' is a sequence of letter frequency maps, one for each column. There should be 6 of each letter in each column, so we look for the one with 5.
<
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA"
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"])
Line 619 ⟶ 882:
(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst))
(->> freqs (map #(v->k % 5)) (apply str) println)</
=={{header|CoffeeScript}}==
<
missing_permutation = (arr) ->
# Find the missing permutation in an array of N! - 1 permutations.
Line 659 ⟶ 922:
console.log missing_permutation(arr)
</syntaxhighlight>
{{out}}
Line 668 ⟶ 931:
=={{header|Common Lisp}}==
<
'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"))
Line 681 ⟶ 944:
(cons (count letter occurs) letter))
letters))))))
(concatenate 'string (mapcar #'least-occurs (enum (length letters)))))))</
{{out}}
<pre>ROSETTA> (missing-perm *permutations*)
Line 687 ⟶ 950:
=={{header|D}}==
<
import std.stdio, std.string, std.algorithm, std.range, std.conv;
Line 706 ⟶ 969:
// Version 2: xor all the ASCII values, the uneven one
// gets flushed out. Based on
enum len = 4;
char[len] b = 0;
Line 729 ⟶ 992:
perms[0][maxCode - code].write;
}
}</
{{out}}
<pre>DBAC
Line 735 ⟶ 998:
DBAC
DBAC</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Find_the_missing_permutation#Pascal Pascal].
=={{header|EasyLang}}==
<syntaxhighlight>
perms$[] = [ "ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB" ]
n = len perms$[1]
len cnt[] n
#
nn = 1
for i to n - 1
nn *= i
.
for i to 4
for j to n
cnt[j] = 0
.
for s$ in perms$[]
cod = strcode substr s$ i 1 - 64
cnt[cod] += 1
.
for j to n
if cnt[j] <> nn
miss$ &= strchar (j + 64)
break 1
.
.
.
print miss$
</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
=={{header|EchoLisp}}==
<
;; use the obvious methos
(lib 'list) ; for (permutations) function
Line 752 ⟶ 1,050:
(set-substract (make-set all-perms) (make-set perms))
→ { DBAC }
</syntaxhighlight>
=={{header|Elixir}}==
<
def find_miss_perm(head, perms) do
all_permutations(head) -- perms
Line 774 ⟶ 1,070:
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"]
IO.inspect RC.find_miss_perm( hd(perms), perms )</
{{out}}
Line 783 ⟶ 1,079:
=={{header|Erlang}}==
The obvious method. It seems fast enough (no waiting time).
<syntaxhighlight lang="erlang">
-module( find_missing_permutation ).
Line 800 ⟶ 1,096:
is_different( [_H] ) -> true;
is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ).
</syntaxhighlight>
{{out}}
<pre>
Line 808 ⟶ 1,104:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM MISSING
Line 842 ⟶ 1,138:
PRINT("Solution is: ";SOL$)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Solution is: DBAC
</pre>
=={{header|Factor}}==
Permutations are read in via STDIN.
<syntaxhighlight lang="factor">USING: io math.combinatorics sequences sets ;
"ABCD" all-permutations lines diff first print</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
Line 853 ⟶ 1,159:
'''Method:''' Read the permutations in as hexadecimal numbers, exclusive ORing them together gives the answer.
(This solution assumes that none of the permutations is defined as a Forth word.)
<
ABCD CABD xor ACDB xor DACB xor BCDA xor ACBD xor
ADCB xor CDAB xor DABC xor BCAD xor CADB xor CDBA xor
Line 859 ⟶ 1,165:
BADC xor BDAC xor CBDA xor DBCA xor DCAB xor
cr .( Missing permutation: ) u.
decimal</
{{out}}
<pre>Missing permutation: DBAC ok</pre>
Line 865 ⟶ 1,171:
=={{header|Fortran}}==
'''Work-around''' to let it run properly with some bugged versions (e.g. 4.3.2) of gfortran: remove the ''parameter'' attribute to the array list.
<
implicit none
Line 880 ⟶ 1,186:
write (*, *)
end program missing_permutation</
{{out}}
<pre>DBAC</pre>
=={{header|FreeBASIC}}==
===Simple count===
<syntaxhighlight lang="freebasic">' version 30-03-2017
' compile with: fbc -s console
Data "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD"
Data "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA"
Data "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD"
Data "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
' ------=< MAIN >=------
Dim As ulong total(3, Asc("A") To Asc("D")) ' total(0 to 3, 65 to 68)
Dim As ULong i, j, n = 24 \ 4 ' n! \ n
Dim As String tmp
For i = 1 To 23
Read tmp
For j = 0 To 3
total(j, tmp[j]) += 1
Next
Next
tmp = Space(4)
For i = 0 To 3
For j = Asc("A") To Asc("D")
If total(i, j) <> n Then
tmp[i] = j
End If
Next
Next
Print "The missing permutation is : "; tmp
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>The missing permutation is : DBAC</pre>
===Add the value's===
<syntaxhighlight lang="freebasic">' version 30-03-2017
' compile with: fbc -s console
Data "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD"
Data "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA"
Data "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD"
Data "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
' ------=< MAIN >=------
Dim As ULong total(3) ' total(0 to 3)
Dim As ULong i, j, n = 24 \ 4 ' n! \ n
Dim As ULong total_val = (Asc("A") + Asc("B") + Asc("C") + Asc("D")) * n
Dim As String tmp
For i = 1 To 23
Read tmp
For j = 0 To 3
total(j) += tmp[j]
Next
Next
tmp = Space(4)
For i = 0 To 3
tmp[i] = total_val - total(i)
Next
Print "The missing permutation is : "; tmp
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
<pre>output is same as the first version</pre>
===Using Xor===
<syntaxhighlight lang="freebasic">' version 30-03-2017
' compile with: fbc -s console
Data "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD"
Data "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA"
Data "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD"
Data "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
' ------=< MAIN >=------
Dim As ULong i,j
Dim As String tmp, missing = chr(0, 0, 0, 0) ' or string(4, 0)
For i = 1 To 23
Read tmp
For j = 0 To 3
missing[j] Xor= tmp[j]
Next
Next
Print "The missing permutation is : "; missing
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
<pre>Output is the same as the first version</pre>
=={{header|Frink}}==
<syntaxhighlight lang="frink">p = toSet[trim[splitLines["""ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB"""]]]
s = ["A","B","C","D"]
for n = s.lexicographicPermute[]
{
str = join["", n]
if ! p.contains[str]
println[str]
}</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
=={{header|GAP}}==
<
L :=
[ "ABCD", "CABD", "ACDB", "DACB", "BCDA",
Line 901 ⟶ 1,351:
# convert back to letters
s := "ABCD";
List(v, p -> List(p, i -> s[i]));</
=={{header|Go}}==
Alternate method suggested by task description:
<
import (
Line 950 ⟶ 1,401:
}
fmt.Println(string(b))
}</
Xor method suggested by
<
b := make([]byte, len(given[0]))
for _, p := range given {
Line 960 ⟶ 1,411:
}
fmt.Println(string(b))
}</
{{out}} in either case:
<pre>
Line 968 ⟶ 1,419:
=={{header|Groovy}}==
Solution:
<
def missingPerms
missingPerms = {List elts, List perms ->
Line 976 ⟶ 1,427:
: missingPerms(elts - e, ePerms).collect { [e] + it }
}.sum()
}</
Test:
<
def p = ['ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB', 'DABC', 'BCAD', 'CADB', 'CDBA',
'CBAD', 'ABDC', 'ADBC', 'BDCA', 'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'].collect { it as List }
def mp = missingPerms(e, p)
mp.each { println it }</
{{out}}
Line 990 ⟶ 1,441:
=={{header|Haskell}}==
====Difference between two lists====
{{works with|GHC|7.10.3}}
<
import Control.Monad (join)
Line 1,027 ⟶ 1,479:
main :: IO ()
main = print $ missingPerm deficientPermsList</
{{Out}}
<pre>["DBAC"]</pre>
====Character frequency in each column====
Another, more statistical, approach is to return the least common letter in each of the four columns. (If all permutations were present, letter frequencies would not vary).
<
import Data.Ord (comparing)
Line 1,039 ⟶ 1,492:
:: Ord a
=> [[a]] -> [a]
missingPerm =
deficientPermsList :: [String]
Line 1,069 ⟶ 1,522:
main :: IO ()
main = print $ missingPerm deficientPermsList</
{{Out}}
<pre>"DBAC"</pre>
====Folding XOR over the list of permutations====
Surfacing the missing bits:
{{Trans|JavaScript}}
{{Trans|Python}}
<syntaxhighlight lang="haskell">import Data.Char (chr, ord)
import Data.Bits (xor)
missingPerm :: [String] -> String
missingPerm = fmap chr . foldr (zipWith xor . fmap ord) [0, 0, 0, 0]
deficientPermsList :: [String]
deficientPermsList =
[ "ABCD"
, "CABD"
, "ACDB"
, "DACB"
, "BCDA"
, "ACBD"
, "ADCB"
, "CDAB"
, "DABC"
, "BCAD"
, "CADB"
, "CDBA"
, "CBAD"
, "ABDC"
, "ADBC"
, "BDCA"
, "DCBA"
, "BACD"
, "BADC"
, "BDAC"
, "CBDA"
, "DBCA"
, "DCAB"
]
main :: IO ()
main = putStrLn $ missingPerm deficientPermsList</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 1,085 ⟶ 1,580:
write("The difference is : ")
every write(!givens, " ")
end</
The approach above generates a full set of permutations and calculates the difference. Changing the two commented lines to the three below will calculate on the fly and would be more efficient for larger data sets.
<
if member(givens,x) then delete(givens,x) # remove givens as they are generated
else insert(givens,x) # add back any not given</
A still more efficient version is:
<
procedure main()
Line 1,105 ⟶ 1,600:
if not member(givens, p) then write(p)
end</
{{libheader|Icon Programming Library}}
Line 1,112 ⟶ 1,607:
=={{header|J}}==
'''Solution:'''
<
missingPerms=: -.~ permutations @ {.</
'''Use:'''
<pre>data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA'
Line 1,125 ⟶ 1,620:
Or the above could be a single definition that works the same way:
<
Or the equivalent explicit (cf. tacit above) definition:
<
item=. {. y
y -.~ item A.~ i.! #item
)</
Or, the solution could be obtained without defining an independent program:
<
DBAC</
Here, <code>'ABCD'</code> represents the values being permuted (their order does not matter), and <code>4</code> is how many of them we have.
Line 1,142 ⟶ 1,637:
Yet another alternative expression, which uses parentheses instead of the [http://www.jsoftware.com/help/dictionary/d220v.htm passive operator] (<code>~</code>), would be:
<
DBAC</
Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable:
<
DBAC</
However, that's actually a false economy - not only does this approach take more code to implement (at least, in J) but we are already dealing with a data structure of approximately the size of all permutations. So what is being saved by this supposedly "more efficient" approach? Not much... (Still, perhaps this exercise is useful as an illustration of some kind of advertising concept?)
We could use parity, as suggested in the task hints:
<
DBAC</
We could use arithmetic, as suggested in the task hints:
<
DBAC</
=={{header|Java}}==
Line 1,164 ⟶ 1,659:
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]]
<
import com.google.common.base.Joiner;
Line 1,183 ⟶ 1,678:
System.out.println(joiner.join(cs));
}
}</
{{out}}
Line 1,190 ⟶ 1,685:
Alternate version, based on checksumming each position:
<
{
public static void main(String[] args)
Line 1,213 ⟶ 1,708:
System.out.println("Missing permutation: " + missingPermutation.toString());
}
}</
=={{header|JavaScript}}==
Line 1,221 ⟶ 1,716:
The permute() function taken from http://snippets.dzone.com/posts/show/1032
<
for(var p = -1, j, k, f, r, l = v.length, q = 1, i = l + 1; --i; q *= i);
for(x = [new Array(l), new Array(l), new Array(l), new Array(l)], j = q, k = l + 1, i = -1;
Line 1,240 ⟶ 1,735:
missing = all.filter(function(elem) {return list.indexOf(elem) == -1});
print(missing); // ==> DBAC</
====Functional====
<
// [a] -> [[a]]
Line 1,283 ⟶ 1,778:
'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\
CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB'
);</
{{Out}}
<
===ES6===
====Statistical====
=====Using a dictionary=====
<
'use strict';
Line 1,324 ⟶ 1,819:
// --> 'DBAC'
})();</
{{Out}}
<pre>DBAC</pre>
=====Composing functional primitives=====
{{Trans|Haskell}}
<syntaxhighlight lang="javascript">(() => {
'use strict';
// MISSING PERMUTATION ---------------------------------------------------
// missingPermutation :: [String] -> String
const missingPermutation = xs =>
map(
// Rarest letter,
compose([
sort,
group,
curry(minimumBy)(comparing(length)),
head
]),
// in each column.
transpose(map(stringChars, xs))
)
.join('');
// GENERIC FUNCTIONAL PRIMITIVES -----------------------------------------
// transpose :: [[a]] -> [[a]]
const transpose = xs =>
xs[0].map((_, iCol) => xs.map(row => row[iCol]));
// sort :: Ord a => [a] -> [a]
const sort = xs => xs.sort();
// group :: Eq a => [a] -> [[a]]
const group = xs => groupBy((a, b) => a === b, xs);
// groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
const groupBy = (f, xs) => {
const dct = xs.slice(1)
.reduce((a, x) => {
const
h = a.active.length > 0 ? a.active[0] : undefined,
blnGroup = h !== undefined && f(h, x);
return {
active: blnGroup ? a.active.concat(x) : [x],
sofar: blnGroup ? a.sofar : a.sofar.concat([a.active])
};
}, {
active: xs.length > 0 ? [xs[0]] : [],
sofar: []
});
return dct.sofar.concat(dct.active.length > 0 ? [dct.active] : []);
};
// length :: [a] -> Int
const length = xs => xs.length;
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
(x, y) => {
const
a = f(x),
b = f(y);
return a < b ? -1 : a > b ? 1 : 0
};
// minimumBy :: (a -> a -> Ordering) -> [a] -> a
const minimumBy = (f, xs) =>
xs.reduce((a, x) => a === undefined ? x : (
f(x, a) < 0 ? x : a
), undefined);
// head :: [a] -> a
const head = xs => xs.length ? xs[0] : undefined;
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f)
// compose :: [(a -> a)] -> (a -> a)
const compose = fs => x => fs.reduce((a, f) => f(a), x);
// curry :: ((a, b) -> c) -> a -> b -> c
const curry = f => a => b => f(a, b);
// stringChars :: String -> [Char]
const stringChars = s => s.split('');
// TEST ------------------------------------------------------------------
return missingPermutation(["ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
]);
// -> "DBAC"
})();</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
====XOR====
Folding an xor operator over the list of character codes:
<syntaxhighlight lang="javascript">(() => {
'use strict';
// main :: IO ()
const main = () => {
const xs = [
'ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD',
'ADCB', 'CDAB', 'DABC', 'BCAD', 'CADB', 'CDBA',
'CBAD', 'ABDC', 'ADBC', 'BDCA', 'DCBA', 'BACD',
'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'
];
return xs.reduce(
(a, x) => zipWith(xor)(a)(codes(x)),
[0, 0, 0, 0]
).map(x => String.fromCodePoint(x)).join('')
};
// ---------------------- GENERIC ----------------------
// codes :: String -> [Int]
const codes = s =>
s.split('').map(c => c.codePointAt(0));
// xor :: Int -> Int -> Int
const xor = a =>
b => (a ^ b)
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => xs.slice(0).map(
(x, i) => f(x)(ys[i])
);
return main()
})();</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
Line 1,349 ⟶ 1,990:
If your version of jq has transpose/0, the definition given here
(which is the same as in [[Matrix_Transpose#jq]]) may be omitted.
<
if (.[0] | length) == 0 then []
else [map(.[0])] + (map(.[1:]) | transpose)
Line 1,370 ⟶ 2,011:
# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]):
def encode_string: [explode[] - 65];</
'''The task''':
<
{{Out}}
<
"DBAC"</
=={{header|Julia}}==
{{works with|Julia|0.6}}
=== Obvious method ===
Calculate all possible permutations and return the first not included in the array.
<syntaxhighlight lang="julia">using BenchmarkTools, Combinatorics
function missingperm(arr::Vector)
allperms = String.(permutations(arr[1])) # revised for type safety
for perm in allperms
if perm ∉ arr return perm end
end
end
arr = ["ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD",
"CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC",
@show missingperm(arr)</syntaxhighlight>
{{out}}
<pre>missingperm(arr) = "DBAC"</pre>
=== Alternative method 1 ===
{{trans|Python}}
<syntaxhighlight lang="julia">function missingperm1(arr::Vector{<:AbstractString})
c = perm[pos]
if c ∈ s pop!(s, c) else push!(s, c) end
end
missperm *= first(s)
end
return missperm
end
</syntaxhighlight>
=== Alternative method 2 ===
{{trans|Raku}}
<syntaxhighlight lang="julia">function missingperm2(arr::Vector)
len = length(arr[1])
xorval = zeros(UInt8, len)
for perm in [Vector{UInt8}(s) for s in arr], i in 1:len
xorval[i] ⊻= perm[i]
end
return String(xorval)
end
@show missingperm(arr)
@show missingperm1(arr)
@show missingperm2(arr)
@btime missingperm(arr)
@btime missingperm1(arr)
@btime missingperm2(arr)
</syntaxhighlight>{{out}}
<pre>
missingperm(arr) = "DBAC"
missingperm1(arr) = "DBAC"
missingperm2(arr) = "DBAC"
6.460 μs (148 allocations: 8.55 KiB)
6.780 μs (24 allocations: 2.13 KiB)
3.100 μs (50 allocations: 2.94 KiB)
</pre>
=={{header|K}}==
<
g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB")
Line 1,467 ⟶ 2,110:
p2@&~p2 _lin p
"DBAC"</
Alternative approach:
<
table:{b@<b:(x@*:'a),'#:'a:=x}
,/"ABCD"@&:'{5=(table p[;x])[;1]}'!4
"DBAC"</
Third approach (where p is the given set of permutations):
<syntaxhighlight lang="k">
,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p
</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.2
fun <T> permute(input: List<T>): List<List<T>> {
if (input.size == 1) return listOf(input)
val perms = mutableListOf<List<T>>()
val toInsert = input[0]
for (perm in permute(input.drop(1))) {
for (i in 0..perm.size) {
val newPerm = perm.toMutableList()
newPerm.add(i, toInsert)
perms.add(newPerm)
}
}
return perms
}
fun <T> missingPerms(input: List<T>, perms: List<List<T>>) = permute(input) - perms
fun main(args: Array<String>) {
val input = listOf('A', 'B', 'C', 'D')
val strings = listOf(
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
)
val perms = strings.map { it.toList() }
val missing = missingPerms(input, perms)
if (missing.size == 1)
print("The missing permutation is ${missing[0].joinToString("")}")
else {
println("There are ${missing.size} missing permutations, namely:\n")
for (perm in missing) println(perm.joinToString(""))
}
}</syntaxhighlight>
{{out}}
<pre>
The missing permutation is DBAC
</pre>
=={{header|Lua}}==
Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight
<
local permList, pStr = {
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
Line 1,491 ⟶ 2,175:
pStr = table.concat(perm)
if not tablex.find(permList, pStr) then print(pStr) end
end</
{{out}}
<pre>DBAC</pre>
=={{header|Maple}}==
<syntaxhighlight lang="maple">lst := ["ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB","DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA","DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"]:
perm := table():
for letter in "ABCD" do
perm[letter] := 0:
end do:
for item in lst do
for letter in "ABCD" do
perm[letter] += StringTools:-FirstFromLeft(letter, item):
end do:
end do:
print(StringTools:-Join(ListTools:-Flatten([indices(perm)], 4)[sort(map(x->60-x, ListTools:-Flatten([entries(perm)],4)),'output=permutation')], "")):</syntaxhighlight>
{{Out|Output}}
<pre>"DBAC"</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC",
"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"};
Line 1,503 ⟶ 2,202:
->{"DBAC"}</
=={{header|MATLAB}}==
This solution is designed to work on a column vector of strings. This will not work with a cell array or row vector of strings.
<
permsList = perms(list(1,:)); %Generate all permutations of the 4 letters
Line 1,534 ⟶ 2,233:
end %for
end %fingMissingPerms</
{{out}}
<
'CABD';
'ACDB';
Line 1,591 ⟶ 2,290:
ans =
DBAC</
=={{header|Nim}}==
{{trans|Python}}
<
proc missingPermutation(arr: openArray[string]): string =
result = ""
if arr.len == 0: return
if arr.len == 1: return arr[0][1] & arr[0][0]
for pos in 0 ..
var s: set[char] = {}
for permutation in arr:
Line 1,611 ⟶ 2,310:
const given = """ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB""".
echo missingPermutation(given)</
{{out}}
<pre>DBAC</pre>
Line 1,620 ⟶ 2,319:
some utility functions:
<
let rec insert x = function
| [] -> [[x]]
Line 1,637 ⟶ 2,336:
(* convert a char list to a string *)
let string_of_chars cl =
String.concat "" (List.map (String.make 1) cl)</
resolve the task:
<
"ABCD";"CABD";"ACDB";"DACB";
"BCDA";"ACBD";"ADCB";"CDAB";
Line 1,656 ⟶ 2,355:
let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms
let () = List.iter print_endline results</
Alternate method : if we had all permutations,
Line 1,664 ⟶ 2,363:
of the number of occurences of each letter.
The following program works with permutations of at least 3 letters:
<
let n = String.length s in
Array.init n (fun i -> int_of_char s.[i] - 65);;
Line 1,693 ⟶ 2,392:
find_missing deficient_perms;;
(* - : string = "DBAC" *)</
=={{header|Octave}}==
<
'BCDA';'ACBD';'ADCB';'CDAB'; ...
'DABC';'BCAD';'CADB';'CDBA'; ...
Line 1,710 ⟶ 2,409:
bits(there) = 0;
missing = dec2base(find(bits)-1,'ABCD')
</syntaxhighlight>
=={{header|Oz}}==
Using constraint programming for this problem may be a bit overkill...
<
GivenPermutations =
["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
Line 1,733 ⟶ 2,432:
{System.showInfo "Missing: "#P}
end
end</
=={{header|PARI/GP}}==
<
v=apply(u->permtonum(apply(n->n-64,Vec(Vecsmall(u)))),v);
t=numtoperm(4, binomial(4!,2)-sum(i=1,#v,v[i]));
Strchr(apply(n->n+64,t))</
{{out}}
<pre>%1 = "DBAC"</pre>
=={{header|Pascal}}==
like [[c]], summation, and [[
<
{$MODE DELPHI} //for result
Line 1,788 ⟶ 2,489:
For row := low(tcol) to High(tcol) do
IF SumElemCol[col,row]=fibN_1 then
result[col]:=
end;
Line 1,799 ⟶ 2,500:
For row := low(tmissPerm) to High(tmissPerm) do
For col := low(tcol) to High(tcol) do
result[col] :=
end;
Line 1,805 ⟶ 2,506:
writeln(CountOccurences,' is missing');
writeln(CheckXOR,' is missing');
end.</
DBAC is missing</pre>
Line 1,813 ⟶ 2,514:
the first missing rotation is the target.
<
my %hash; @hash{@_} = ();
for my $s (@_) { exists $hash{$_} or return $_
Line 1,822 ⟶ 2,523:
@perms = qw(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB);
print check_perm(@perms), "\n";</
{{out}}
<pre>DBAC</pre>
===Alternates===
All cases take permutation list on STDIN or as filename on command line
<br><br>
If the string XOR was of all the permutations, the result would be a string of nulls "\0",
since one is missing, it is the result of XOR of all the rest :)
<syntaxhighlight lang="perl">print eval join '^', map "'$_'", <>;</syntaxhighlight>
or if you don't like eval...
<syntaxhighlight lang="perl">$\ ^= $_ while <>;
print '';</syntaxhighlight>
<syntaxhighlight lang="perl">local $_ = join '', <>;
my %h = map { $_, '' } reverse =~ /\w+/g;
delete @h{ /\w+/g };
print %h, "\n";</syntaxhighlight>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"ABCD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CABD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ACDB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DACB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BCDA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ACBD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ADCB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CDAB"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"DABC"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BCAD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CADB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CDBA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CBAD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ABDC"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ADBC"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BDCA"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"DCBA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BACD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BADC"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BDAC"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CBDA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DBCA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DCAB"</span><span style="color: #0000FF;">}</span>
<span style="color: #000080;font-style:italic;">-- 1: sum of letters</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)+</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- based on the notion that missing = sum(full)-sum(partial) would be true,
-- and that sum(full) would be like {M,M,M,M} rather than a mix of numbers.
-- the final step is
-- max-r[i] -> { 3, 1, 0, 2}
-- to chars -> { D, B, A, C}
-- (but obviously both done in one line)
-- 2: the xor trick</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_xor_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- (relies on the missing chars being present an odd number of times, non-missing chars an even number of times)
-- 3: find least frequent letters</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">cdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">smallest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)+</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- (relies on the assumption that a full set would have each letter occurring the same number of times in each position)
-- (smallest(count,1) returns the index position of the smallest, rather than it's value)
-- 4: test all permutations</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"ABCD"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- (relies on brute force(!) - but this is the only method that could be made to cope with >1 omission)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,897 ⟶ 2,603:
=={{header|PHP}}==
<
$finalres = Array();
function permut($arr,$result=array()){
Line 1,917 ⟶ 2,623:
permut($given);
print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC )
</syntaxhighlight>
=={{header|Picat}}==
Here are several approaches, including constraint modelling, sets (ordset), and permutations.
All assume that the variables P1 and/or Perms has been defined:
<syntaxhighlight lang="picat"> P1 = ["ABCD","CABD","ACDB","DACB","BCDA","ACBD",
"ADCB","CDAB","DABC","BCAD","CADB","CDBA",
"CBAD","ABDC","ADBC","BDCA","DCBA","BACD",
"BADC","BDAC","CBDA","DBCA","DCAB"],
Perms = permutations("ABCD"),
% ...
</syntaxhighlight>
===Very imperative===
<syntaxhighlight lang="picat"> % ...
Missing = _,
foreach(P in Perms, Missing = _)
Found = false,
foreach(T in P1)
if P == T then
Found := true
end
end,
if not Found then
Missing := P
end
end,
println(missing1=Missing).</syntaxhighlight>
===Somewhat less imperative===
<syntaxhighlight lang="picat"> % ...
Missing2 = _,
foreach(P in Perms, Missing2 = _)
if not member(P,P1) then
Missing2 := P
end
end,
println(missing2=Missing2).</syntaxhighlight>
===Using findall===
<syntaxhighlight lang="picat"> % ...
println(missing3=difference(Perms,P1)).
difference(Xs,Ys) = findall(X,(member(X,Xs),not(member(X,Ys)))).</syntaxhighlight>
===findall approach as a one-liner===
<syntaxhighlight lang="picat"> % ...
println(missing4=findall(X,(member(X,Perms),not(member(X,P1))))).</syntaxhighlight>
===Using ordsets===
The module <code>ordsets</code> must be imported,
<syntaxhighlight lang="picat">import ordsets.
% ...
println(missing5=subtract(new_ordset(Perms),new_ordset(P1))).</syntaxhighlight>
===List comprehension===
List comprehension with <code>membchk/1</code> for the check)
<syntaxhighlight lang="picat"> % ...
println(missing6=[P:P in Perms,not membchk(P,P1)])</syntaxhighlight>
===Using maps===
<syntaxhighlight lang="picat"> % ...
Map = new_map(),
foreach(P in P1) Map.put(P,1) end,
println(missing7=[P: P in Perms, not Map.has_key(P)]).</syntaxhighlight>
==="Merge sort" variants===
"Merge sort" variants, using sorted lists. <code>zip/2</code> requires that the length of the two lists are the same, hence the "dummy".
<syntaxhighlight lang="picat"> % ...
PermsSorted = Perms.sort(),
P1Sorted = P1.sort(),
Found2 = false,
foreach({P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"]), Found2 = false)
if P != PP then
println(missing8=P),
Found2 := true
end
end,
A = [cond(P == PP,1,0) : {P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"])],
println(missing9=[PermsSorted[I] : I in 1..PermsSorted.length, A[I] = 0].first()),
% shorter
println(missing10=[P:{P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"]), P != PP].first()),</syntaxhighlight>
===Constraint modelling===
The <code>cp</code> module must be imported.
<syntaxhighlight lang="picat">import cp.
% ...
ABCD = new_map(['A'=1,'B'=2,'C'=3,'D'=4]),
% convert to integers (for the table constraint)
P1Table = [ [ABCD.get(C,0) : C in P].to_array() : P in P1],
Missing3 = new_list(4), Missing3 :: 1..4,
all_different(Missing3),
table_notin({Missing3[1],Missing3[2],Missing3[3],Missing3[4]},P1Table),
solve(Missing3),
ABCD2 = "ABCD",
println(missing11=[ABCD2[I] : I in Missing3]).</syntaxhighlight>
===Matrix approach===
<syntaxhighlight lang="picat"> % ...
PermsLen = Perms.length,
P1Len = P1.length,
A2 = new_array(PermsLen,P1Len), bind_vars(A2,0),
foreach(I in 1..PermsLen, J in 1..P1Len, Perms[I] = P1[J])
A2[I,J] := 1
end,
println(missing12=[Perms[I] : I in 1..PermsLen, sum([A2[I,J] : J in 1..P1Len])=0]).</syntaxhighlight>
===Xor variant===
{{trans|Raku}}
<syntaxhighlight lang="picat"> % ...
println(missing13=to_fstring("%X",reduce(^,[parse_term("0x"++P):P in P1]))).</syntaxhighlight>
===Count occurrences===
Count the character with the least occurrence (=5) for each positions (1..4). Some variants.
{{trans|K}}
<syntaxhighlight lang="picat"> % ...
println(missing14=[[O:O=5 in Occ]:Occ in [occurrences([P[I]:P in P1]):I in 1..4]]),
% variant using sorting the occurrences
println(missing15a=[C:C=_ in [sort2(Occ).first():Occ in [occurrences([P[I]:P in P1]):I in 1..4]]]),
% transpose instead of array index
println(missing15b=[C:C=_ in [sort2(O).first():T in transpose(P1),O=occurrences(T)]]),
% extract the values with first
println(missing15c=[sort2(O).first():T in transpose(P1),O=occurrences(T)].map(first)),
println(missing15d=[sort2(O).first().first():T in transpose(P1),O=occurrences(T)]),
println(missing15e=[S[1,1]:T in transpose(P1),S=sort2(occurrences(T))]).
% return a map with the elements and the number of occurrences
occurrences(List) = Map =>
Map = new_map(),
foreach(E in List)
Map.put(E, cond(Map.has_key(E),Map.get(E)+1,1))
end,
Perms2 = Perms,
foreach(P in P1) Perms2 := delete(Perms2,P) end,
println(missing16=Perms2),
nl.
% sort a map according to values
sort2(Map) = [K=V:_=(K=V) in sort([V=(K=V): K=V in Map])]
</syntaxhighlight>
Running all these snippets:
{{out}}
<pre>
missing1 = DBAC
missing2 = DBAC
missing3 = [DBAC]
missing4 = [DBAC]
missing5 = [DBAC]
missing6 = [DBAC]
missing7 = [DBAC]
missing8 = DBAC
missing9 = DBAC
missing10 = DBAC
missing11 = DBAC
missing12 = [DBAC]
missing13 = DBAC
missing14 = [D,B,A,C]
missing15a = DBAC
missing15b = DBAC
missing15c = DBAC
missing15d = DBAC
missing15e = DBAC
missing16 = [DBAC]</pre>
=={{header|PicoLisp}}==
<
(mapcar chop
(quote
Line 1,934 ⟶ 2,815:
(rot L) )
(unless (member Lst *PermList) # Check
(prinl Lst) ) ) ) )</
{{out}}
<pre>DBAC</pre>
Line 1,941 ⟶ 2,822:
{{works with|PowerShell|4.0}}
<syntaxhighlight lang="powershell">
function permutation ($array) {
function generate($n, $array, $A) {
Line 1,998 ⟶ 2,879:
)
$perm | where{-not $find.Contains($_)}
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 2,005 ⟶ 2,886:
=={{header|PureBasic}}==
<
Define.i i, j
Define.s a
Line 2,043 ⟶ 2,924:
Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA"
Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"
EndDataSection</
Based on the [[Permutations#PureBasic|Permutations]] task,
the solution could be:
<
NewList a.s()
findPermutations(a(), "ABCD", 4)
Line 2,061 ⟶ 2,942:
Print(#CRLF$ + "Press ENTER to exit"): Input()
EndIf</
=={{header|Python}}==
===Python: Calculate difference when compared to all permutations===
{{works with|Python|2.6+}}
<
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
Line 2,073 ⟶ 2,954:
allPerms = [''.join(x) for x in permutations(given[0])]
missing = list(set(allPerms) - set(given)) # ['DBAC']</
===Python:Counting lowest frequency character at each position===
Line 2,079 ⟶ 2,960:
i.e. it never needs to generate the full set of expected permutations.
<
def missing_permutation(arr):
"Find the missing permutation in an array of N! - 1 permutations."
Line 2,110 ⟶ 2,991:
print missing_permutation(given)
</syntaxhighlight>
===Python:Counting lowest frequency character at each position: functional===
Uses the same method as explained directly above,
but calculated in a more functional manner:
<
>>> given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'''.split()
>>> ''.join(Counter(x).most_common()[-1][0] for x in zip(*given))
'DBAC'
>>> </
;Explanation
Line 2,129 ⟶ 3,010:
created by the call to <code>most_common()</code>
is the least common character.
<
>>> pp(list(zip(*given)), width=120)
[('A', 'C', 'A', 'D', 'B', 'A', 'A', 'C', 'D', 'B', 'C', 'C', 'C', 'A', 'A', 'B', 'D', 'B', 'B', 'B', 'C', 'D', 'D'),
Line 2,146 ⟶ 3,027:
>>> ''.join([Counter(x).most_common()[-1][0] for x in zip(*given)])
'DBAC'
>>> </
===Python:Folding XOR over the set of strings===
Surfacing the missing bits:
{{Trans|JavaScript}}
<syntaxhighlight lang="python">'''Find the missing permutation'''
from functools import reduce
from operator import xor
print(''.join([
chr(i) for i in reduce(
lambda a, s: map(
xor,
a,
[ord(c) for c in list(s)]
), [
'ABCD', 'CABD', 'ACDB', 'DACB',
'BCDA', 'ACBD', 'ADCB', 'CDAB',
'DABC', 'BCAD', 'CADB', 'CDBA',
'CBAD', 'ABDC', 'ADBC', 'BDCA',
'DCBA', 'BACD', 'BADC', 'BDAC',
'CBDA', 'DBCA', 'DCAB'
],
[0, 0, 0, 0]
)
]))</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
=={{header|Quackery}}==
Credit to [[#Raku|Raku]] for the method, and noting that the strings are valid hexadecimal numbers.
<syntaxhighlight lang="quackery"> $ "ABCD CABD ACDB DACB BCDA ACBD
ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD
BADC BDAC CBDA DBCA DCAB" nest$
16 base put
[] swap
witheach [ $->n drop join ]
0 swap witheach ^
number$ echo$
base release</syntaxhighlight>
{{out}}
<pre>DBAC</pre>
=={{header|R}}==
This uses the "combinat" package, which is a standard R package:
<syntaxhighlight lang="text">
library(combinat)
Line 2,163 ⟶ 3,092:
setdiff(perms3, incomplete)
</syntaxhighlight>
{{out}}
Line 2,171 ⟶ 3,100:
=={{header|Racket}}==
<
#lang racket
Line 2,207 ⟶ 3,136:
c))
;; -> '(D B A C)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>my @givens = <ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>;
my @perms = <A B C D>.permutations.map: *.join;
.say when none(@givens) for @perms;</syntaxhighlight>
{{out}}<pre>DBAC</pre>
Of course, all of these solutions are working way too hard,
when you can just xor all the bits,
and the missing one will just pop right out:
<syntaxhighlight lang="raku" line>say [~^] <ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>;</syntaxhighlight>
{{out}}<pre>DBAC</pre>
=={{header|RapidQ}}==
<syntaxhighlight lang="vb">
Dim PList as QStringList
PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB"
Line 2,235 ⟶ 3,180:
showmessage MPerm
'= DBAC
</syntaxhighlight>
=={{header|REXX}}==
<
"DCBA BACD BADC BDAC CBDA DBCA DCAB"
@.= /* [↓] needs to be as long as THINGS.*/
@abcU
things
bunch
do j=1 for things /* [↓] only get a portion of alphabet.*/
$.j= substr(@abcU, j, 1)
end /*j*/ /* [↑] build a letter array for speed.*/
call permSet 1 /*invoke PERMSET subroutine recursively*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
permSet: procedure expose $. @. bunch list things;
if ?>bunch then do; _=
do m=1 for bunch /*build a permutation. */
_= _ || @.m
end /*m*/
/* [↓] is in the list? */
Line 2,261 ⟶ 3,206:
else do x=1 for things /*build a permutation. */
do k=1 for ?-1
if @.k==$.x then iterate x
end /*k*/
@.?= $.x
call permSet ?+1 /*call
end /*x*/
return</
{{out|output|text= when using the default input:}}
<pre>
DBAC is missing from the list.
Line 2,273 ⟶ 3,218:
=={{header|Ring}}==
<
list = "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
Line 2,287 ⟶ 3,232:
next
next
</syntaxhighlight>
Output:
<pre>
Line 2,295 ⟶ 3,240:
=={{header|Ruby}}==
{{works with|Ruby|2.0+}}
<
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
Line 2,302 ⟶ 3,247:
all = given[0].chars.permutation.collect(&:join)
puts "missing: #{all - given}"</
{{out}}
<pre>
Line 2,309 ⟶ 3,254:
=={{header|Run BASIC}}==
<
for a = asc("A") to asc("D")
Line 2,324 ⟶ 3,269:
next c
next b
next a</
{{out}}
<pre>DBAC missing</pre>
=={{header|Rust}}==
{{trans|Go}}
Xor method suggested by Raku contributor:
<syntaxhighlight lang="rust">const GIVEN_PERMUTATIONS: [&str; 23] = [
"ABCD",
"CABD",
"ACDB",
"DACB",
"BCDA",
"ACBD",
"ADCB",
"CDAB",
"DABC",
"BCAD",
"CADB",
"CDBA",
"CBAD",
"ABDC",
"ADBC",
"BDCA",
"DCBA",
"BACD",
"BADC",
"BDAC",
"CBDA",
"DBCA",
"DCAB"
];
fn main() {
const PERMUTATION_LEN: usize = GIVEN_PERMUTATIONS[0].len();
let mut bytes_result: [u8; PERMUTATION_LEN] = [0; PERMUTATION_LEN];
for permutation in &GIVEN_PERMUTATIONS {
for (i, val) in permutation.bytes().enumerate() {
bytes_result[i] ^= val;
}
}
println!("{}", std::str::from_utf8(&bytes_result).unwrap());
}
</syntaxhighlight>
{{out}}
<pre>
DBAC
</pre>
=={{header|Scala}}==
{{libheader|Scala}}
{{works with|Scala|2.8}}
<
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {
val n = a.size
Line 2,370 ⟶ 3,363:
DBCA
DCAB""".stripMargin.split("\n")
println(findMissingPerm(perms(0), perms))</
===Scala 2.9.x===
{{works with|Scala|2.9.1}}
<
--"ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB".stripMargin.split(" ").toSet))</
=={{header|Seed7}}==
<
const func string: missingPermutation (in array string: perms) is func
Line 2,410 ⟶ 3,403:
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB")));
end func;</
{{out}}
Line 2,419 ⟶ 3,412:
=={{header|Sidef}}==
{{trans|Perl}}
<
hash.set_keys(arr...)
arr.each { |s|
var t = (s.substr(1) + s.substr(0, 1))
hash.has_key(t) || return t
} * s.len
}
}
var perms = %w(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB)
say check_perm(perms)
{{out}}
<pre>
DBAC
</pre>
=={{header|TI-83 BASIC}}==
<syntaxhighlight lang="ti83b">"ABCDCABDACDBDACBBCDAACBDADCBCDABDABCBCADCADBCDBACBADABDCADBCBDCADCBABACDBADCBDACCBDADBCADCAB"→Str0
"ABCD"→Str1
length(Str0)→L
[[0,0,0,0][0,0,0,0][0,0,0,0][0,0,0,0]]→[A]
For(I,1,L,4)
For(J,1,4,1)
sub(Str0,I+J-1,1)→Str2
For(K,1,4,1)
sub(Str1,K,1)→Str3
If Str2=Str3
Then
[A](J,K)+1→[A](J,K)
End
End
End
End
Matr►list([A],1,L₁)
min(L₁)→M
" "→Str4
For(I,1,4,1)
For(J,1,4,1)
If [A](I,J)=M
Then
Str4+sub(Str1,J,1)→Str4
End
End
End
sub(Str4,2,4)→Str4
Disp "MISSING"
Disp Str4</syntaxhighlight>
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
package require struct::list
Line 2,454 ⟶ 3,484:
}
}
</syntaxhighlight>
=={{header|Ursala}}==
Line 2,460 ⟶ 3,490:
and needn't be reinvented, but its definition is shown here in the interest of
comparison with other solutions.
<
The <code>~&j</code> operator computes set differences.
<
#show+
Line 2,490 ⟶ 3,520:
CBDA
DBCA
DCAB]-</
{{out}}
<pre>
Line 2,498 ⟶ 3,528:
=={{header|VBScript}}==
Uses the 3rd method approach by adding the columns.
<syntaxhighlight lang="vb">
arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_
Line 2,523 ⟶ 3,553:
WScript.StdOut.WriteLine missing
</syntaxhighlight>
{{Out}}
<pre>DBAC</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">
fn main() {
list := ('ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB
CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB')
elem := ['A', 'B', 'C', 'D']
if find_missed_pmt_1(list, elem) !='' {println('${find_missed_pmt_1(list, elem)} is missing')}
else {println('Warning: nothing found')}
if find_missed_pmt_2(list, elem) !='' {println('${find_missed_pmt_2(list, elem)} is missing')}
else {println('Warning: nothing found')}
if find_missed_pmt_3(list, elem) !='' {println('${find_missed_pmt_3(list, elem)} is missing')}
else {println('Warning: nothing found')}
}
fn find_missed_pmt_1(list string, elem []string) string {
mut result := ''
for avals in elem {
for bvals in elem {
for cvals in elem {
for dvals in elem {
result = avals + bvals + cvals + dvals
if avals != bvals
&& avals != cvals
&& avals != dvals
&& bvals != cvals
&& bvals != dvals
&& cvals != dvals {
if list.replace_each(['\n','','\t','']).split(' ').any(it == result) == false {return result}
}
}
}
}
}
return result
}
fn find_missed_pmt_2(list string, elem []string) string {
list_arr := list.replace_each(['\n','','\t','']).split(' ')
mut es := []u8{len: elem.len}
mut aa := map[u8]int{}
mut result :=''
for idx, _ in es {
aa = map[u8]int{}
for vals in list_arr {
aa[vals[idx]]++
}
for chr, count in aa {
if count & 1 == 1 {
result += chr.ascii_str()
break
}
}
}
return result
}
fn find_missed_pmt_3(list string, elem []string) string {
list_arr := list.replace_each(['\n','','\t','']).split(' ')
mut miss_1_arr, mut miss_2_arr, mut miss_3_arr, mut miss_4_arr := []u8{}, []u8{}, []u8{}, []u8{}
mut res1, mut res2, mut res3, mut res4 := '', '', '', ''
for group in list_arr {
for chr in group[0].ascii_str() {miss_1_arr << chr}
for chr in group[1].ascii_str() {miss_2_arr << chr}
for chr in group[2].ascii_str() {miss_3_arr << chr}
for chr in group[3].ascii_str() {miss_4_arr << chr}
}
for chr in elem {
if miss_1_arr.bytestr().count(chr) < 6 {res1 = chr}
if miss_2_arr.bytestr().count(chr) < 6 {res2 = chr}
if miss_3_arr.bytestr().count(chr) < 6 {res3 = chr}
if miss_4_arr.bytestr().count(chr) < 6 {res4 = chr}
}
return res1 + res2 + res3 + res4
}
</syntaxhighlight>
{{out}}
<pre>
DBAC is missing
DBAC is missing
DBAC is missing
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-set}}
{{libheader|Wren-perm}}
<syntaxhighlight lang="wren">import "./set" for Set
import "./perm" for Perm
var missingPerms = Fn.new { |input, perms|
var s1 = Set.new()
s1.addAll(perms)
var perms2 = Perm.list(input).map { |p| p.join() }
var s2 = Set.new()
s2.addAll(perms2)
return s2.except(s1).toList
}
var input = ["A", "B", "C", "D"]
var perms = [
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
]
var missing = missingPerms.call(input, perms)
if (missing.count == 1) {
System.print("The missing permutation is %(missing[0])")
} else {
System.print("There are %(missing.count) missing permutations, namely:\n")
System.print(missing)
}</syntaxhighlight>
{{out}}
<pre>
The missing permutation is DBAC
</pre>
=={{header|XPL0}}==
Line 2,532 ⟶ 3,681:
missperm <missperm.txt
<
int P, I;
[P:= 0;
for I:= 1 to 24-1 do P:= P xor HexIn(1);
HexOut(0, P);
]</
{{out}}
Line 2,546 ⟶ 3,695:
=={{header|zkl}}==
Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution.
<
"DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA",
"DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB");
Utils.Helpers.permute(["A".."D"]).apply("concat").copy().remove(data.xplode());</
Copy creates a read/write list from a read only list.
xplode() pushes all elements of data as parameters to remove.
Line 2,558 ⟶ 3,707:
=={{header|ZX Spectrum Basic}}==
<
20 LET length=LEN l$
30 FOR a= CODE "A" TO CODE "D"
Line 2,571 ⟶ 3,720:
120 NEXT i
130 PRINT x$;" is missing"
140 NEXT d: NEXT c: NEXT b: NEXT a</
|