Find the missing permutation: Difference between revisions
m indented the list. |
PascalABC.NET |
||
(35 intermediate revisions by 20 users not shown) | |||
Line 2: | Line 2: | ||
<pre> |
<pre> |
||
ABCD |
ABCD |
||
CABD |
CABD |
||
ACDB |
ACDB |
||
DACB |
DACB |
||
BCDA |
BCDA |
||
ACBD |
ACBD |
||
ADCB |
ADCB |
||
CDAB |
CDAB |
||
DABC |
DABC |
||
BCAD |
BCAD |
||
CADB |
CADB |
||
CDBA |
CDBA |
||
CBAD |
CBAD |
||
ABDC |
ABDC |
||
ADBC |
ADBC |
||
BDCA |
BDCA |
||
DCBA |
DCBA |
||
BACD |
BACD |
||
BADC |
BADC |
||
BDAC |
BDAC |
||
CBDA |
CBDA |
||
DBCA |
DBCA |
||
DCAB |
DCAB |
||
</pre> |
</pre> |
||
Listed above are all of the permutations of the symbols '''A''', '''B''', '''C''', and '''D''', ''except'' for one permutation that's ''not'' listed. |
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 57: | Line 57: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="11l">V perms = [‘ABCD’, ‘CABD’, ‘ACDB’, ‘DACB’, ‘BCDA’, ‘ACBD’, ‘ADCB’, ‘CDAB’, |
||
‘DABC’, ‘BCAD’, ‘CADB’, ‘CDBA’, ‘CBAD’, ‘ABDC’, ‘ADBC’, ‘BDCA’, |
‘DABC’, ‘BCAD’, ‘CADB’, ‘CDBA’, ‘CBAD’, ‘ABDC’, ‘ADBC’, ‘BDCA’, |
||
‘DCBA’, ‘BACD’, ‘BADC’, ‘BDAC’, ‘CBDA’, ‘DBCA’, ‘DCAB’] |
‘DCBA’, ‘BACD’, ‘BADC’, ‘BDAC’, ‘CBDA’, ‘DBCA’, ‘DCAB’] |
||
Line 71: | Line 71: | ||
L.break |
L.break |
||
print(missing)</ |
print(missing)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 81: | Line 81: | ||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
Very compact version, thanks to the clever [[#Raku|Raku]] "xor" algorithm. |
Very compact version, thanks to the clever [[#Raku|Raku]] "xor" algorithm. |
||
< |
<syntaxhighlight lang="360asm">* Find the missing permutation - 19/10/2015 |
||
PERMMISX CSECT |
PERMMISX CSECT |
||
USING PERMMISX,R15 set base register |
USING PERMMISX,R15 set base register |
||
Line 109: | Line 109: | ||
MISS DC 4XL1'00',C' is missing' buffer |
MISS DC 4XL1'00',C' is missing' buffer |
||
YREGS |
YREGS |
||
END PERMMISX</ |
END PERMMISX</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC is missing</pre> |
<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}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
procedure Missing_Permutations is |
procedure Missing_Permutations is |
||
subtype Permutation_Character is Character range 'A' .. 'D'; |
subtype Permutation_Character is Character range 'A' .. 'D'; |
||
Line 165: | Line 258: | ||
Ada.Text_IO.Put_Line ("Missing Permutation:"); |
Ada.Text_IO.Put_Line ("Missing Permutation:"); |
||
Put (Missing_Permutation); |
Put (Missing_Permutation); |
||
end Missing_Permutations;</ |
end Missing_Permutations;</syntaxhighlight> |
||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
< |
<syntaxhighlight lang="aime">void |
||
paste(record r, index x, text p, integer a) |
paste(record r, index x, text p, integer a) |
||
{ |
{ |
||
Line 201: | Line 294: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>DBAC</pre> |
<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" |
|||
, "ACBD", "ADCB", "CDAB", "DABC", "BCAD" |
|||
, "CADB", "CDBA", "CBAD", "ABDC", "ADBC" |
|||
, "BDCA", "DCBA", "BACD", "BADC", "BDAC" |
|||
, "CBDA", "DBCA", "DCAB" |
|||
); |
|||
# sets b to b XOR v and returns b # |
|||
PRIO XORAB = 1; |
|||
OP XORAB = ( REF BITS b, BITS v )REF BITS: b := b XOR v; |
|||
# 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}}== |
=={{header|AppleScript}}== |
||
Line 211: | Line 349: | ||
Yosemite OS X onwards (uses NSString for sorting): |
Yosemite OS X onwards (uses NSString for sorting): |
||
< |
<syntaxhighlight lang="applescript">use framework "Foundation" -- ( sort ) |
||
--------------- RAREST LETTER IN EACH COLUMN ------------- |
|||
on run |
on run |
||
concat(map(composeList({¬ |
|||
intercalate("", ¬ |
|||
head, ¬ |
|||
minimumBy(comparing(|length|)), ¬ |
|||
group, ¬ |
|||
curry(minimumBy)'s |λ|(comparing(|length|)), ¬ |
|||
sort}), ¬ |
|||
transpose(map(chars, ¬ |
|||
|words|("ABCD CABD ACDB DACB BCDA ACBD " & ¬ |
|||
"ADCB CDAB DABC BCAD CADB CDBA " & ¬ |
|||
"CBAD ABDC ADBC BDCA DCBA BACD " & ¬ |
|||
"BADC BDAC CBDA DBCA DCAB"))))) |
|||
"BADC BDAC CBDA DBCA DCAB"))))) |
|||
--> "DBAC" |
--> "DBAC" |
||
end run |
end run |
||
-- GENERIC FUNCTIONS ---------------------------------------------------------- |
|||
-------------------- GENERIC FUNCTIONS ------------------- |
|||
-- chars :: String -> [String] |
-- chars :: String -> [String] |
||
Line 236: | Line 374: | ||
characters of s |
characters of s |
||
end chars |
end chars |
||
-- Ordering :: (-1 | 0 | 1) |
-- Ordering :: (-1 | 0 | 1) |
||
Line 248: | Line 387: | ||
end if |
end if |
||
end compare |
end compare |
||
-- comparing :: (a -> b) -> (a -> a -> Ordering) |
-- comparing :: (a -> b) -> (a -> a -> Ordering) |
||
Line 258: | Line 398: | ||
end comparing |
end comparing |
||
-- composeAll :: [(a -> a)] -> (a -> a) |
|||
-- composeList :: [(a -> a)] -> (a -> a) |
|||
on composeAll(fs) |
|||
on composeList(fs) |
|||
script |
script |
||
on |λ|(x) |
on |λ|(x) |
||
script |
script go |
||
on |λ|(f, a) |
on |λ|(f, a) |
||
mReturn(f)'s |λ|(a) |
mReturn(f)'s |λ|(a) |
||
end |λ| |
end |λ| |
||
end script |
end script |
||
foldr(go, x, fs) |
|||
foldr(result, x, fs) |
|||
end |λ| |
end |λ| |
||
end script |
end script |
||
end |
end composeList |
||
-- 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 |
|||
-- curry :: (Script|Handler) -> Script |
|||
on curry(f) |
|||
script |
|||
on |λ|(a) |
|||
script |
|||
on |λ|(b) |
|||
|λ|(a, b) of mReturn(f) |
|||
end |λ| |
|||
end script |
|||
end |λ| |
|||
end script |
|||
end curry |
|||
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
||
Line 297: | Line 441: | ||
end tell |
end tell |
||
end foldl |
end foldl |
||
-- foldr :: (b -> a -> a) -> a -> [b] -> a |
-- foldr :: (b -> a -> a) -> a -> [b] -> a |
||
Line 309: | Line 454: | ||
end tell |
end tell |
||
end foldr |
end foldr |
||
-- group :: Eq a => [a] -> [[a]] |
-- group :: Eq a => [a] -> [[a]] |
||
Line 320: | Line 466: | ||
groupBy(eq, xs) |
groupBy(eq, xs) |
||
end group |
end group |
||
-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]] |
-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]] |
||
Line 352: | Line 499: | ||
end if |
end if |
||
end groupBy |
end groupBy |
||
-- head :: [a] -> a |
-- head :: [a] -> a |
||
Line 361: | Line 509: | ||
end if |
end if |
||
end head |
end head |
||
-- intercalate :: Text -> [Text] -> Text |
-- intercalate :: Text -> [Text] -> Text |
||
Line 369: | Line 518: | ||
return strJoined |
return strJoined |
||
end intercalate |
end intercalate |
||
-- length :: [a] -> Int |
-- length :: [a] -> Int |
||
Line 374: | Line 524: | ||
length of xs |
length of xs |
||
end |length| |
end |length| |
||
-- map :: (a -> b) -> [a] -> [b] |
-- map :: (a -> b) -> [a] -> [b] |
||
Line 386: | Line 537: | ||
end tell |
end tell |
||
end map |
end map |
||
-- minimumBy :: (a -> a -> Ordering) -> [a] -> a |
-- minimumBy :: (a -> a -> Ordering) -> [a] -> a |
||
on minimumBy(f |
on minimumBy(f) |
||
script |
|||
if length of xs < 1 then return missing value |
|||
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 |
|||
return v |
|||
end |
end repeat |
||
return v |
|||
end tell |
|||
end |λ| |
|||
end script |
|||
end minimumBy |
end minimumBy |
||
-- Lift 2nd class handler function into 1st class script wrapper |
-- Lift 2nd class handler function into 1st class script wrapper |
||
Line 410: | Line 567: | ||
end if |
end if |
||
end mReturn |
end mReturn |
||
-- sort :: [a] -> [a] |
-- sort :: [a] -> [a] |
||
Line 416: | Line 574: | ||
sortedArrayUsingSelector:"compare:") as list |
sortedArrayUsingSelector:"compare:") as list |
||
end sort |
end sort |
||
-- tail :: [a] -> [a] |
-- tail :: [a] -> [a] |
||
Line 425: | Line 584: | ||
end if |
end if |
||
end tail |
end tail |
||
-- transpose :: [[a]] -> [[a]] |
-- transpose :: [[a]] -> [[a]] |
||
Line 442: | Line 602: | ||
map(column, item 1 of xss) |
map(column, item 1 of xss) |
||
end transpose |
end transpose |
||
-- words :: String -> [String] |
-- words :: String -> [String] |
||
on |words|(s) |
on |words|(s) |
||
words of s |
words of s |
||
end |words|</ |
end |words|</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>"DBAC"</pre> |
<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}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">IncompleteList := "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB" |
||
CompleteList := Perm( "ABCD" ) |
CompleteList := Perm( "ABCD" ) |
||
Line 480: | Line 657: | ||
} |
} |
||
return substr(L, 1, -1) |
return substr(L, 1, -1) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Line 486: | Line 663: | ||
This reads the list of permutations as standard input and outputs the missing one. |
This reads the list of permutations as standard input and outputs the missing one. |
||
< |
<syntaxhighlight lang="awk">{ |
||
split($1,a,""); |
split($1,a,""); |
||
for (i=1;i<=4;++i) { |
for (i=1;i<=4;++i) { |
||
Line 504: | Line 681: | ||
} |
} |
||
print s[1]s[2]s[3]s[4] |
print s[1]s[2]s[3]s[4] |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 511: | Line 688: | ||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM perms$(22), miss&(4) |
||
perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \ |
perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \ |
||
\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \ |
\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \ |
||
Line 522: | Line 699: | ||
NEXT |
NEXT |
||
PRINT $$^miss&(0) " is missing" |
PRINT $$^miss&(0) " is missing" |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 530: | Line 707: | ||
=={{header|Burlesque}}== |
=={{header|Burlesque}}== |
||
< |
<syntaxhighlight lang="burlesque"> |
||
ln"ABCD"r@\/\\ |
ln"ABCD"r@\/\\ |
||
</syntaxhighlight> |
|||
</lang> |
|||
(Feed permutations via STDIN. Uses the naive method). |
(Feed permutations via STDIN. Uses the naive method). |
||
Line 539: | Line 716: | ||
the letters with the lowest frequency: |
the letters with the lowest frequency: |
||
< |
<syntaxhighlight lang="burlesque"> |
||
ln)XXtp)><)F:)<]u[/v\[ |
ln)XXtp)><)F:)<]u[/v\[ |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#define N 4 |
#define N 4 |
||
Line 576: | Line 753: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Missing: DBAC</pre> |
<pre>Missing: DBAC</pre> |
||
Line 583: | Line 760: | ||
===By permutating=== |
===By permutating=== |
||
{{works with|C sharp|C#|2+}} |
{{works with|C sharp|C#|2+}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 623: | Line 800: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
===By xor-ing the values=== |
===By xor-ing the values=== |
||
{{works with|C sharp|C#|3+}} |
{{works with|C sharp|C#|3+}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
using System.Linq; |
using System.Linq; |
||
Line 644: | Line 821: | ||
Console.WriteLine(string.Join("", values.Select(i => (char)i))); |
Console.WriteLine(string.Join("", values.Select(i => (char)i))); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <vector> |
#include <vector> |
||
#include <set> |
#include <set> |
||
Line 685: | Line 862: | ||
std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n")); |
std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n")); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure"> |
||
(use 'clojure.math.combinatorics) |
(use 'clojure.math.combinatorics) |
||
(use 'clojure.set) |
(use 'clojure.set) |
||
Line 695: | Line 872: | ||
(def s1 (apply hash-set (permutations "ABCD"))) |
(def s1 (apply hash-set (permutations "ABCD"))) |
||
(def missing (difference s1 given)) |
(def missing (difference s1 given)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
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. |
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. |
||
< |
<syntaxhighlight lang="clojure">(def abcds ["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" |
||
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA" |
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA" |
||
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"]) |
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"]) |
||
Line 705: | Line 882: | ||
(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst)) |
(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst)) |
||
(->> freqs (map #(v->k % 5)) (apply str) println)</ |
(->> freqs (map #(v->k % 5)) (apply str) println)</syntaxhighlight> |
||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
missing_permutation = (arr) -> |
missing_permutation = (arr) -> |
||
# Find the missing permutation in an array of N! - 1 permutations. |
# Find the missing permutation in an array of N! - 1 permutations. |
||
Line 745: | Line 922: | ||
console.log missing_permutation(arr) |
console.log missing_permutation(arr) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 754: | Line 931: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defparameter *permutations* |
||
'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA" |
'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA" |
||
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB")) |
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB")) |
||
Line 767: | Line 944: | ||
(cons (count letter occurs) letter)) |
(cons (count letter occurs) letter)) |
||
letters)))))) |
letters)))))) |
||
(concatenate 'string (mapcar #'least-occurs (enum (length letters)))))))</ |
(concatenate 'string (mapcar #'least-occurs (enum (length letters)))))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>ROSETTA> (missing-perm *permutations*) |
<pre>ROSETTA> (missing-perm *permutations*) |
||
Line 773: | Line 950: | ||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio, std.string, std.algorithm, std.range, std.conv; |
import std.stdio, std.string, std.algorithm, std.range, std.conv; |
||
Line 815: | Line 992: | ||
perms[0][maxCode - code].write; |
perms[0][maxCode - code].write; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC |
<pre>DBAC |
||
Line 821: | Line 998: | ||
DBAC |
DBAC |
||
DBAC</pre> |
DBAC</pre> |
||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Find_the_missing_permutation#Pascal Pascal]. |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang=text> |
|||
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}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
;; use the obvious methos |
;; use the obvious methos |
||
(lib 'list) ; for (permutations) function |
(lib 'list) ; for (permutations) function |
||
Line 838: | Line 1,050: | ||
(set-substract (make-set all-perms) (make-set perms)) |
(set-substract (make-set all-perms) (make-set perms)) |
||
→ { DBAC } |
→ { DBAC } |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def find_miss_perm(head, perms) do |
def find_miss_perm(head, perms) do |
||
all_permutations(head) -- perms |
all_permutations(head) -- perms |
||
Line 858: | Line 1,070: | ||
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"] |
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"] |
||
IO.inspect RC.find_miss_perm( hd(perms), perms )</ |
IO.inspect RC.find_miss_perm( hd(perms), perms )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 867: | Line 1,079: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
The obvious method. It seems fast enough (no waiting time). |
The obvious method. It seems fast enough (no waiting time). |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
-module( find_missing_permutation ). |
-module( find_missing_permutation ). |
||
Line 884: | Line 1,096: | ||
is_different( [_H] ) -> true; |
is_different( [_H] ) -> true; |
||
is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ). |
is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 892: | Line 1,104: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<syntaxhighlight lang="erre"> |
|||
<lang ERRE> |
|||
PROGRAM MISSING |
PROGRAM MISSING |
||
Line 926: | Line 1,138: | ||
PRINT("Solution is: ";SOL$) |
PRINT("Solution is: ";SOL$) |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 934: | Line 1,146: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
Permutations are read in via STDIN. |
Permutations are read in via STDIN. |
||
< |
<syntaxhighlight lang="factor">USING: io math.combinatorics sequences sets ; |
||
"ABCD" all-permutations lines diff first print</ |
"ABCD" all-permutations lines diff first print</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 947: | Line 1,159: | ||
'''Method:''' Read the permutations in as hexadecimal numbers, exclusive ORing them together gives the answer. |
'''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.) |
(This solution assumes that none of the permutations is defined as a Forth word.) |
||
< |
<syntaxhighlight lang="forth"> hex |
||
ABCD CABD xor ACDB xor DACB xor BCDA xor ACBD xor |
ABCD CABD xor ACDB xor DACB xor BCDA xor ACBD xor |
||
ADCB xor CDAB xor DABC xor BCAD xor CADB xor CDBA xor |
ADCB xor CDAB xor DABC xor BCAD xor CADB xor CDBA xor |
||
Line 953: | Line 1,165: | ||
BADC xor BDAC xor CBDA xor DBCA xor DCAB xor |
BADC xor BDAC xor CBDA xor DBCA xor DCAB xor |
||
cr .( Missing permutation: ) u. |
cr .( Missing permutation: ) u. |
||
decimal</ |
decimal</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Missing permutation: DBAC ok</pre> |
<pre>Missing permutation: DBAC ok</pre> |
||
Line 959: | Line 1,171: | ||
=={{header|Fortran}}== |
=={{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. |
'''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. |
||
< |
<syntaxhighlight lang="fortran">program missing_permutation |
||
implicit none |
implicit none |
||
Line 974: | Line 1,186: | ||
write (*, *) |
write (*, *) |
||
end program missing_permutation</ |
end program missing_permutation</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
Line 980: | Line 1,192: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Simple count=== |
===Simple count=== |
||
< |
<syntaxhighlight lang="freebasic">' version 30-03-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,016: | Line 1,228: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The missing permutation is : DBAC</pre> |
<pre>The missing permutation is : DBAC</pre> |
||
===Add the value's=== |
===Add the value's=== |
||
< |
<syntaxhighlight lang="freebasic">' version 30-03-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,053: | Line 1,265: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
<pre>output is same as the first version</pre> |
<pre>output is same as the first version</pre> |
||
===Using Xor=== |
===Using Xor=== |
||
< |
<syntaxhighlight lang="freebasic">' version 30-03-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,082: | Line 1,294: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
<pre>Output is the same as the first version</pre> |
<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}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap"># our deficient list |
||
L := |
L := |
||
[ "ABCD", "CABD", "ACDB", "DACB", "BCDA", |
[ "ABCD", "CABD", "ACDB", "DACB", "BCDA", |
||
Line 1,102: | Line 1,351: | ||
# convert back to letters |
# convert back to letters |
||
s := "ABCD"; |
s := "ABCD"; |
||
List(v, p -> List(p, i -> s[i]));</ |
List(v, p -> List(p, i -> s[i]));</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Alternate method suggested by task description: |
Alternate method suggested by task description: |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,152: | Line 1,401: | ||
} |
} |
||
fmt.Println(string(b)) |
fmt.Println(string(b)) |
||
}</ |
}</syntaxhighlight> |
||
Xor method suggested by Raku contributor: |
Xor method suggested by Raku contributor: |
||
< |
<syntaxhighlight lang="go">func main() { |
||
b := make([]byte, len(given[0])) |
b := make([]byte, len(given[0])) |
||
for _, p := range given { |
for _, p := range given { |
||
Line 1,162: | Line 1,411: | ||
} |
} |
||
fmt.Println(string(b)) |
fmt.Println(string(b)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} in either case: |
{{out}} in either case: |
||
<pre> |
<pre> |
||
Line 1,170: | Line 1,419: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">def fact = { n -> [1,(1..<(n+1)).inject(1) { prod, i -> prod * i }].max() } |
||
def missingPerms |
def missingPerms |
||
missingPerms = {List elts, List perms -> |
missingPerms = {List elts, List perms -> |
||
Line 1,178: | Line 1,427: | ||
: missingPerms(elts - e, ePerms).collect { [e] + it } |
: missingPerms(elts - e, ePerms).collect { [e] + it } |
||
}.sum() |
}.sum() |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">def e = 'ABCD' as List |
||
def p = ['ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB', 'DABC', 'BCAD', 'CADB', 'CDBA', |
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 } |
'CBAD', 'ABDC', 'ADBC', 'BDCA', 'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'].collect { it as List } |
||
def mp = missingPerms(e, p) |
def mp = missingPerms(e, p) |
||
mp.each { println it }</ |
mp.each { println it }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,194: | Line 1,443: | ||
====Difference between two lists==== |
====Difference between two lists==== |
||
{{works with|GHC|7.10.3}} |
{{works with|GHC|7.10.3}} |
||
< |
<syntaxhighlight lang="haskell">import Data.List ((\\), permutations, nub) |
||
import Control.Monad (join) |
import Control.Monad (join) |
||
Line 1,230: | Line 1,479: | ||
main :: IO () |
main :: IO () |
||
main = print $ missingPerm deficientPermsList</ |
main = print $ missingPerm deficientPermsList</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>["DBAC"]</pre> |
<pre>["DBAC"]</pre> |
||
Line 1,237: | Line 1,486: | ||
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). |
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). |
||
< |
<syntaxhighlight lang="haskell">import Data.List (minimumBy, group, sort, transpose) |
||
import Data.Ord (comparing) |
import Data.Ord (comparing) |
||
Line 1,273: | Line 1,522: | ||
main :: IO () |
main :: IO () |
||
main = print $ missingPerm deficientPermsList</ |
main = print $ missingPerm deficientPermsList</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>"DBAC"</pre> |
<pre>"DBAC"</pre> |
||
Line 1,281: | Line 1,530: | ||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<syntaxhighlight lang="haskell">import Data.Char (chr, ord) |
||
import Data.Bits (xor) |
import Data.Bits (xor) |
||
Line 1,315: | Line 1,564: | ||
main :: IO () |
main :: IO () |
||
main = putStrLn $ missingPerm deficientPermsList</ |
main = putStrLn $ missingPerm deficientPermsList</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<syntaxhighlight lang="icon">link strings # for permutes |
||
procedure main() |
procedure main() |
||
Line 1,331: | Line 1,580: | ||
write("The difference is : ") |
write("The difference is : ") |
||
every write(!givens, " ") |
every write(!givens, " ") |
||
end</ |
end</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="icon">every x := permutes("ABCD") do # generate all permutations |
||
if member(givens,x) then delete(givens,x) # remove givens as they are generated |
if member(givens,x) then delete(givens,x) # remove givens as they are generated |
||
else insert(givens,x) # add back any not given</ |
else insert(givens,x) # add back any not given</syntaxhighlight> |
||
A still more efficient version is: |
A still more efficient version is: |
||
< |
<syntaxhighlight lang="icon">link strings |
||
procedure main() |
procedure main() |
||
Line 1,351: | Line 1,600: | ||
if not member(givens, p) then write(p) |
if not member(givens, p) then write(p) |
||
end</ |
end</syntaxhighlight> |
||
{{libheader|Icon Programming Library}} |
{{libheader|Icon Programming Library}} |
||
Line 1,358: | Line 1,607: | ||
=={{header|J}}== |
=={{header|J}}== |
||
'''Solution:''' |
'''Solution:''' |
||
< |
<syntaxhighlight lang="j">permutations=: A.~ i.@!@# |
||
missingPerms=: -.~ permutations @ {.</ |
missingPerms=: -.~ permutations @ {.</syntaxhighlight> |
||
'''Use:''' |
'''Use:''' |
||
<pre>data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA' |
<pre>data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA' |
||
Line 1,371: | Line 1,620: | ||
Or the above could be a single definition that works the same way: |
Or the above could be a single definition that works the same way: |
||
< |
<syntaxhighlight lang="j">missingPerms=: -.~ (A.~ i.@!@#) @ {. </syntaxhighlight> |
||
Or the equivalent explicit (cf. tacit above) definition: |
Or the equivalent explicit (cf. tacit above) definition: |
||
< |
<syntaxhighlight lang="j">missingPerms=: monad define |
||
item=. {. y |
item=. {. y |
||
y -.~ item A.~ i.! #item |
y -.~ item A.~ i.! #item |
||
)</ |
)</syntaxhighlight> |
||
Or, the solution could be obtained without defining an independent program: |
Or, the solution could be obtained without defining an independent program: |
||
< |
<syntaxhighlight lang="j"> data -.~ 'ABCD' A.~ i.!4 |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
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. |
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,388: | Line 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: |
Yet another alternative expression, which uses parentheses instead of the [http://www.jsoftware.com/help/dictionary/d220v.htm passive operator] (<code>~</code>), would be: |
||
< |
<syntaxhighlight lang="j"> ((i.!4) A. 'ABCD') -. data |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable: |
Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable: |
||
< |
<syntaxhighlight lang="j"> 'ABCD'{~,I.@(= <./)@(#/.~)@('ABCD' , ])"1 |:perms |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
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?) |
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: |
We could use parity, as suggested in the task hints: |
||
< |
<syntaxhighlight lang="j"> ,(~.#~2|(#/.~))"1|:data |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
We could use arithmetic, as suggested in the task hints: |
We could use arithmetic, as suggested in the task hints: |
||
< |
<syntaxhighlight lang="j"> ({.data){~|(->./)+/({.i.])data |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
Line 1,410: | Line 1,659: | ||
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]] |
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]] |
||
< |
<syntaxhighlight lang="java">import java.util.ArrayList; |
||
import com.google.common.base.Joiner; |
import com.google.common.base.Joiner; |
||
Line 1,429: | Line 1,678: | ||
System.out.println(joiner.join(cs)); |
System.out.println(joiner.join(cs)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,436: | Line 1,685: | ||
Alternate version, based on checksumming each position: |
Alternate version, based on checksumming each position: |
||
< |
<syntaxhighlight lang="java">public class FindMissingPermutation |
||
{ |
{ |
||
public static void main(String[] args) |
public static void main(String[] args) |
||
Line 1,459: | Line 1,708: | ||
System.out.println("Missing permutation: " + missingPermutation.toString()); |
System.out.println("Missing permutation: " + missingPermutation.toString()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 1,467: | Line 1,716: | ||
The permute() function taken from http://snippets.dzone.com/posts/show/1032 |
The permute() function taken from http://snippets.dzone.com/posts/show/1032 |
||
< |
<syntaxhighlight lang="javascript">permute = function(v, m){ //v1.0 |
||
for(var p = -1, j, k, f, r, l = v.length, q = 1, i = l + 1; --i; q *= i); |
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; |
for(x = [new Array(l), new Array(l), new Array(l), new Array(l)], j = q, k = l + 1, i = -1; |
||
Line 1,486: | Line 1,735: | ||
missing = all.filter(function(elem) {return list.indexOf(elem) == -1}); |
missing = all.filter(function(elem) {return list.indexOf(elem) == -1}); |
||
print(missing); // ==> DBAC</ |
print(missing); // ==> DBAC</syntaxhighlight> |
||
====Functional==== |
====Functional==== |
||
< |
<syntaxhighlight lang="javascript">(function (strList) { |
||
// [a] -> [[a]] |
// [a] -> [[a]] |
||
Line 1,529: | Line 1,778: | ||
'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\ |
'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\ |
||
CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB' |
CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB' |
||
);</ |
);</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">["DBAC"]</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
====Statistical==== |
====Statistical==== |
||
=====Using a dictionary===== |
=====Using a dictionary===== |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,570: | Line 1,819: | ||
// --> 'DBAC' |
// --> 'DBAC' |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,578: | Line 1,827: | ||
=====Composing functional primitives===== |
=====Composing functional primitives===== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,673: | Line 1,922: | ||
// -> "DBAC" |
// -> "DBAC" |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
Line 1,679: | Line 1,928: | ||
====XOR==== |
====XOR==== |
||
Folding an xor operator over the list of character codes: |
Folding an xor operator over the list of character codes: |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,717: | Line 1,966: | ||
return main() |
return main() |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
Line 1,741: | Line 1,990: | ||
If your version of jq has transpose/0, the definition given here |
If your version of jq has transpose/0, the definition given here |
||
(which is the same as in [[Matrix_Transpose#jq]]) may be omitted. |
(which is the same as in [[Matrix_Transpose#jq]]) may be omitted. |
||
< |
<syntaxhighlight lang="jq">def transpose: |
||
if (.[0] | length) == 0 then [] |
if (.[0] | length) == 0 then [] |
||
else [map(.[0])] + (map(.[1:]) | transpose) |
else [map(.[0])] + (map(.[1:]) | transpose) |
||
Line 1,762: | Line 2,011: | ||
# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]): |
# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]): |
||
def encode_string: [explode[] - 65];</ |
def encode_string: [explode[] - 65];</syntaxhighlight> |
||
'''The task''': |
'''The task''': |
||
< |
<syntaxhighlight lang="jq">map(encode_string) | transpose | map(parities | decode) | join("")</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="sh">$ jq -R . Find_the_missing_permutation.txt | jq -s -f Find_the_missing_permutation.jq |
||
"DBAC"</ |
"DBAC"</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 1,776: | Line 2,025: | ||
=== Obvious method === |
=== Obvious method === |
||
Calculate all possible permutations and return the first not included in the array. |
Calculate all possible permutations and return the first not included in the array. |
||
< |
<syntaxhighlight lang="julia">using BenchmarkTools, Combinatorics |
||
function missingperm(arr::Vector) |
function missingperm(arr::Vector) |
||
Line 1,788: | Line 2,037: | ||
"CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", |
"CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", |
||
"CBDA", "DBCA", "DCAB"] |
"CBDA", "DBCA", "DCAB"] |
||
@show missingperm(arr)</ |
@show missingperm(arr)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,795: | Line 2,044: | ||
=== Alternative method 1 === |
=== Alternative method 1 === |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">function missingperm1(arr::Vector{<:AbstractString}) |
||
missperm = string() |
missperm = string() |
||
for pos in 1:length(arr[1]) |
for pos in 1:length(arr[1]) |
||
Line 1,807: | Line 2,056: | ||
return missperm |
return missperm |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=== Alternative method 2 === |
=== Alternative method 2 === |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="julia">function missingperm2(arr::Vector) |
||
len = length(arr[1]) |
len = length(arr[1]) |
||
xorval = zeros(UInt8, len) |
xorval = zeros(UInt8, len) |
||
Line 1,827: | Line 2,076: | ||
@btime missingperm1(arr) |
@btime missingperm1(arr) |
||
@btime missingperm2(arr) |
@btime missingperm2(arr) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
missingperm(arr) = "DBAC" |
missingperm(arr) = "DBAC" |
||
Line 1,838: | Line 2,087: | ||
=={{header|K}}== |
=={{header|K}}== |
||
< |
<syntaxhighlight lang="k"> split:{1_'(&x=y)_ x:y,x} |
||
g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB") |
g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB") |
||
Line 1,861: | Line 2,110: | ||
p2@&~p2 _lin p |
p2@&~p2 _lin p |
||
"DBAC"</ |
"DBAC"</syntaxhighlight> |
||
Alternative approach: |
Alternative approach: |
||
< |
<syntaxhighlight lang="k"> |
||
table:{b@<b:(x@*:'a),'#:'a:=x} |
table:{b@<b:(x@*:'a),'#:'a:=x} |
||
,/"ABCD"@&:'{5=(table p[;x])[;1]}'!4 |
,/"ABCD"@&:'{5=(table p[;x])[;1]}'!4 |
||
"DBAC"</ |
"DBAC"</syntaxhighlight> |
||
Third approach (where p is the given set of permutations): |
Third approach (where p is the given set of permutations): |
||
<syntaxhighlight lang="k"> |
|||
<lang K> |
|||
,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p |
,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
fun <T> permute(input: List<T>): List<List<T>> { |
fun <T> permute(input: List<T>): List<List<T>> { |
||
Line 1,908: | Line 2,157: | ||
for (perm in missing) println(perm.joinToString("")) |
for (perm in missing) println(perm.joinToString("")) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,917: | Line 2,166: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight |
Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight |
||
< |
<syntaxhighlight lang="lua">local permute, tablex = require("pl.permute"), require("pl.tablex") |
||
local permList, pStr = { |
local permList, pStr = { |
||
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", |
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", |
||
Line 1,926: | Line 2,175: | ||
pStr = table.concat(perm) |
pStr = table.concat(perm) |
||
if not tablex.find(permList, pStr) then print(pStr) end |
if not tablex.find(permList, pStr) then print(pStr) end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
=={{header|Maple}}== |
=={{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(): |
perm := table(): |
||
for letter in "ABCD" do |
for letter in "ABCD" do |
||
Line 1,941: | Line 2,190: | ||
end do: |
end do: |
||
end do: |
end do: |
||
print(StringTools:-Join(ListTools:-Flatten([indices(perm)], 4)[sort(map(x->60-x, ListTools:-Flatten([entries(perm)],4)),'output=permutation')], "")):</ |
print(StringTools:-Join(ListTools:-Flatten([indices(perm)], 4)[sort(map(x->60-x, ListTools:-Flatten([entries(perm)],4)),'output=permutation')], "")):</syntaxhighlight> |
||
{{Out|Output}} |
{{Out|Output}} |
||
<pre>"DBAC"</pre> |
<pre>"DBAC"</pre> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ProvidedSet = {"ABCD" , "CABD" , "ACDB" , "DACB" , "BCDA" , "ACBD", |
||
"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC", |
"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC", |
||
"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"}; |
"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"}; |
||
Line 1,953: | Line 2,202: | ||
->{"DBAC"}</ |
->{"DBAC"}</syntaxhighlight> |
||
=={{header|MATLAB}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="matlab">function perm = findMissingPerms(list) |
||
permsList = perms(list(1,:)); %Generate all permutations of the 4 letters |
permsList = perms(list(1,:)); %Generate all permutations of the 4 letters |
||
Line 1,984: | Line 2,233: | ||
end %for |
end %for |
||
end %fingMissingPerms</ |
end %fingMissingPerms</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="matlab">>> list = ['ABCD'; |
||
'CABD'; |
'CABD'; |
||
'ACDB'; |
'ACDB'; |
||
Line 2,041: | Line 2,290: | ||
ans = |
ans = |
||
DBAC</ |
DBAC</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import strutils |
||
proc missingPermutation(arr): string = |
proc missingPermutation(arr: openArray[string]): string = |
||
result = "" |
result = "" |
||
if arr.len == 0: return |
if arr.len == 0: return |
||
if arr.len == 1: return arr[0][1] & arr[0][0] |
if arr.len == 1: return arr[0][1] & arr[0][0] |
||
for pos in 0 .. |
for pos in 0 ..< arr[0].len: |
||
var s: set[char] = {} |
var s: set[char] = {} |
||
for permutation in arr: |
for permutation in arr: |
||
Line 2,061: | Line 2,310: | ||
const given = """ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
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""". |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB""".splitWhiteSpace() |
||
echo missingPermutation(given)</ |
echo missingPermutation(given)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
Line 2,070: | Line 2,319: | ||
some utility functions: |
some utility functions: |
||
< |
<syntaxhighlight lang="ocaml">(* insert x at all positions into li and return the list of results *) |
||
let rec insert x = function |
let rec insert x = function |
||
| [] -> [[x]] |
| [] -> [[x]] |
||
Line 2,087: | Line 2,336: | ||
(* convert a char list to a string *) |
(* convert a char list to a string *) |
||
let string_of_chars cl = |
let string_of_chars cl = |
||
String.concat "" (List.map (String.make 1) cl)</ |
String.concat "" (List.map (String.make 1) cl)</syntaxhighlight> |
||
resolve the task: |
resolve the task: |
||
< |
<syntaxhighlight lang="ocaml">let deficient_perms = [ |
||
"ABCD";"CABD";"ACDB";"DACB"; |
"ABCD";"CABD";"ACDB";"DACB"; |
||
"BCDA";"ACBD";"ADCB";"CDAB"; |
"BCDA";"ACBD";"ADCB";"CDAB"; |
||
Line 2,106: | Line 2,355: | ||
let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms |
let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms |
||
let () = List.iter print_endline results</ |
let () = List.iter print_endline results</syntaxhighlight> |
||
Alternate method : if we had all permutations, |
Alternate method : if we had all permutations, |
||
Line 2,114: | Line 2,363: | ||
of the number of occurences of each letter. |
of the number of occurences of each letter. |
||
The following program works with permutations of at least 3 letters: |
The following program works with permutations of at least 3 letters: |
||
< |
<syntaxhighlight lang="ocaml">let array_of_perm s = |
||
let n = String.length s in |
let n = String.length s in |
||
Array.init n (fun i -> int_of_char s.[i] - 65);; |
Array.init n (fun i -> int_of_char s.[i] - 65);; |
||
Line 2,143: | Line 2,392: | ||
find_missing deficient_perms;; |
find_missing deficient_perms;; |
||
(* - : string = "DBAC" *)</ |
(* - : string = "DBAC" *)</syntaxhighlight> |
||
=={{header|Octave}}== |
=={{header|Octave}}== |
||
< |
<syntaxhighlight lang="octave">given = [ 'ABCD';'CABD';'ACDB';'DACB'; ... |
||
'BCDA';'ACBD';'ADCB';'CDAB'; ... |
'BCDA';'ACBD';'ADCB';'CDAB'; ... |
||
'DABC';'BCAD';'CADB';'CDBA'; ... |
'DABC';'BCAD';'CADB';'CDBA'; ... |
||
Line 2,160: | Line 2,409: | ||
bits(there) = 0; |
bits(there) = 0; |
||
missing = dec2base(find(bits)-1,'ABCD') |
missing = dec2base(find(bits)-1,'ABCD') |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Using constraint programming for this problem may be a bit overkill... |
Using constraint programming for this problem may be a bit overkill... |
||
< |
<syntaxhighlight lang="oz">declare |
||
GivenPermutations = |
GivenPermutations = |
||
["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA" |
["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA" |
||
Line 2,183: | Line 2,432: | ||
{System.showInfo "Missing: "#P} |
{System.showInfo "Missing: "#P} |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">v=["ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB","DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA","DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"]; |
||
v=apply(u->permtonum(apply(n->n-64,Vec(Vecsmall(u)))),v); |
v=apply(u->permtonum(apply(n->n-64,Vec(Vecsmall(u)))),v); |
||
t=numtoperm(4, binomial(4!,2)-sum(i=1,#v,v[i])); |
t=numtoperm(4, binomial(4!,2)-sum(i=1,#v,v[i])); |
||
Strchr(apply(n->n+64,t))</ |
Strchr(apply(n->n+64,t))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = "DBAC"</pre> |
<pre>%1 = "DBAC"</pre> |
||
Line 2,195: | Line 2,444: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
like [[c]], summation, and [[Raku]] XORing |
like [[c]], summation, and [[Raku]] XORing |
||
< |
<syntaxhighlight lang="pascal">program MissPerm; |
||
{$MODE DELPHI} //for result |
{$MODE DELPHI} //for result |
||
Line 2,240: | Line 2,489: | ||
For row := low(tcol) to High(tcol) do |
For row := low(tcol) to High(tcol) do |
||
IF SumElemCol[col,row]=fibN_1 then |
IF SumElemCol[col,row]=fibN_1 then |
||
result[col]:= |
result[col]:= ansichar(row+chOfs); |
||
end; |
end; |
||
Line 2,251: | Line 2,500: | ||
For row := low(tmissPerm) to High(tmissPerm) do |
For row := low(tmissPerm) to High(tmissPerm) do |
||
For col := low(tcol) to High(tcol) do |
For col := low(tcol) to High(tcol) do |
||
result[col] := |
result[col] := ansichar(ord(result[col]) XOR ord(Given_Permutations[row,col])); |
||
end; |
end; |
||
Line 2,257: | Line 2,506: | ||
writeln(CountOccurences,' is missing'); |
writeln(CountOccurences,' is missing'); |
||
writeln(CheckXOR,' is missing'); |
writeln(CheckXOR,' is missing'); |
||
end.</ |
end.</syntaxhighlight>{{out}}<pre>DBAC is missing |
||
DBAC is missing</pre> |
DBAC is missing</pre> |
||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
begin |
|||
var s := ''' |
|||
ABCD |
|||
CABD |
|||
ACDB |
|||
DACB |
|||
BCDA |
|||
ACBD |
|||
ADCB |
|||
CDAB |
|||
DABC |
|||
BCAD |
|||
CADB |
|||
CDBA |
|||
CBAD |
|||
ABDC |
|||
ADBC |
|||
BDCA |
|||
DCBA |
|||
BACD |
|||
BADC |
|||
BDAC |
|||
CBDA |
|||
DBCA |
|||
DCAB |
|||
'''; |
|||
var perms := s.ToLines; |
|||
Print(('ABCD'.Permutations.ToHashSet - perms.ToHashSet).First); |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
DBAC |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Line 2,265: | Line 2,551: | ||
the first missing rotation is the target. |
the first missing rotation is the target. |
||
< |
<syntaxhighlight lang="perl">sub check_perm { |
||
my %hash; @hash{@_} = (); |
my %hash; @hash{@_} = (); |
||
for my $s (@_) { exists $hash{$_} or return $_ |
for my $s (@_) { exists $hash{$_} or return $_ |
||
Line 2,274: | Line 2,560: | ||
@perms = qw(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
@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); |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB); |
||
print check_perm(@perms), "\n";</ |
print check_perm(@perms), "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
== |
===Alternates=== |
||
All cases take permutation list on STDIN or as filename on command line |
|||
<lang Phix>constant perms = {"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", |
|||
<br><br> |
|||
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", |
|||
If the string XOR was of all the permutations, the result would be a string of nulls "\0", |
|||
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"} |
|||
since one is missing, it is the result of XOR of all the rest :) |
|||
<syntaxhighlight lang="perl">print eval join '^', map "'$_'", <>;</syntaxhighlight> |
|||
-- 1: sum of letters |
|||
or if you don't like eval... |
|||
sequence r = repeat(0,4) |
|||
<syntaxhighlight lang="perl">$\ ^= $_ while <>; |
|||
for i=1 to length(perms) do |
|||
print '';</syntaxhighlight> |
|||
r = sq_add(r,perms[i]) |
|||
Every permutation has a "reverse", just take all reverses and remove the "normals". |
|||
end for |
|||
<syntaxhighlight lang="perl">local $_ = join '', <>; |
|||
r = sq_sub(max(r)+'A',r) |
|||
my %h = map { $_, '' } reverse =~ /\w+/g; |
|||
puts(1,r&'\n') |
|||
delete @h{ /\w+/g }; |
|||
-- based on the notion that missing = sum(full)-sum(partial) would be true, |
|||
print %h, "\n";</syntaxhighlight> |
|||
-- and that sum(full) would be like {M,M,M,M} rather than a mix of numbers. |
|||
-- the final step is equivalent to eg {1528,1530,1531,1529} |
|||
-- max-r[i] -> { 3, 1, 0, 2} |
|||
-- to chars -> { D, B, A, C} |
|||
-- (but obviously both done in one line) |
|||
=={{header|Phix}}== |
|||
-- 2: the xor trick |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
r = repeat(0,4) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
for i=1 to length(perms) do |
|||
<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> |
|||
r = sq_xor_bits(r,perms[i]) |
|||
<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> |
|||
end for |
|||
<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> |
|||
puts(1,r&'\n') |
|||
-- (relies on the missing chars being present an odd number of times, non-missing chars an even number of times) |
|||
<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> |
|||
-- 3: find least frequent letters |
|||
<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> |
|||
r = " " |
|||
<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> |
|||
for i=1 to length(r) do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
sequence count = repeat(0,4) |
|||
<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> |
|||
for j=1 to length(perms) do |
|||
<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> |
|||
count[perms[j][i]-'A'+1] += 1 |
|||
<span style="color: #000080;font-style:italic;">-- based on the notion that missing = sum(full)-sum(partial) would be true, |
|||
end for |
|||
-- and that sum(full) would be like {M,M,M,M} rather than a mix of numbers. |
|||
r[i] = smallest(count,1)+'A'-1 |
|||
-- the final step is equivalent to eg {1528,1530,1531,1529} |
|||
end for |
|||
-- max-r[i] -> { 3, 1, 0, 2} |
|||
puts(1,r&'\n') |
|||
-- to chars -> { D, B, A, C} |
|||
-- (relies on the assumption that a full set would have each letter occurring the same number of times in each position) |
|||
-- (but obviously both done in one line) |
|||
-- (smallest(count,1) returns the index position of the smallest, rather than it's value) |
|||
-- |
-- 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> |
|||
for i=1 to factorial(4) do |
|||
<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> |
|||
r = permute(i,"ABCD") |
|||
<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> |
|||
if not find(r,perms) then exit end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<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> |
|||
puts(1,r&'\n') |
|||
<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) |
|||
-- (relies on brute force(!) - but this is the only method that could be made to cope with >1 omission)</lang> |
|||
-- 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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,335: | Line 2,640: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
$finalres = Array(); |
$finalres = Array(); |
||
function permut($arr,$result=array()){ |
function permut($arr,$result=array()){ |
||
Line 2,355: | Line 2,660: | ||
permut($given); |
permut($given); |
||
print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC ) |
print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(setq *PermList |
||
(mapcar chop |
(mapcar chop |
||
(quote |
(quote |
||
Line 2,372: | Line 2,852: | ||
(rot L) ) |
(rot L) ) |
||
(unless (member Lst *PermList) # Check |
(unless (member Lst *PermList) # Check |
||
(prinl Lst) ) ) ) )</ |
(prinl Lst) ) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC</pre> |
<pre>DBAC</pre> |
||
Line 2,379: | Line 2,859: | ||
{{works with|PowerShell|4.0}} |
{{works with|PowerShell|4.0}} |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function permutation ($array) { |
function permutation ($array) { |
||
function generate($n, $array, $A) { |
function generate($n, $array, $A) { |
||
Line 2,436: | Line 2,916: | ||
) |
) |
||
$perm | where{-not $find.Contains($_)} |
$perm | where{-not $find.Contains($_)} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 2,443: | Line 2,923: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Procedure in_List(in.s) |
||
Define.i i, j |
Define.i i, j |
||
Define.s a |
Define.s a |
||
Line 2,481: | Line 2,961: | ||
Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA" |
Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA" |
||
Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB" |
Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB" |
||
EndDataSection</ |
EndDataSection</syntaxhighlight> |
||
Based on the [[Permutations#PureBasic|Permutations]] task, |
Based on the [[Permutations#PureBasic|Permutations]] task, |
||
the solution could be: |
the solution could be: |
||
< |
<syntaxhighlight lang="purebasic">If OpenConsole() |
||
NewList a.s() |
NewList a.s() |
||
findPermutations(a(), "ABCD", 4) |
findPermutations(a(), "ABCD", 4) |
||
Line 2,499: | Line 2,979: | ||
Print(#CRLF$ + "Press ENTER to exit"): Input() |
Print(#CRLF$ + "Press ENTER to exit"): Input() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: Calculate difference when compared to all permutations=== |
===Python: Calculate difference when compared to all permutations=== |
||
{{works with|Python|2.6+}} |
{{works with|Python|2.6+}} |
||
< |
<syntaxhighlight lang="python">from itertools import permutations |
||
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
||
Line 2,511: | Line 2,991: | ||
allPerms = [''.join(x) for x in permutations(given[0])] |
allPerms = [''.join(x) for x in permutations(given[0])] |
||
missing = list(set(allPerms) - set(given)) # ['DBAC']</ |
missing = list(set(allPerms) - set(given)) # ['DBAC']</syntaxhighlight> |
||
===Python:Counting lowest frequency character at each position=== |
===Python:Counting lowest frequency character at each position=== |
||
Line 2,517: | Line 2,997: | ||
i.e. it never needs to generate the full set of expected permutations. |
i.e. it never needs to generate the full set of expected permutations. |
||
< |
<syntaxhighlight lang="python"> |
||
def missing_permutation(arr): |
def missing_permutation(arr): |
||
"Find the missing permutation in an array of N! - 1 permutations." |
"Find the missing permutation in an array of N! - 1 permutations." |
||
Line 2,548: | Line 3,028: | ||
print missing_permutation(given) |
print missing_permutation(given) |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Python:Counting lowest frequency character at each position: functional=== |
===Python:Counting lowest frequency character at each position: functional=== |
||
Uses the same method as explained directly above, |
Uses the same method as explained directly above, |
||
but calculated in a more functional manner: |
but calculated in a more functional manner: |
||
< |
<syntaxhighlight lang="python">>>> from collections import Counter |
||
>>> given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
>>> 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() |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'''.split() |
||
>>> ''.join(Counter(x).most_common()[-1][0] for x in zip(*given)) |
>>> ''.join(Counter(x).most_common()[-1][0] for x in zip(*given)) |
||
'DBAC' |
'DBAC' |
||
>>> </ |
>>> </syntaxhighlight> |
||
;Explanation |
;Explanation |
||
Line 2,567: | Line 3,047: | ||
created by the call to <code>most_common()</code> |
created by the call to <code>most_common()</code> |
||
is the least common character. |
is the least common character. |
||
< |
<syntaxhighlight lang="python">>>> from pprint import pprint as pp |
||
>>> pp(list(zip(*given)), width=120) |
>>> 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'), |
[('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,584: | Line 3,064: | ||
>>> ''.join([Counter(x).most_common()[-1][0] for x in zip(*given)]) |
>>> ''.join([Counter(x).most_common()[-1][0] for x in zip(*given)]) |
||
'DBAC' |
'DBAC' |
||
>>> </ |
>>> </syntaxhighlight> |
||
===Python:Folding XOR over the set of strings=== |
===Python:Folding XOR over the set of strings=== |
||
Surfacing the missing bits: |
Surfacing the missing bits: |
||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
< |
<syntaxhighlight lang="python">'''Find the missing permutation''' |
||
from functools import reduce |
from functools import reduce |
||
Line 2,611: | Line 3,091: | ||
[0, 0, 0, 0] |
[0, 0, 0, 0] |
||
) |
) |
||
]))</ |
]))</syntaxhighlight> |
||
{{Out}} |
{{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> |
<pre>DBAC</pre> |
||
=={{header|R}}== |
=={{header|R}}== |
||
This uses the "combinat" package, which is a standard R package: |
This uses the "combinat" package, which is a standard R package: |
||
<lang> |
<syntaxhighlight lang="text"> |
||
library(combinat) |
library(combinat) |
||
Line 2,630: | Line 3,129: | ||
setdiff(perms3, incomplete) |
setdiff(perms3, incomplete) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,638: | Line 3,137: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
Line 2,674: | Line 3,173: | ||
c)) |
c)) |
||
;; -> '(D B A C) |
;; -> '(D B A C) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<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>; |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>; |
||
my @perms = <A B C D>.permutations.map: *.join; |
my @perms = <A B C D>.permutations.map: *.join; |
||
.say when none(@givens) for @perms;</ |
.say when none(@givens) for @perms;</syntaxhighlight> |
||
{{out}}<pre>DBAC</pre> |
{{out}}<pre>DBAC</pre> |
||
Of course, all of these solutions are working way too hard, |
Of course, all of these solutions are working way too hard, |
||
when you can just xor all the bits, |
when you can just xor all the bits, |
||
and the missing one will just pop right out: |
and the missing one will just pop right out: |
||
<lang |
<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>;</ |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>;</syntaxhighlight> |
||
{{out}}<pre>DBAC</pre> |
{{out}}<pre>DBAC</pre> |
||
=={{header|RapidQ}}== |
=={{header|RapidQ}}== |
||
<syntaxhighlight lang="vb"> |
|||
<lang vb> |
|||
Dim PList as QStringList |
Dim PList as QStringList |
||
PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB" |
PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB" |
||
Line 2,718: | Line 3,217: | ||
showmessage MPerm |
showmessage MPerm |
||
'= DBAC |
'= DBAC |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds one or more missing permutations from an internal list & displays them.*/ |
||
list= 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA', |
list= 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA', |
||
"DCBA BACD BADC BDAC CBDA DBCA DCAB" /*list that is missing one permutation.*/ |
"DCBA BACD BADC BDAC CBDA DBCA DCAB" /*list that is missing one permutation.*/ |
||
Line 2,749: | Line 3,248: | ||
call permSet ?+1 /*call self recursively. */ |
call permSet ?+1 /*call self recursively. */ |
||
end /*x*/ |
end /*x*/ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 2,756: | Line 3,255: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="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" |
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,770: | Line 3,269: | ||
next |
next |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,778: | Line 3,277: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{works with|Ruby|2.0+}} |
{{works with|Ruby|2.0+}} |
||
< |
<syntaxhighlight lang="ruby">given = %w{ |
||
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA |
||
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB |
||
Line 2,785: | Line 3,284: | ||
all = given[0].chars.permutation.collect(&:join) |
all = given[0].chars.permutation.collect(&:join) |
||
puts "missing: #{all - given}"</ |
puts "missing: #{all - given}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,792: | Line 3,291: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">list$ = "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB" |
||
for a = asc("A") to asc("D") |
for a = asc("A") to asc("D") |
||
Line 2,807: | Line 3,306: | ||
next c |
next c |
||
next b |
next b |
||
next a</ |
next a</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>DBAC missing</pre> |
<pre>DBAC missing</pre> |
||
Line 2,814: | Line 3,313: | ||
{{trans|Go}} |
{{trans|Go}} |
||
Xor method suggested by Raku contributor: |
Xor method suggested by Raku contributor: |
||
< |
<syntaxhighlight lang="rust">const GIVEN_PERMUTATIONS: [&str; 23] = [ |
||
"ABCD", |
"ABCD", |
||
"CABD", |
"CABD", |
||
Line 2,853: | Line 3,352: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,862: | Line 3,361: | ||
{{libheader|Scala}} |
{{libheader|Scala}} |
||
{{works with|Scala|2.8}} |
{{works with|Scala|2.8}} |
||
< |
<syntaxhighlight lang="scala">def fat(n: Int) = (2 to n).foldLeft(1)(_*_) |
||
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else { |
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else { |
||
val n = a.size |
val n = a.size |
||
Line 2,901: | Line 3,400: | ||
DBCA |
DBCA |
||
DCAB""".stripMargin.split("\n") |
DCAB""".stripMargin.split("\n") |
||
println(findMissingPerm(perms(0), perms))</ |
println(findMissingPerm(perms(0), perms))</syntaxhighlight> |
||
===Scala 2.9.x=== |
===Scala 2.9.x=== |
||
{{works with|Scala|2.9.1}} |
{{works with|Scala|2.9.1}} |
||
< |
<syntaxhighlight lang="scala">println("missing perms: "+("ABCD".permutations.toSet |
||
--"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))</ |
--"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))</syntaxhighlight> |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func string: missingPermutation (in array string: perms) is func |
const func string: missingPermutation (in array string: perms) is func |
||
Line 2,941: | Line 3,440: | ||
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", |
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", |
||
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"))); |
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"))); |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,950: | Line 3,449: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">func check_perm(arr) { |
||
var hash = Hash() |
var hash = Hash() |
||
hash.set_keys(arr...) |
hash.set_keys(arr...) |
||
Line 2,964: | Line 3,463: | ||
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB) |
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB) |
||
say check_perm(perms)</ |
say check_perm(perms)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
DBAC |
DBAC |
||
</pre> |
</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}}== |
=={{header|Tcl}}== |
||
{{tcllib|struct::list}} |
{{tcllib|struct::list}} |
||
< |
<syntaxhighlight lang="tcl"> |
||
package require struct::list |
package require struct::list |
||
Line 2,986: | Line 3,521: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Uiua}}== |
|||
Counts occurrences of each char by column and spots the outliers. |
|||
<syntaxhighlight lang="uiua"> |
|||
Perms ← ⊜∘⊸≠@ "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB" |
|||
/⊂≡(▽-⟜/↥:⊕⊃⊢⧻⊛.)⍉ Perms |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
"DBAC" |
|||
</pre> |
|||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
Line 2,992: | Line 3,538: | ||
and needn't be reinvented, but its definition is shown here in the interest of |
and needn't be reinvented, but its definition is shown here in the interest of |
||
comparison with other solutions. |
comparison with other solutions. |
||
< |
<syntaxhighlight lang="ursala">permutations = ~&itB^?a\~&aNC *=ahPfatPRD refer ^C/~&a ~&ar&& ~&arh2falrtPXPRD</syntaxhighlight> |
||
The <code>~&j</code> operator computes set differences. |
The <code>~&j</code> operator computes set differences. |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#show+ |
#show+ |
||
Line 3,022: | Line 3,568: | ||
CBDA |
CBDA |
||
DBCA |
DBCA |
||
DCAB]-</ |
DCAB]-</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,030: | Line 3,576: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
Uses the 3rd method approach by adding the columns. |
Uses the 3rd method approach by adding the columns. |
||
<syntaxhighlight lang="vb"> |
|||
<lang vb> |
|||
arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_ |
arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_ |
||
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_ |
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_ |
||
Line 3,055: | Line 3,601: | ||
WScript.StdOut.WriteLine missing |
WScript.StdOut.WriteLine missing |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>DBAC</pre> |
<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}}== |
=={{header|XPL0}}== |
||
Line 3,064: | Line 3,729: | ||
missperm <missperm.txt |
missperm <missperm.txt |
||
< |
<syntaxhighlight lang="xpl0">code HexIn=26, HexOut=27; |
||
int P, I; |
int P, I; |
||
[P:= 0; |
[P:= 0; |
||
for I:= 1 to 24-1 do P:= P xor HexIn(1); |
for I:= 1 to 24-1 do P:= P xor HexIn(1); |
||
HexOut(0, P); |
HexOut(0, P); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,078: | Line 3,743: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution. |
Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution. |
||
< |
<syntaxhighlight lang="zkl">var data=L("ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB", |
||
"DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA", |
"DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA", |
||
"DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"); |
"DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"); |
||
Utils.Helpers.permute(["A".."D"]).apply("concat").copy().remove(data.xplode());</ |
Utils.Helpers.permute(["A".."D"]).apply("concat").copy().remove(data.xplode());</syntaxhighlight> |
||
Copy creates a read/write list from a read only list. |
Copy creates a read/write list from a read only list. |
||
xplode() pushes all elements of data as parameters to remove. |
xplode() pushes all elements of data as parameters to remove. |
||
Line 3,090: | Line 3,755: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
< |
<syntaxhighlight lang="zxbasic">10 LET l$="ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB" |
||
20 LET length=LEN l$ |
20 LET length=LEN l$ |
||
30 FOR a= CODE "A" TO CODE "D" |
30 FOR a= CODE "A" TO CODE "D" |
||
Line 3,103: | Line 3,768: | ||
120 NEXT i |
120 NEXT i |
||
130 PRINT x$;" is missing" |
130 PRINT x$;" is missing" |
||
140 NEXT d: NEXT c: NEXT b: NEXT a</ |
140 NEXT d: NEXT c: NEXT b: NEXT a</syntaxhighlight> |
Latest revision as of 08:18, 5 August 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
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.
- Task
Find that missing permutation.
- Methods
- Obvious method:
enumerate all permutations of A, B, C, and D, and then look for the missing permutation.
- alternate method:
Hint: if all permutations were shown above, how many times would A appear in each position? What is the parity of this number?
- another alternate method:
Hint: if you add up the letter values of each column, does a missing letter A, B, C, and D from each column cause the total value for each column to be unique?
- Related task
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)
- Output:
DBAC
360 Assembly
Very compact version, thanks to the clever Raku "xor" algorithm.
* Find the missing permutation - 19/10/2015
PERMMISX CSECT
USING PERMMISX,R15 set base register
LA R4,0 i=0
LA R6,1 step
LA R7,23 to
LOOPI BXH R4,R6,ELOOPI do i=1 to hbound(perms)
LA R5,0 j=0
LA R8,1 step
LA R9,4 to
LOOPJ BXH R5,R8,ELOOPJ do j=1 to hbound(miss)
LR R1,R4 i
SLA R1,2 *4
LA R3,PERMS-5(R1) @perms(i)
AR R3,R5 j
LA R2,MISS-1(R5) @miss(j)
XC 0(1,R2),0(R3) miss(j)=miss(j) xor substr(perms(i),j,1)
B LOOPJ
ELOOPJ B LOOPI
ELOOPI XPRNT MISS,15 print buffer
XR R15,R15 set return code
BR R14 return to caller
PERMS DC C'ABCD',C'CABD',C'ACDB',C'DACB',C'BCDA',C'ACBD'
DC C'ADCB',C'CDAB',C'DABC',C'BCAD',C'CADB',C'CDBA'
DC C'CBAD',C'ABDC',C'ADBC',C'BDCA',C'DCBA',C'BACD'
DC C'BADC',C'BDAC',C'CBDA',C'DBCA',C'DCAB'
MISS DC 4XL1'00',C' is missing' buffer
YREGS
END PERMMISX
- Output:
DBAC is missing
8080 Assembly
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
- Output:
Missing permutation: DBAC
8086 Assembly
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'
- Output:
Missing permutation: DBAC
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
- Output:
Screenshot from Atari 8-bit computer
DBAC
Ada
with Ada.Text_IO;
procedure Missing_Permutations is
subtype Permutation_Character is Character range 'A' .. 'D';
Character_Count : constant :=
1 + Permutation_Character'Pos (Permutation_Character'Last)
- Permutation_Character'Pos (Permutation_Character'First);
type Permutation_String is
array (1 .. Character_Count) of Permutation_Character;
procedure Put (Item : Permutation_String) is
begin
for I in Item'Range loop
Ada.Text_IO.Put (Item (I));
end loop;
end Put;
Given_Permutations : array (Positive range <>) of Permutation_String :=
("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD",
"BADC", "BDAC", "CBDA", "DBCA", "DCAB");
Count : array (Permutation_Character, 1 .. Character_Count) of Natural
:= (others => (others => 0));
Max_Count : Positive := 1;
Missing_Permutation : Permutation_String;
begin
for I in Given_Permutations'Range loop
for Pos in 1 .. Character_Count loop
Count (Given_Permutations (I) (Pos), Pos) :=
Count (Given_Permutations (I) (Pos), Pos) + 1;
if Count (Given_Permutations (I) (Pos), Pos) > Max_Count then
Max_Count := Count (Given_Permutations (I) (Pos), Pos);
end if;
end loop;
end loop;
for Char in Permutation_Character loop
for Pos in 1 .. Character_Count loop
if Count (Char, Pos) < Max_Count then
Missing_Permutation (Pos) := Char;
end if;
end loop;
end loop;
Ada.Text_IO.Put_Line ("Missing Permutation:");
Put (Missing_Permutation);
end Missing_Permutations;
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;
}
- Output:
DBAC
ALGOL 68
Uses the XOR algorithm of the Raku sample.
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"
, "ACBD", "ADCB", "CDAB", "DABC", "BCAD"
, "CADB", "CDBA", "CBAD", "ABDC", "ADBC"
, "BDCA", "DCBA", "BACD", "BADC", "BDAC"
, "CBDA", "DBCA", "DCAB"
);
# sets b to b XOR v and returns b #
PRIO XORAB = 1;
OP XORAB = ( REF BITS b, BITS v )REF BITS: b := b XOR v;
# 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
- Output:
DBAC
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.
missing ← ((⊂↓⍳¨⌊/) +⌿∘(⊢∘.=∪∘∊)) ⌷ ∪∘∊
- Output:
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
AppleScript
(Statistical versions)
Taking the third approach from the task description, and composing with functional primitives:
Yosemite OS X onwards (uses NSString for sorting):
use framework "Foundation" -- ( sort )
--------------- RAREST LETTER IN EACH COLUMN -------------
on run
concat(map(composeList({¬
head, ¬
minimumBy(comparing(|length|)), ¬
group, ¬
sort}), ¬
transpose(map(chars, ¬
|words|("ABCD CABD ACDB DACB BCDA ACBD " & ¬
"ADCB CDAB DABC BCAD CADB CDBA " & ¬
"CBAD ABDC ADBC BDCA DCBA BACD " & ¬
"BADC BDAC CBDA DBCA DCAB")))))
--> "DBAC"
end run
-------------------- GENERIC FUNCTIONS -------------------
-- chars :: String -> [String]
on chars(s)
characters of s
end chars
-- Ordering :: (-1 | 0 | 1)
-- compare :: a -> a -> Ordering
on compare(a, b)
if a < b then
-1
else if a > b then
1
else
0
end if
end compare
-- 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
-- composeList :: [(a -> a)] -> (a -> a)
on composeList(fs)
script
on |λ|(x)
script go
on |λ|(f, a)
mReturn(f)'s |λ|(a)
end |λ|
end script
foldr(go, x, fs)
end |λ|
end script
end composeList
-- 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 v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- 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 lng to 1 by -1
set v to |λ|(item i of xs, v, i, xs)
end repeat
return v
end tell
end foldr
-- 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
-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to lstText as text
set my text item delimiters to dlm
return strJoined
end intercalate
-- 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
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- sort :: [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬
sortedArrayUsingSelector:"compare:") as list
end sort
-- tail :: [a] -> [a]
on tail(xs)
if length of xs > 1 then
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
-- words :: String -> [String]
on |words|(s)
words of s
end |words|
- Output:
"DBAC"
Arturo
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
- Output:
DBAC
AutoHotkey
IncompleteList := "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
CompleteList := Perm( "ABCD" )
Missing := ""
Loop, Parse, CompleteList, `n, `r
If !InStr( IncompleteList , A_LoopField )
Missing .= "`n" A_LoopField
MsgBox Missing Permutation(s):%Missing%
;-------------------------------------------------
; Shortened version of [VxE]'s permutation function
; http://www.autohotkey.com/forum/post-322251.html#322251
Perm( s , dL="" , t="" , p="") {
StringSplit, m, s, % d := SubStr(dL,1,1) , %t%
IfEqual, m0, 1, return m1 d p
Loop %m0%
{
r := m1
Loop % m0-2
x := A_Index + 1, r .= d m%x%
L .= Perm(r, d, t, m%m0% d p)"`n" , mx := m1
Loop % m0-1
x := A_Index + 1, m%A_Index% := m%x%
m%m0% := mx
}
return substr(L, 1, -1)
}
AWK
This reads the list of permutations as standard input and outputs the missing one.
{
split($1,a,"");
for (i=1;i<=4;++i) {
t[i,a[i]]++;
}
}
END {
for (k in t) {
split(k,a,SUBSEP)
for (l in t) {
split(l, b, SUBSEP)
if (a[1] == b[1] && t[k] < t[l]) {
s[a[1]] = a[2]
break
}
}
}
print s[1]s[2]s[3]s[4]
}
- Output:
DBAC
BBC BASIC
DIM perms$(22), miss&(4)
perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \
\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \
\ "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
FOR i% = 0 TO DIM(perms$(),1)
FOR j% = 1 TO DIM(miss&(),1)
miss&(j%-1) EOR= ASCMID$(perms$(i%),j%)
NEXT
NEXT
PRINT $$^miss&(0) " is missing"
END
- Output:
DBAC is missing
Burlesque
ln"ABCD"r@\/\\
(Feed permutations via STDIN. Uses the naive method).
Version calculating frequency of occurences of each letter in each row and thus finding the missing permutation by choosing the letters with the lowest frequency:
ln)XXtp)><)F:)<]u[/v\[
C
#include <stdio.h>
#define N 4
const char *perms[] = {
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB",
};
int main()
{
int i, j, n, cnt[N];
char miss[N];
for (n = i = 1; i < N; i++) n *= i; /* n = (N-1)!, # of occurrence */
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) cnt[j] = 0;
/* count how many times each letter occur at position i */
for (j = 0; j < sizeof(perms)/sizeof(const char*); j++)
cnt[perms[j][i] - 'A']++;
/* letter not occurring (N-1)! times is the missing one */
for (j = 0; j < N && cnt[j] == n; j++);
miss[i] = j + 'A';
}
printf("Missing: %.*s\n", N, miss);
return 0;
}
- Output:
Missing: DBAC
C#
By permutating
using System;
using System.Collections.Generic;
namespace MissingPermutation
{
class Program
{
static void Main()
{
string[] given = new string[] { "ABCD", "CABD", "ACDB", "DACB",
"BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA",
"CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC",
"CBDA", "DBCA", "DCAB" };
List<string> result = new List<string>();
permuteString(ref result, "", "ABCD");
foreach (string a in result)
if (Array.IndexOf(given, a) == -1)
Console.WriteLine(a + " is a missing Permutation");
}
public static void permuteString(ref List<string> result, string beginningString, string endingString)
{
if (endingString.Length <= 1)
{
result.Add(beginningString + endingString);
}
else
{
for (int i = 0; i < endingString.Length; i++)
{
string newString = endingString.Substring(0, i) + endingString.Substring(i + 1);
permuteString(ref result, beginningString + (endingString.ToCharArray())[i], newString);
}
}
}
}
}
By xor-ing the values
using System;
using System.Linq;
public class Test
{
public static void Main()
{
var input = new [] {"ABCD","CABD","ACDB","DACB","BCDA",
"ACBD","ADCB","CDAB","DABC","BCAD","CADB",
"CDBA","CBAD","ABDC","ADBC","BDCA","DCBA",
"BACD","BADC","BDAC","CBDA","DBCA","DCAB"};
int[] values = {0,0,0,0};
foreach (string s in input)
for (int i = 0; i < 4; i++)
values[i] ^= s[i];
Console.WriteLine(string.Join("", values.Select(i => (char)i)));
}
}
C++
#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;
}
Clojure
(use 'clojure.math.combinatorics)
(use 'clojure.set)
(def given (apply hash-set (partition 4 5 "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB" )))
(def s1 (apply hash-set (permutations "ABCD")))
(def missing (difference s1 given))
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.
(def abcds ["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB"
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA"
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"])
(def freqs (->> abcds (apply map vector) (map frequencies)))
(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst))
(->> freqs (map #(v->k % 5)) (apply str) println)
CoffeeScript
missing_permutation = (arr) ->
# Find the missing permutation in an array of N! - 1 permutations.
# We won't validate every precondition, but we do have some basic
# guards.
if arr.length == 0
throw Error "Need more data"
if arr.length == 1
return [arr[0][1] + arr[0][0]]
# Now we know that for each position in the string, elements should appear
# an even number of times (N-1 >= 2). We can use a set to detect the element appearing
# an odd number of times. Detect odd occurrences by toggling admission/expulsion
# to and from the set for each value encountered. At the end of each pass one element
# will remain in the set.
result = ''
for pos in [0...arr[0].length]
set = {}
for permutation in arr
c = permutation[pos]
if set[c]
delete set[c]
else
set[c] = true
for c of set
result += c
break
result
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'''
arr = (s for s in given.replace('\n', ' ').split ' ' when s != '')
console.log missing_permutation(arr)
- Output:
> coffee missing_permute.coffee DBAC
Common Lisp
(defparameter *permutations*
'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"))
(defun missing-perm (perms)
(let* ((letters (loop for i across (car perms) collecting i))
(l (/ (1+ (length perms)) (length letters))))
(labels ((enum (n) (loop for i below n collecting i))
(least-occurs (pos)
(let ((occurs (loop for i in perms collecting (aref i pos))))
(cdr (assoc (1- l) (mapcar #'(lambda (letter)
(cons (count letter occurs) letter))
letters))))))
(concatenate 'string (mapcar #'least-occurs (enum (length letters)))))))
- Output:
ROSETTA> (missing-perm *permutations*) "DBAC"
D
void main() {
import std.stdio, std.string, std.algorithm, std.range, std.conv;
immutable perms = "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC
BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD
BADC BDAC CBDA DBCA DCAB".split;
// Version 1: test all permutations.
immutable permsSet = perms
.map!representation
.zip(true.repeat)
.assocArray;
auto perm = perms[0].dup.representation;
do {
if (perm !in permsSet)
writeln(perm.map!(c => char(c)));
} while (perm.nextPermutation);
// Version 2: xor all the ASCII values, the uneven one
// gets flushed out. Based on Raku (via Go).
enum len = 4;
char[len] b = 0;
foreach (immutable p; perms)
b[] ^= p[];
b.writeln;
// Version 3: sum ASCII values.
immutable rowSum = perms[0].sum;
len
.iota
.map!(i => to!char(rowSum - perms.transversal(i).sum % rowSum))
.writeln;
// Version 4: a checksum, Java translation. maxCode will be 36.
immutable maxCode = reduce!q{a * b}(len - 1, iota(3, len + 1));
foreach (immutable i; 0 .. len) {
immutable code = perms.map!(p => perms[0].countUntil(p[i])).sum;
// Code will come up 3, 1, 0, 2 short of 36.
perms[0][maxCode - code].write;
}
}
- Output:
DBAC DBAC DBAC DBAC
Delphi
See Pascal.
EasyLang
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$
- Output:
DBAC
EchoLisp
;; use the obvious methos
(lib 'list) ; for (permutations) function
;; input
(define perms '
(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB))
;; generate all permutations
(define all-perms (map list->string (permutations '(A B C D))))
→ all-perms
;; {set} substraction
(set-substract (make-set all-perms) (make-set perms))
→ { DBAC }
Elixir
defmodule RC do
def find_miss_perm(head, perms) do
all_permutations(head) -- perms
end
defp all_permutations(string) do
list = String.split(string, "", trim: true)
Enum.map(permutations(list), fn x -> Enum.join(x) end)
end
defp permutations([]), do: [[]]
defp permutations(list), do: (for x <- list, y <- permutations(list -- [x]), do: [x|y])
end
perms = ["ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"]
IO.inspect RC.find_miss_perm( hd(perms), perms )
- Output:
["DBAC"]
Erlang
The obvious method. It seems fast enough (no waiting time).
-module( find_missing_permutation ).
-export( [difference/2, task/0] ).
difference( Permutate_this, Existing_permutations ) -> all_permutations( Permutate_this ) -- Existing_permutations.
task() -> difference( "ABCD", existing_permutations() ).
all_permutations( String ) -> [[A, B, C, D] || A <- String, B <- String, C <- String, D <- String, is_different([A, B, C, D])].
existing_permutations() -> ["ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"].
is_different( [_H] ) -> true;
is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ).
- Output:
6> find_the_missing_permutation:task(). ["DBAC"]
ERRE
PROGRAM MISSING
CONST N=4
DIM PERMS$[23]
BEGIN
PRINT(CHR$(12);) ! CLS
DATA("ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB")
DATA("CDAB","DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC")
DATA("BDCA","DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB")
FOR I%=1 TO UBOUND(PERMS$,1) DO
READ(PERMS$[I%])
END FOR
SOL$="...."
FOR I%=1 TO N DO
CH$=CHR$(I%+64)
COUNT%=0
FOR Z%=1 TO N DO
COUNT%=0
FOR J%=1 TO UBOUND(PERMS$,1) DO
IF CH$=MID$(PERMS$[J%],Z%,1) THEN COUNT%=COUNT%+1 END IF
END FOR
IF COUNT%<>6 THEN
!$RCODE="MID$(SOL$,Z%,1)=CH$"
END IF
END FOR
END FOR
PRINT("Solution is: ";SOL$)
END PROGRAM
- Output:
Solution is: DBAC
Factor
Permutations are read in via STDIN.
USING: io math.combinatorics sequences sets ;
"ABCD" all-permutations lines diff first print
- Output:
DBAC
Forth
Tested with: GForth, VFX Forth, SwiftForth, Win32 Forth. Should work with any ANS Forth system.
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.)
hex
ABCD CABD xor ACDB xor DACB xor BCDA xor ACBD xor
ADCB xor CDAB xor DABC xor BCAD xor CADB xor CDBA xor
CBAD xor ABDC xor ADBC xor BDCA xor DCBA xor BACD xor
BADC xor BDAC xor CBDA xor DBCA xor DCAB xor
cr .( Missing permutation: ) u.
decimal
- Output:
Missing permutation: DBAC ok
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.
program missing_permutation
implicit none
character (4), dimension (23), parameter :: list = &
& (/'ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB', &
& 'DABC', 'BCAD', 'CADB', 'CDBA', 'CBAD', 'ABDC', 'ADBC', 'BDCA', &
& 'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'/)
integer :: i, j, k
do i = 1, 4
j = minloc ((/(count (list (:) (i : i) == list (1) (k : k)), k = 1, 4)/), 1)
write (*, '(a)', advance = 'no') list (1) (j : j)
end do
write (*, *)
end program missing_permutation
- Output:
DBAC
FreeBASIC
Simple count
' 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
- Output:
The missing permutation is : DBAC
Add the value's
' 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
output is same as the first version
Using Xor
' 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
Output is the same as the first version
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]
}
- Output:
DBAC
GAP
# our deficient list
L :=
[ "ABCD", "CABD", "ACDB", "DACB", "BCDA",
"ACBD", "ADCB", "CDAB", "DABC", "BCAD",
"CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC",
"CBDA", "DBCA", "DCAB" ];
# convert L to permutations on 1..4
u := List(L, s -> List([1..4], i -> Position("ABCD", s[i])));
# set difference (with all permutations)
v := Difference(PermutationsList([1..4]), u);
# convert back to letters
s := "ABCD";
List(v, p -> List(p, i -> s[i]));
Go
Alternate method suggested by task description:
package main
import (
"fmt"
"strings"
)
var given = strings.Split(`ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB`, "\n")
func main() {
b := make([]byte, len(given[0]))
for i := range b {
m := make(map[byte]int)
for _, p := range given {
m[p[i]]++
}
for char, count := range m {
if count&1 == 1 {
b[i] = char
break
}
}
}
fmt.Println(string(b))
}
Xor method suggested by Raku contributor:
func main() {
b := make([]byte, len(given[0]))
for _, p := range given {
for i, c := range []byte(p) {
b[i] ^= c
}
}
fmt.Println(string(b))
}
- Output:
in either case
DBAC
Groovy
Solution:
def fact = { n -> [1,(1..<(n+1)).inject(1) { prod, i -> prod * i }].max() }
def missingPerms
missingPerms = {List elts, List perms ->
perms.empty ? elts.permutations() : elts.collect { e ->
def ePerms = perms.findAll { e == it[0] }.collect { it[1..-1] }
ePerms.size() == fact(elts.size() - 1) ? [] \
: missingPerms(elts - e, ePerms).collect { [e] + it }
}.sum()
}
Test:
def e = 'ABCD' as List
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 }
- Output:
[D, B, A, C]
Haskell
Difference between two lists
import Data.List ((\\), permutations, nub)
import Control.Monad (join)
missingPerm
:: Eq a
=> [[a]] -> [[a]]
missingPerm = (\\) =<< permutations . nub . join
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 = print $ missingPerm deficientPermsList
- Output:
["DBAC"]
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.List (minimumBy, group, sort, transpose)
import Data.Ord (comparing)
missingPerm
:: Ord a
=> [[a]] -> [a]
missingPerm = fmap (head . minimumBy (comparing length) . group . sort) . transpose
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 = print $ missingPerm deficientPermsList
- Output:
"DBAC"
Folding XOR over the list of permutations
Surfacing the missing bits:
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
- Output:
DBAC
Icon and Unicon
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.
A still more efficient version is:
member 'strings' provides permutes(s) which generates all permutations of a string
J
Solution:
permutations=: A.~ i.@!@#
missingPerms=: -.~ permutations @ {.
Use:
data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA' data=: data,>;: 'CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB' missingPerms data DBAC
Alternatives
Or the above could be a single definition that works the same way:
missingPerms=: -.~ (A.~ i.@!@#) @ {.
Or the equivalent explicit (cf. tacit above) definition:
missingPerms=: monad define
item=. {. y
y -.~ item A.~ i.! #item
)
Or, the solution could be obtained without defining an independent program:
data -.~ 'ABCD' A.~ i.!4
DBAC
Here, 'ABCD'
represents the values being permuted (their order does not matter), and 4
is how many of them we have.
Yet another alternative expression, which uses parentheses instead of the passive operator (~
), would be:
((i.!4) A. 'ABCD') -. data
DBAC
Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable:
'ABCD'{~,I.@(= <./)@(#/.~)@('ABCD' , ])"1 |:perms
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:
,(~.#~2|(#/.~))"1|:data
DBAC
We could use arithmetic, as suggested in the task hints:
({.data){~|(->./)+/({.i.])data
DBAC
Java
optimized Following needs: Utils.java
import java.util.ArrayList;
import com.google.common.base.Joiner;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
public class FindMissingPermutation {
public static void main(String[] args) {
Joiner joiner = Joiner.on("").skipNulls();
ImmutableSet<String> s = ImmutableSet.of("ABCD", "CABD", "ACDB",
"DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB",
"CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC",
"BDAC", "CBDA", "DBCA", "DCAB");
for (ArrayList<Character> cs : Utils.Permutations(Lists.newArrayList(
'A', 'B', 'C', 'D')))
if (!s.contains(joiner.join(cs)))
System.out.println(joiner.join(cs));
}
}
- Output:
DBAC
Alternate version, based on checksumming each position:
public class FindMissingPermutation
{
public static void main(String[] args)
{
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" };
String characterSet = givenPermutations[0];
// Compute n! * (n - 1) / 2
int maxCode = characterSet.length() - 1;
for (int i = characterSet.length(); i >= 3; i--)
maxCode *= i;
StringBuilder missingPermutation = new StringBuilder();
for (int i = 0; i < characterSet.length(); i++)
{
int code = 0;
for (String permutation : givenPermutations)
code += characterSet.indexOf(permutation.charAt(i));
missingPermutation.append(characterSet.charAt(maxCode - code));
}
System.out.println("Missing permutation: " + missingPermutation.toString());
}
}
JavaScript
ES5
Imperative
The permute() function taken from http://snippets.dzone.com/posts/show/1032
permute = function(v, m){ //v1.0
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;
++i < l; x[2][i] = i, x[1][i] = x[0][i] = j /= --k);
for(r = new Array(q); ++p < q;)
for(r[p] = new Array(l), i = -1; ++i < l; !--x[1][i] && (x[1][i] = x[0][i],
x[2][i] = (x[2][i] + 1) % l), r[p][i] = m ? x[3][i] : v[x[3][i]])
for(x[3][i] = x[2][i], f = 0; !f; f = !f)
for(j = i; j; x[3][--j] == x[2][i] && (x[3][i] = x[2][i] = (x[2][i] + 1) % l, f = 1));
return r;
};
list = [ 'ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB',
'DABC', 'BCAD', 'CADB', 'CDBA', 'CBAD', 'ABDC', 'ADBC', 'BDCA',
'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'];
all = permute(list[0].split('')).map(function(elem) {return elem.join('')});
missing = all.filter(function(elem) {return list.indexOf(elem) == -1});
print(missing); // ==> DBAC
Functional
(function (strList) {
// [a] -> [[a]]
function permutations(xs) {
return xs.length ? (
chain(xs, function (x) {
return chain(permutations(deleted(x, xs)), function (ys) {
return [[x].concat(ys).join('')];
})
})) : [[]];
}
// Monadic bind/chain for lists
// [a] -> (a -> b) -> [b]
function chain(xs, f) {
return [].concat.apply([], xs.map(f));
}
// a -> [a] -> [a]
function deleted(x, xs) {
return xs.length ? (
x === xs[0] ? xs.slice(1) : [xs[0]].concat(
deleted(x, xs.slice(1))
)
) : [];
}
// Provided subset
var lstSubSet = strList.split('\n');
// Any missing permutations
// (we can use fold/reduce, filter, or chain (concat map) here)
return chain(permutations('ABCD'.split('')), function (x) {
return lstSubSet.indexOf(x) === -1 ? [x] : [];
});
})(
'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\
CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB'
);
- Output:
["DBAC"]
ES6
Statistical
Using a dictionary
(() => {
'use strict';
// transpose :: [[a]] -> [[a]]
let transpose = xs =>
xs[0].map((_, iCol) => xs
.map((row) => row[iCol]));
let 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 transpose(xs.split(' ')
.map(x => x.split('')))
.map(col => col.reduce((a, x) => ( // count of each character in each column
a[x] = (a[x] || 0) + 1,
a
), {}))
.map(dct => { // character with frequency below mean of distribution ?
let ks = Object.keys(dct),
xs = ks.map(k => dct[k]),
mean = xs.reduce((a, b) => a + b, 0) / xs.length;
return ks.reduce(
(a, k) => a ? a : (dct[k] < mean ? k : undefined),
undefined
);
})
.join(''); // 4 chars as single string
// --> 'DBAC'
})();
- Output:
DBAC
Composing functional primitives
(() => {
'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"
})();
- Output:
DBAC
XOR
Folding an xor operator over the list of character codes:
(() => {
'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()
})();
- Output:
DBAC
jq
The following assumes that a file, Find_the_missing_permutation.txt, has the text exactly as presented in the task description.
To find the missing permutation, we can for simplicity invoke jq twice:
jq -R . Find_the_missing_permutation.txt | jq -s -f Find_the_missing_permutation.jq
The first invocation simply converts the raw text into a stream of JSON strings; these are then processed by the following program, which implements the parity-based approach.
The program will handle permutations of any set of uppercase letters. The letters need not be consecutive. Note that the following encoding of letters is used: A => 0, B => 1, ....
Infrastructure:
If your version of jq has transpose/0, the definition given here (which is the same as in Matrix_Transpose#jq) may be omitted.
def transpose:
if (.[0] | length) == 0 then []
else [map(.[0])] + (map(.[1:]) | transpose)
end ;
# Input: an array of integers (based on the encoding of A=0, B=1, etc)
# corresponding to the occurrences in any one position of the
# letters in the list of permutations.
# Output: a tally in the form of an array recording in position i the
# parity of the number of occurrences of the letter corresponding to i.
# Example: given [0,1,0,1,2], the array of counts of 0, 1, and 2 is [2, 2, 1],
# and thus the final result is [0, 0, 1].
def parities:
reduce .[] as $x ( []; .[$x] = (1 + .[$x]) % 2);
# Input: an array of parity-counts, e.g. [0, 1, 0, 0]
# Output: the corresponding letter, e.g. "B".
def decode:
[index(1) + 65] | implode;
# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]):
def encode_string: [explode[] - 65];
The task:
map(encode_string) | transpose | map(parities | decode) | join("")
- Output:
$ jq -R . Find_the_missing_permutation.txt | jq -s -f Find_the_missing_permutation.jq
"DBAC"
Julia
Obvious method
Calculate all possible permutations and return the first not included in the array.
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",
"CBDA", "DBCA", "DCAB"]
@show missingperm(arr)
- Output:
missingperm(arr) = "DBAC"
Alternative method 1
function missingperm1(arr::Vector{<:AbstractString})
missperm = string()
for pos in 1:length(arr[1])
s = Set()
for perm in arr
c = perm[pos]
if c ∈ s pop!(s, c) else push!(s, c) end
end
missperm *= first(s)
end
return missperm
end
Alternative method 2
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)
- Output:
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)
K
split:{1_'(&x=y)_ x:y,x}
g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB")
g,:(" CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB")
p: split[g;" "];
/ All permutations of "ABCD"
perm:{:[1<x;,/(>:'(x,x)#1,x#0)[;0,'1+_f x-1];,!x]}
p2:a@(perm(#a:"ABCD"));
/ Which permutations in p are there in p2?
p2 _lin p
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
/ Invert the result
~p2 _lin p
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
/ It's the 20th permutation that is missing
&~p2 _lin p
,20
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):
,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p
Kotlin
// 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(""))
}
}
- Output:
The missing permutation is DBAC
Lua
Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight
local permute, tablex = require("pl.permute"), require("pl.tablex")
local permList, pStr = {
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
}
for perm in permute.iter({"A","B","C","D"}) do
pStr = table.concat(perm)
if not tablex.find(permList, pStr) then print(pStr) end
end
- Output:
DBAC
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')], "")):
- Output:
"DBAC"
Mathematica / Wolfram Language
ProvidedSet = {"ABCD" , "CABD" , "ACDB" , "DACB" , "BCDA" , "ACBD",
"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC",
"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"};
Complement[StringJoin /@ Permutations@Characters@First@#, #] &@ProvidedSet
->{"DBAC"}
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.
function perm = findMissingPerms(list)
permsList = perms(list(1,:)); %Generate all permutations of the 4 letters
perm = []; %This is the functions return value if the list is not missing a permutation
%Normally the rest of this would be vectorized, but because this is
%done on a vector of strings, the vectorized functions will only access
%one character at a time. So, in order for this to work we have to use
%loops.
for i = (1:size(permsList,1))
found = false;
for j = (1:size(list,1))
if (permsList(i,:) == list(j,:))
found = true;
break
end
end
if not(found)
perm = permsList(i,:);
return
end
end %for
end %fingMissingPerms
- Output:
>> list = ['ABCD';
'CABD';
'ACDB';
'DACB';
'BCDA';
'ACBD';
'ADCB';
'CDAB';
'DABC';
'BCAD';
'CADB';
'CDBA';
'CBAD';
'ABDC';
'ADBC';
'BDCA';
'DCBA';
'BACD';
'BADC';
'BDAC';
'CBDA';
'DBCA';
'DCAB']
list =
ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB
>> findMissingPerms(list)
ans =
DBAC
Nim
import strutils
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 ..< arr[0].len:
var s: set[char] = {}
for permutation in arr:
let c = permutation[pos]
if c in s: s.excl c
else: s.incl c
for c in s: result.add c
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""".splitWhiteSpace()
echo missingPermutation(given)
- Output:
DBAC
OCaml
some utility functions:
(* insert x at all positions into li and return the list of results *)
let rec insert x = function
| [] -> [[x]]
| a::m as li -> (x::li) :: (List.map (fun y -> a::y) (insert x m))
(* list of all permutations of li *)
let permutations li =
List.fold_right (fun a z -> List.concat (List.map (insert a) z)) li [[]]
(* convert a string to a char list *)
let chars_of_string s =
let cl = ref [] in
String.iter (fun c -> cl := c :: !cl) s;
(List.rev !cl)
(* convert a char list to a string *)
let string_of_chars cl =
String.concat "" (List.map (String.make 1) cl)
resolve the task:
let deficient_perms = [
"ABCD";"CABD";"ACDB";"DACB";
"BCDA";"ACBD";"ADCB";"CDAB";
"DABC";"BCAD";"CADB";"CDBA";
"CBAD";"ABDC";"ADBC";"BDCA";
"DCBA";"BACD";"BADC";"BDAC";
"CBDA";"DBCA";"DCAB";
]
let it = chars_of_string (List.hd deficient_perms)
let perms = List.map string_of_chars (permutations it)
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, each letter would appear an even number of times at each position. Since there is only one permutation missing, we can find where each letter goes by looking at the parity of the number of occurences of each letter. The following program works with permutations of at least 3 letters:
let array_of_perm s =
let n = String.length s in
Array.init n (fun i -> int_of_char s.[i] - 65);;
let perm_of_array a =
let n = Array.length a in
let s = String.create n in
Array.iteri (fun i x ->
s.[i] <- char_of_int (x + 65)
) a;
s;;
let find_missing v =
let n = String.length (List.hd v) in
let a = Array.make_matrix n n 0
and r = ref v in
List.iter (fun s ->
let u = array_of_perm s in
Array.iteri (fun i x -> x.(u.(i)) <- x.(u.(i)) + 1) a
) v;
let q = Array.make n 0 in
Array.iteri (fun i x ->
Array.iteri (fun j y ->
if y mod 2 != 0 then q.(i) <- j
) x
) a;
perm_of_array q;;
find_missing deficient_perms;;
(* - : string = "DBAC" *)
Octave
given = [ 'ABCD';'CABD';'ACDB';'DACB'; ...
'BCDA';'ACBD';'ADCB';'CDAB'; ...
'DABC';'BCAD';'CADB';'CDBA'; ...
'CBAD';'ABDC';'ADBC';'BDCA'; ...
'DCBA';'BACD';'BADC';'BDAC'; ...
'CBDA';'DBCA';'DCAB' ];
val = 4.^(3:-1:0)';
there = 1+(toascii(given)-toascii('A'))*val;
every = 1+perms(0:3)*val;
bits = zeros(max(every),1);
bits(every) = 1;
bits(there) = 0;
missing = dec2base(find(bits)-1,'ABCD')
Oz
Using constraint programming for this problem may be a bit overkill...
declare
GivenPermutations =
["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"]
%% four distinct variables between "A" and "D":
proc {Description Root}
Root = {FD.list 4 &A#&D}
{FD.distinct Root}
{FD.distribute naiv Root}
end
AllPermutations = {SearchAll Description}
in
for P in AllPermutations do
if {Not {Member P GivenPermutations}} then
{System.showInfo "Missing: "#P}
end
end
PARI/GP
v=["ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB","DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA","DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"];
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))
- Output:
%1 = "DBAC"
Pascal
like c, summation, and Raku XORing
program MissPerm;
{$MODE DELPHI} //for result
const
maxcol = 4;
type
tmissPerm = 1..23;
tcol = 1..maxcol;
tResString = String[maxcol];
const
Given_Permutations : array [tmissPerm] of tResString =
('ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD',
'ADCB', 'CDAB', 'DABC', 'BCAD', 'CADB', 'CDBA',
'CBAD', 'ABDC', 'ADBC', 'BDCA', 'DCBA', 'BACD',
'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB');
chOfs = Ord('A')-1;
var
SumElemCol: array[tcol,tcol] of NativeInt;
function fib(n: NativeUint): NativeUint;
var
i : NativeUint;
Begin
result := 1;
For i := 2 to n do
result:= result*i;
end;
function CountOccurences: tresString;
//count the number of every letter in every column
//should be (colmax-1)! => 6
//the missing should count (colmax-1)! -1 => 5
var
fibN_1 : NativeUint;
row, col: NativeInt;
Begin
For row := low(tmissPerm) to High(tmissPerm) do
For col := low(tcol) to High(tcol) do
inc(SumElemCol[col,ORD(Given_Permutations[row,col])-chOfs]);
//search the missing
fibN_1 := fib(maxcol-1)-1;
setlength(result,maxcol);
For col := low(tcol) to High(tcol) do
For row := low(tcol) to High(tcol) do
IF SumElemCol[col,row]=fibN_1 then
result[col]:= ansichar(row+chOfs);
end;
function CheckXOR: tresString;
var
row,col: NativeUint;
Begin
setlength(result,maxcol);
fillchar(result[1],maxcol,#0);
For row := low(tmissPerm) to High(tmissPerm) do
For col := low(tcol) to High(tcol) do
result[col] := ansichar(ord(result[col]) XOR ord(Given_Permutations[row,col]));
end;
Begin
writeln(CountOccurences,' is missing');
writeln(CheckXOR,' is missing');
end.
- Output:
DBAC is missing DBAC is missing
PascalABC.NET
begin
var s := '''
ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB
''';
var perms := s.ToLines;
Print(('ABCD'.Permutations.ToHashSet - perms.ToHashSet).First);
end.
- Output:
DBAC
Perl
Because the set of all permutations contains all its own rotations, the first missing rotation is the target.
sub check_perm {
my %hash; @hash{@_} = ();
for my $s (@_) { exists $hash{$_} or return $_
for map substr($s,1) . substr($s,0,1), (1..length $s); }
}
# Check and display
@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";
- Output:
DBAC
Alternates
All cases take permutation list on STDIN or as filename on command line
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 :)
print eval join '^', map "'$_'", <>;
or if you don't like eval...
$\ ^= $_ while <>;
print '';
Every permutation has a "reverse", just take all reverses and remove the "normals".
local $_ = join '', <>;
my %h = map { $_, '' } reverse =~ /\w+/g;
delete @h{ /\w+/g };
print %h, "\n";
Phix
with javascript_semantics constant perms = {"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"} -- 1: sum of letters sequence r = repeat(0,4) for i=1 to length(perms) do r = sq_add(r,perms[i]) end for r = sq_sub(max(r)+'A',r) printf(1,"%s\n",{r}) -- 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 equivalent to eg {1528,1530,1531,1529} -- max-r[i] -> { 3, 1, 0, 2} -- to chars -> { D, B, A, C} -- (but obviously both done in one line) -- 2: the xor trick r = repeat(0,4) for i=1 to length(perms) do r = sq_xor_bits(r,perms[i]) end for printf(1,"%s\n",{r}) -- (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 r = " " for i=1 to length(r) do sequence count = repeat(0,4) for j=1 to length(perms) do integer cdx = perms[j][i]-'A'+1 count[cdx] += 1 end for r[i] = smallest(count,1)+'A'-1 end for printf(1,"%s\n",{r}) -- (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 for i=1 to factorial(4) do r = permute(i,"ABCD") if not find(r,perms) then exit end if end for printf(1,"%s\n",{r}) -- (relies on brute force(!) - but this is the only method that could be made to cope with >1 omission)
- Output:
DBAC DBAC DBAC DBAC
PHP
<?php
$finalres = Array();
function permut($arr,$result=array()){
global $finalres;
if(empty($arr)){
$finalres[] = implode("",$result);
}else{
foreach($arr as $key => $val){
$newArr = $arr;
$newres = $result;
$newres[] = $val;
unset($newArr[$key]);
permut($newArr,$newres);
}
}
}
$givenPerms = Array("ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB","DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA","DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB");
$given = Array("A","B","C","D");
permut($given);
print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC )
Picat
Here are several approaches, including constraint modelling, sets (ordset), and permutations.
All assume that the variables P1 and/or Perms has been defined:
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"),
% ...
Very imperative
% ...
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).
Somewhat less imperative
% ...
Missing2 = _,
foreach(P in Perms, Missing2 = _)
if not member(P,P1) then
Missing2 := P
end
end,
println(missing2=Missing2).
Using findall
% ...
println(missing3=difference(Perms,P1)).
difference(Xs,Ys) = findall(X,(member(X,Xs),not(member(X,Ys)))).
findall approach as a one-liner
% ...
println(missing4=findall(X,(member(X,Perms),not(member(X,P1))))).
Using ordsets
The module ordsets
must be imported,
import ordsets.
% ...
println(missing5=subtract(new_ordset(Perms),new_ordset(P1))).
List comprehension
List comprehension with membchk/1
for the check)
% ...
println(missing6=[P:P in Perms,not membchk(P,P1)])
Using maps
% ...
Map = new_map(),
foreach(P in P1) Map.put(P,1) end,
println(missing7=[P: P in Perms, not Map.has_key(P)]).
"Merge sort" variants
"Merge sort" variants, using sorted lists. zip/2
requires that the length of the two lists are the same, hence the "dummy".
% ...
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()),
Constraint modelling
The cp
module must be imported.
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]).
Matrix approach
% ...
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]).
Xor variant
% ...
println(missing13=to_fstring("%X",reduce(^,[parse_term("0x"++P):P in P1]))).
Count occurrences
Count the character with the least occurrence (=5) for each positions (1..4). Some variants.
% ...
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])]
Running all these snippets:
- Output:
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]
PicoLisp
(setq *PermList
(mapcar chop
(quote
"ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB"
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA"
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB" ) ) )
(let (Lst (chop "ABCD") L Lst)
(recur (L) # Permute
(if (cdr L)
(do (length L)
(recurse (cdr L))
(rot L) )
(unless (member Lst *PermList) # Check
(prinl Lst) ) ) ) )
- Output:
DBAC
PowerShell
function permutation ($array) {
function generate($n, $array, $A) {
if($n -eq 1) {
$array[$A] -join ''
}
else{
for( $i = 0; $i -lt ($n - 1); $i += 1) {
generate ($n - 1) $array $A
if($n % 2 -eq 0){
$i1, $i2 = $i, ($n-1)
$temp = $A[$i1]
$A[$i1] = $A[$i2]
$A[$i2] = $temp
}
else{
$i1, $i2 = 0, ($n-1)
$temp = $A[$i1]
$A[$i1] = $A[$i2]
$A[$i2] = $temp
}
}
generate ($n - 1) $array $A
}
}
$n = $array.Count
if($n -gt 0) {
(generate $n $array (0..($n-1)))
} else {$array}
}
$perm = permutation @('A','B','C', 'D')
$find = @(
"ABCD"
"CABD"
"ACDB"
"DACB"
"BCDA"
"ACBD"
"ADCB"
"CDAB"
"DABC"
"BCAD"
"CADB"
"CDBA"
"CBAD"
"ABDC"
"ADBC"
"BDCA"
"DCBA"
"BACD"
"BADC"
"BDAC"
"CBDA"
"DBCA"
"DCAB"
)
$perm | where{-not $find.Contains($_)}
Output:
DBAC
PureBasic
Procedure in_List(in.s)
Define.i i, j
Define.s a
Restore data_to_test
For i=1 To 3*8-1
Read.s a
If in=a
ProcedureReturn #True
EndIf
Next i
ProcedureReturn #False
EndProcedure
Define.c z, x, c, v
If OpenConsole()
For z='A' To 'D'
For x='A' To 'D'
If z=x:Continue:EndIf
For c='A' To 'D'
If c=x Or c=z:Continue:EndIf
For v='A' To 'D'
If v=c Or v=x Or v=z:Continue:EndIf
Define.s test=Chr(z)+Chr(x)+Chr(c)+Chr(v)
If Not in_List(test)
PrintN(test+" is missing.")
EndIf
Next
Next
Next
Next
PrintN("Press Enter to exit"):Input()
EndIf
DataSection
data_to_test:
Data.s "ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB"
Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA"
Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"
EndDataSection
Based on the Permutations task, the solution could be:
If OpenConsole()
NewList a.s()
findPermutations(a(), "ABCD", 4)
ForEach a()
Select a()
Case "ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB","DABC"
Case "BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA","DCBA","BACD"
Case "BADC","BDAC","CBDA","DBCA","DCAB"
Default
PrintN(A()+" is missing.")
EndSelect
Next
Print(#CRLF$ + "Press ENTER to exit"): Input()
EndIf
Python
Python: Calculate difference when compared to all permutations
from itertools import permutations
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()
allPerms = [''.join(x) for x in permutations(given[0])]
missing = list(set(allPerms) - set(given)) # ['DBAC']
Python:Counting lowest frequency character at each position
Here is a solution that is more in the spirit of the challenge, 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."
# We won't validate every precondition, but we do have some basic
# guards.
if len(arr) == 0: raise Exception("Need more data")
if len(arr) == 1:
return [arr[0][1] + arr[0][0]]
# Now we know that for each position in the string, elements should appear
# an even number of times (N-1 >= 2). We can use a set to detect the element appearing
# an odd number of times. Detect odd occurrences by toggling admission/expulsion
# to and from the set for each value encountered. At the end of each pass one element
# will remain in the set.
missing_permutation = ''
for pos in range(len(arr[0])):
s = set()
for permutation in arr:
c = permutation[pos]
if c in s:
s.remove(c)
else:
s.add(c)
missing_permutation += list(s)[0]
return missing_permutation
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()
print missing_permutation(given)
Python:Counting lowest frequency character at each position: functional
Uses the same method as explained directly above, but calculated in a more functional manner:
>>> from collections import Counter
>>> 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
It is rather obfuscated, but can be explained
by showing these intermediate results and noting
that zip(*x)
transposes x;
and that at the end of the list
created by the call to most_common()
is the least common character.
>>> from pprint import pprint as pp
>>> 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'),
('B', 'A', 'C', 'A', 'C', 'C', 'D', 'D', 'A', 'C', 'A', 'D', 'B', 'B', 'D', 'D', 'C', 'A', 'A', 'D', 'B', 'B', 'C'),
('C', 'B', 'D', 'C', 'D', 'B', 'C', 'A', 'B', 'A', 'D', 'B', 'A', 'D', 'B', 'C', 'B', 'C', 'D', 'A', 'D', 'C', 'A'),
('D', 'D', 'B', 'B', 'A', 'D', 'B', 'B', 'C', 'D', 'B', 'A', 'D', 'C', 'C', 'A', 'A', 'D', 'C', 'C', 'A', 'A', 'B')]
>>> pp([Counter(x).most_common() for x in zip(*given)])
[[('C', 6), ('B', 6), ('A', 6), ('D', 5)],
[('D', 6), ('C', 6), ('A', 6), ('B', 5)],
[('D', 6), ('C', 6), ('B', 6), ('A', 5)],
[('D', 6), ('B', 6), ('A', 6), ('C', 5)]]
>>> pp([Counter(x).most_common()[-1] for x in zip(*given)])
[('D', 5), ('B', 5), ('A', 5), ('C', 5)]
>>> pp([Counter(x).most_common()[-1][0] for x in zip(*given)])
['D', 'B', 'A', 'C']
>>> ''.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:
'''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]
)
]))
- Output:
DBAC
Quackery
Credit to Raku for the method, and noting that the strings are valid hexadecimal numbers.
$ "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
- Output:
DBAC
R
This uses the "combinat" package, which is a standard R package:
library(combinat)
permute.me <- c("A", "B", "C", "D")
perms <- permn(permute.me) # list of all permutations
perms2 <- matrix(unlist(perms), ncol=length(permute.me), byrow=T) # matrix of all permutations
perms3 <- apply(perms2, 1, paste, collapse="") # vector of all permutations
incomplete <- c("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
"DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
"DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB")
setdiff(perms3, incomplete)
- Output:
[1] "DBAC"
Racket
#lang racket
(define almost-all
'([A B C D] [C A B D] [A C D B] [D A C B] [B C D A] [A C B D] [A D C B]
[C D A B] [D A B C] [B C A D] [C A D B] [C D B A] [C B A D] [A B D C]
[A D B C] [B D C A] [D C B A] [B A C D] [B A D C] [B D A C] [C B D A]
[D B C A] [D C A B]))
;; Obvious method:
(for/first ([p (in-permutations (car almost-all))]
#:unless (member p almost-all))
p)
;; -> '(D B A C)
;; For permutations of any set
(define charmap
(for/hash ([x (in-list (car almost-all))] [i (in-naturals)])
(values x i)))
(define size (hash-count charmap))
;; Illustrating approach mentioned in the task description.
;; For each position, character with odd parity at that position.
(require data/bit-vector)
(for/list ([i (in-range size)])
(define parities (make-bit-vector size #f))
(for ([permutation (in-list almost-all)])
(define n (hash-ref charmap (list-ref permutation i)))
(bit-vector-set! parities n (not (bit-vector-ref parities n))))
(for/first ([(c i) charmap] #:when (bit-vector-ref parities i))
c))
;; -> '(D B A C)
Raku
(formerly Perl 6)
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;
- Output:
DBAC
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:
say [~^] <ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>;
- Output:
DBAC
RapidQ
Dim PList as QStringList
PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB"
PList.additems "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA"
PList.additems "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
Dim NumChar(4, 65 to 68) as integer
Dim MPerm as string
'Create table with occurences
For x = 0 to PList.Itemcount -1
for y = 1 to 4
Inc(NumChar(y, asc(PList.Item(x)[y])))
next
next
'When a char only occurs 5 times it's the missing one
for x = 1 to 4
for y = 65 to 68
MPerm = MPerm + iif(NumChar(x, y)=5, chr$(y), "")
next
next
showmessage MPerm
'= DBAC
REXX
/*REXX pgm finds one or more missing permutations from an internal list & displays them.*/
list= 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA',
"DCBA BACD BADC BDAC CBDA DBCA DCAB" /*list that is missing one permutation.*/
@.= /* [↓] needs to be as long as THINGS.*/
@abcU = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' /*an uppercase (Latin/Roman) alphabet. */
things= 4 /*number of unique letters to be used. */
bunch = 4 /*number letters to be used at a time. */
do j=1 for things /* [↓] only get a portion of alphabet.*/
$.j= substr(@abcU, j, 1) /*extract just one letter from alphabet*/
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; parse arg ? /*calls self recursively.*/
if ?>bunch then do; _=
do m=1 for bunch /*build a permutation. */
_= _ || @.m /*add permutation──►list.*/
end /*m*/
/* [↓] is in the list? */
if wordpos(_,list)==0 then say _ ' is missing from the list.'
end
else do x=1 for things /*build a permutation. */
do k=1 for ?-1
if @.k==$.x then iterate x /*was permutation built? */
end /*k*/
@.?= $.x /*define as being built. */
call permSet ?+1 /*call self recursively. */
end /*x*/
return
- output when using the default input:
DBAC is missing from the list.
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"
for a = ascii("A") to ascii("D")
for b = ascii("A") to ascii("D")
for c = ascii("A") to ascii("D")
for d = ascii("A") to ascii("D")
x = char(a) + char(b) + char(c)+ char(d)
if a!=b and a!=c and a!=d and b!=c and b!=d and c!=d
if substr(list,x) = 0 see x + " missing" + nl ok ok
next
next
next
next
Output:
DBAC missing
Ruby
given = %w{
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
}
all = given[0].chars.permutation.collect(&:join)
puts "missing: #{all - given}"
- Output:
missing: ["DBAC"]
Run BASIC
list$ = "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
for a = asc("A") to asc("D")
for b = asc("A") to asc("D")
for c = asc("A") to asc("D")
for d = asc("A") to asc("D")
x$ = chr$(a) + chr$(b) + chr$(c)+ chr$(d)
for i = 1 to 4 ' make sure each letter is unique
j = instr(x$,mid$(x$,i,1))
if instr(x$,mid$(x$,i,1),j + 1) <> 0 then goto [nxt]
next i
if instr(list$,x$) = 0 then print x$;" missing" ' found missing permutation
[nxt] next d
next c
next b
next a
- Output:
DBAC missing
Rust
Xor method suggested by Raku contributor:
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());
}
- Output:
DBAC
Scala
def fat(n: Int) = (2 to n).foldLeft(1)(_*_)
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {
val n = a.size
val fatN1 = fat(n - 1)
val fatN = fatN1 * n
val p = x / fatN1 % fatN
val (before, Seq(el, after @ _*)) = a splitAt p
el +: perm(x % fatN1, before ++ after)
}
def findMissingPerm(start: String, perms: Array[String]): String = {
for {
i <- 0 until fat(start.size)
p = perm(i, start).mkString
} if (!perms.contains(p)) return p
""
}
val perms = """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("\n")
println(findMissingPerm(perms(0), perms))
Scala 2.9.x
println("missing perms: "+("ABCD".permutations.toSet
--"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))
Seed7
$ include "seed7_05.s7i";
const func string: missingPermutation (in array string: perms) is func
result
var string: missing is "";
local
var integer: pos is 0;
var set of char: chSet is (set of char).EMPTY_SET;
var string: permutation is "";
var char: ch is ' ';
begin
if length(perms) <> 0 then
for key pos range perms[1] do
chSet := (set of char).EMPTY_SET;
for permutation range perms do
ch := permutation[pos];
if ch in chSet then
excl(chSet, ch);
else
incl(chSet, ch);
end if;
end for;
missing &:= min(chSet);
end for;
end if;
end func;
const proc: main is func
begin
writeln(missingPermutation([] ("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB")));
end func;
- Output:
DBAC
Sidef
func check_perm(arr) {
var hash = Hash()
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)
- Output:
DBAC
TI-83 BASIC
"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
Tcl
package require struct::list
set have { \
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC \
ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB \
}
struct::list foreachperm element {A B C D} {
set text [join $element ""]
if {$text ni $have} {
puts "Missing permutation(s): $text"
}
}
Uiua
Counts occurrences of each char by column and spots the outliers.
Perms ← ⊜∘⊸≠@ "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
/⊂≡(▽-⟜/↥:⊕⊃⊢⧻⊛.)⍉ Perms
- Output:
"DBAC"
Ursala
The permutation generating function is imported from the standard library below and needn't be reinvented, but its definition is shown here in the interest of comparison with other solutions.
permutations = ~&itB^?a\~&aNC *=ahPfatPRD refer ^C/~&a ~&ar&& ~&arh2falrtPXPRD
The ~&j
operator computes set differences.
#import std
#show+
main =
~&j/permutations'ABCD' -[
ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB]-
- Output:
DBAC
VBScript
Uses the 3rd method approach by adding the columns.
arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD",_
"BADC", "BDAC", "CBDA", "DBCA", "DCAB")
Dim col(4)
'supposes that a complete column have 6 of each letter.
target = (6*Asc("A")) + (6*Asc("B")) + (6*Asc("C")) + (6*Asc("D"))
missing = ""
For i = 0 To UBound(arrp)
For j = 1 To 4
col(j) = col(j) + Asc(Mid(arrp(i),j,1))
Next
Next
For k = 1 To 4
n = target - col(k)
missing = missing & Chr(n)
Next
WScript.StdOut.WriteLine missing
- Output:
DBAC
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
}
- Output:
DBAC is missing DBAC is missing DBAC is missing
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)
}
- Output:
The missing permutation is DBAC
XPL0
The list of permutations is input by using a command line like this: missperm <missperm.txt
code HexIn=26, HexOut=27;
int P, I;
[P:= 0;
for I:= 1 to 24-1 do P:= P xor HexIn(1);
HexOut(0, P);
]
- Output:
0000DBAC
zkl
Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution.
var data=L("ABCD","CABD","ACDB","DACB","BCDA","ACBD","ADCB","CDAB",
"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.
- Output:
L("DBAC")
ZX Spectrum Basic
10 LET l$="ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
20 LET length=LEN l$
30 FOR a= CODE "A" TO CODE "D"
40 FOR b= CODE "A" TO CODE "D"
50 FOR c= CODE "A" TO CODE "D"
60 FOR d= CODE "A" TO CODE "D"
70 LET x$=""
80 IF a=b OR a=c OR a=d OR b=c OR b=d OR c=d THEN GO TO 140
90 LET x$=CHR$ a+CHR$ b+CHR$ c+CHR$ d
100 FOR i=1 TO length STEP 5
110 IF x$=l$(i TO i+3) THEN GO TO 140
120 NEXT i
130 PRINT x$;" is missing"
140 NEXT d: NEXT c: NEXT b: NEXT a
- Programming Tasks
- Solutions by Programming Task
- 11l
- 360 Assembly
- 8080 Assembly
- 8086 Assembly
- Action!
- Ada
- Aime
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BBC BASIC
- Burlesque
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- Delphi
- EasyLang
- EchoLisp
- Elixir
- Erlang
- ERRE
- Factor
- Forth
- Fortran
- FreeBASIC
- Frink
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Lua
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Nim
- OCaml
- Octave
- Oz
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PowerShell
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- RapidQ
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Scala
- Seed7
- Sidef
- TI-83 BASIC
- Tcl
- Tcllib
- Uiua
- Ursala
- VBScript
- V (Vlang)
- Wren
- Wren-set
- Wren-perm
- XPL0
- Zkl
- ZX Spectrum Basic
- Pages with too many expensive parser function calls