Find the missing permutation: Difference between revisions
m
syntax highlighting fixup automation
(→{{header|Picat}}: Moved into subsections.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 57:
{{trans|C}}
<
‘DABC’, ‘BCAD’, ‘CADB’, ‘CDBA’, ‘CBAD’, ‘ABDC’, ‘ADBC’, ‘BDCA’,
‘DCBA’, ‘BACD’, ‘BADC’, ‘BDAC’, ‘CBDA’, ‘DBCA’, ‘DCAB’]
Line 71:
L.break
print(missing)</
{{out}}
Line 81:
{{trans|BBC BASIC}}
Very compact version, thanks to the clever [[#Raku|Raku]] "xor" algorithm.
<
PERMMISX CSECT
USING PERMMISX,R15 set base register
Line 109:
MISS DC 4XL1'00',C' is missing' buffer
YREGS
END PERMMISX</
{{out}}
<pre>DBAC is missing</pre>
=={{header|8080 Assembly}}==
<
puts: equ 9 ; CP/M print string
org 100h
Line 138:
db 'DABC','BCAD','CADB','CDBA','CBAD','ABDC','ADBC','BDCA'
db 'DCBA','BACD','BADC','BDAC','CBDA','DBCA','DCAB'
db 0 ; end marker </
{{out}}
<pre>Missing permutation: DBAC</pre>
=={{header|8086 Assembly}}==
<
org 100h
mov si,perms ; Start of permutations
Line 164:
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'</
{{out}}
<pre>Missing permutation: DBAC</pre>
=={{header|Action!}}==
<
DEFINE PTR="CARD"
DEFINE COUNT="23"
Line 199:
Print(missing)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Find_the_missing_permutation.png Screenshot from Atari 8-bit computer]
Line 208:
=={{header|Ada}}==
<
procedure Missing_Permutations is
subtype Permutation_Character is Character range 'A' .. 'D';
Line 258:
Ada.Text_IO.Put_Line ("Missing Permutation:");
Put (Missing_Permutation);
end Missing_Permutations;</
=={{header|Aime}}==
<
paste(record r, index x, text p, integer a)
{
Line 294:
return 0;
}</
{{Out}}
<pre>DBAC</pre>
Line 300:
=={{header|ALGOL 68}}==
Uses the XOR algorithm of the Raku sample.
<
# the list to find the missing permutation of #
[]STRING list = ( "ABCD", "CABD", "ACDB", "DACB", "BCDA"
Line 321:
print( ( REPR ABS m ) )
OD
END</
{{out}}
<pre>
Line 333:
the letter that occurs least.
<
{{out}}
<
perms⍪←↑'DABC' 'BCAD' 'CADB' 'CDBA' 'CBAD' 'ABDC' 'ADBC' 'BDCA'
perms⍪←↑'DCBA' 'BACD' 'BADC' 'BDAC' 'CBDA' 'DBCA' 'DCAB'
missing perms
DBAC</
=={{header|AppleScript}}==
Line 349:
Yosemite OS X onwards (uses NSString for sorting):
<
--------------- RAREST LETTER IN EACH COLUMN -------------
Line 607:
on |words|(s)
words of s
end |words|</
{{Out}}
<pre>"DBAC"</pre>
Line 613:
=={{header|Arturo}}==
<
"ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC"
"BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD"
Line 621:
allPerms: map permutate split "ABCD" => join
print first difference allPerms perms</
{{out}}
Line 628:
=={{header|AutoHotkey}}==
<
CompleteList := Perm( "ABCD" )
Line 657:
}
return substr(L, 1, -1)
}</
=={{header|AWK}}==
Line 663:
This reads the list of permutations as standard input and outputs the missing one.
<
split($1,a,"");
for (i=1;i<=4;++i) {
Line 681:
}
print s[1]s[2]s[3]s[4]
}</
{{Out}}
Line 688:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \
\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \
Line 699:
NEXT
PRINT $$^miss&(0) " is missing"
END</
{{out}}
<pre>
Line 707:
=={{header|Burlesque}}==
<
ln"ABCD"r@\/\\
</syntaxhighlight>
(Feed permutations via STDIN. Uses the naive method).
Line 716:
the letters with the lowest frequency:
<
ln)XXtp)><)F:)<]u[/v\[
</syntaxhighlight>
=={{header|C}}==
<
#define N 4
Line 753:
return 0;
}</
{{out}}
<pre>Missing: DBAC</pre>
Line 760:
===By permutating===
{{works with|C sharp|C#|2+}}
<
using System.Collections.Generic;
Line 800:
}
}
}</
===By xor-ing the values===
{{works with|C sharp|C#|3+}}
<
using System.Linq;
Line 821:
Console.WriteLine(string.Join("", values.Select(i => (char)i)));
}
}</
=={{header|C++}}==
<
#include <vector>
#include <set>
Line 862:
std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
return 0;
}</
=={{header|Clojure}}==
<
(use 'clojure.math.combinatorics)
(use 'clojure.set)
Line 872:
(def s1 (apply hash-set (permutations "ABCD")))
(def missing (difference s1 given))
</syntaxhighlight>
Here's a version based on the hint in the description. ''freqs'' is a sequence of letter frequency maps, one for each column. There should be 6 of each letter in each column, so we look for the one with 5.
<
"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA"
"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"])
Line 882:
(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst))
(->> freqs (map #(v->k % 5)) (apply str) println)</
=={{header|CoffeeScript}}==
<
missing_permutation = (arr) ->
# Find the missing permutation in an array of N! - 1 permutations.
Line 922:
console.log missing_permutation(arr)
</syntaxhighlight>
{{out}}
Line 931:
=={{header|Common Lisp}}==
<
'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"))
Line 944:
(cons (count letter occurs) letter))
letters))))))
(concatenate 'string (mapcar #'least-occurs (enum (length letters)))))))</
{{out}}
<pre>ROSETTA> (missing-perm *permutations*)
Line 950:
=={{header|D}}==
<
import std.stdio, std.string, std.algorithm, std.range, std.conv;
Line 992:
perms[0][maxCode - code].write;
}
}</
{{out}}
<pre>DBAC
Line 1,002:
=={{header|EchoLisp}}==
<
;; use the obvious methos
(lib 'list) ; for (permutations) function
Line 1,017:
(set-substract (make-set all-perms) (make-set perms))
→ { DBAC }
</syntaxhighlight>
=={{header|Elixir}}==
<
def find_miss_perm(head, perms) do
all_permutations(head) -- perms
Line 1,037:
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"]
IO.inspect RC.find_miss_perm( hd(perms), perms )</
{{out}}
Line 1,046:
=={{header|Erlang}}==
The obvious method. It seems fast enough (no waiting time).
<syntaxhighlight lang="erlang">
-module( find_missing_permutation ).
Line 1,063:
is_different( [_H] ) -> true;
is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ).
</syntaxhighlight>
{{out}}
<pre>
Line 1,071:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM MISSING
Line 1,105:
PRINT("Solution is: ";SOL$)
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 1,113:
=={{header|Factor}}==
Permutations are read in via STDIN.
<
"ABCD" all-permutations lines diff first print</
{{out}}
<pre>
Line 1,126:
'''Method:''' Read the permutations in as hexadecimal numbers, exclusive ORing them together gives the answer.
(This solution assumes that none of the permutations is defined as a Forth word.)
<
ABCD CABD xor ACDB xor DACB xor BCDA xor ACBD xor
ADCB xor CDAB xor DABC xor BCAD xor CADB xor CDBA xor
Line 1,132:
BADC xor BDAC xor CBDA xor DBCA xor DCAB xor
cr .( Missing permutation: ) u.
decimal</
{{out}}
<pre>Missing permutation: DBAC ok</pre>
Line 1,138:
=={{header|Fortran}}==
'''Work-around''' to let it run properly with some bugged versions (e.g. 4.3.2) of gfortran: remove the ''parameter'' attribute to the array list.
<
implicit none
Line 1,153:
write (*, *)
end program missing_permutation</
{{out}}
<pre>DBAC</pre>
Line 1,159:
=={{header|FreeBASIC}}==
===Simple count===
<
' compile with: fbc -s console
Line 1,195:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>The missing permutation is : DBAC</pre>
===Add the value's===
<
' compile with: fbc -s console
Line 1,232:
Print : Print "hit any key to end program"
Sleep
End</
<pre>output is same as the first version</pre>
===Using Xor===
<
' compile with: fbc -s console
Line 1,261:
Print : Print "hit any key to end program"
Sleep
End</
<pre>Output is the same as the first version</pre>
=={{header|GAP}}==
<
L :=
[ "ABCD", "CABD", "ACDB", "DACB", "BCDA",
Line 1,281:
# convert back to letters
s := "ABCD";
List(v, p -> List(p, i -> s[i]));</
=={{header|Go}}==
Alternate method suggested by task description:
<
import (
Line 1,331:
}
fmt.Println(string(b))
}</
Xor method suggested by Raku contributor:
<
b := make([]byte, len(given[0]))
for _, p := range given {
Line 1,341:
}
fmt.Println(string(b))
}</
{{out}} in either case:
<pre>
Line 1,349:
=={{header|Groovy}}==
Solution:
<
def missingPerms
missingPerms = {List elts, List perms ->
Line 1,357:
: missingPerms(elts - e, ePerms).collect { [e] + it }
}.sum()
}</
Test:
<
def p = ['ABCD', 'CABD', 'ACDB', 'DACB', 'BCDA', 'ACBD', 'ADCB', 'CDAB', 'DABC', 'BCAD', 'CADB', 'CDBA',
'CBAD', 'ABDC', 'ADBC', 'BDCA', 'DCBA', 'BACD', 'BADC', 'BDAC', 'CBDA', 'DBCA', 'DCAB'].collect { it as List }
def mp = missingPerms(e, p)
mp.each { println it }</
{{out}}
Line 1,373:
====Difference between two lists====
{{works with|GHC|7.10.3}}
<
import Control.Monad (join)
Line 1,409:
main :: IO ()
main = print $ missingPerm deficientPermsList</
{{Out}}
<pre>["DBAC"]</pre>
Line 1,416:
Another, more statistical, approach is to return the least common letter in each of the four columns. (If all permutations were present, letter frequencies would not vary).
<
import Data.Ord (comparing)
Line 1,452:
main :: IO ()
main = print $ missingPerm deficientPermsList</
{{Out}}
<pre>"DBAC"</pre>
Line 1,460:
{{Trans|JavaScript}}
{{Trans|Python}}
<
import Data.Bits (xor)
Line 1,494:
main :: IO ()
main = putStrLn $ missingPerm deficientPermsList</
{{Out}}
<pre>DBAC</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
procedure main()
Line 1,510:
write("The difference is : ")
every write(!givens, " ")
end</
The approach above generates a full set of permutations and calculates the difference. Changing the two commented lines to the three below will calculate on the fly and would be more efficient for larger data sets.
<
if member(givens,x) then delete(givens,x) # remove givens as they are generated
else insert(givens,x) # add back any not given</
A still more efficient version is:
<
procedure main()
Line 1,530:
if not member(givens, p) then write(p)
end</
{{libheader|Icon Programming Library}}
Line 1,537:
=={{header|J}}==
'''Solution:'''
<
missingPerms=: -.~ permutations @ {.</
'''Use:'''
<pre>data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA'
Line 1,550:
Or the above could be a single definition that works the same way:
<
Or the equivalent explicit (cf. tacit above) definition:
<
item=. {. y
y -.~ item A.~ i.! #item
)</
Or, the solution could be obtained without defining an independent program:
<
DBAC</
Here, <code>'ABCD'</code> represents the values being permuted (their order does not matter), and <code>4</code> is how many of them we have.
Line 1,567:
Yet another alternative expression, which uses parentheses instead of the [http://www.jsoftware.com/help/dictionary/d220v.htm passive operator] (<code>~</code>), would be:
<
DBAC</
Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable:
<
DBAC</
However, that's actually a false economy - not only does this approach take more code to implement (at least, in J) but we are already dealing with a data structure of approximately the size of all permutations. So what is being saved by this supposedly "more efficient" approach? Not much... (Still, perhaps this exercise is useful as an illustration of some kind of advertising concept?)
We could use parity, as suggested in the task hints:
<
DBAC</
We could use arithmetic, as suggested in the task hints:
<
DBAC</
=={{header|Java}}==
Line 1,589:
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]]
<
import com.google.common.base.Joiner;
Line 1,608:
System.out.println(joiner.join(cs));
}
}</
{{out}}
Line 1,615:
Alternate version, based on checksumming each position:
<
{
public static void main(String[] args)
Line 1,638:
System.out.println("Missing permutation: " + missingPermutation.toString());
}
}</
=={{header|JavaScript}}==
Line 1,646:
The permute() function taken from http://snippets.dzone.com/posts/show/1032
<
for(var p = -1, j, k, f, r, l = v.length, q = 1, i = l + 1; --i; q *= i);
for(x = [new Array(l), new Array(l), new Array(l), new Array(l)], j = q, k = l + 1, i = -1;
Line 1,665:
missing = all.filter(function(elem) {return list.indexOf(elem) == -1});
print(missing); // ==> DBAC</
====Functional====
<
// [a] -> [[a]]
Line 1,708:
'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\
CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB'
);</
{{Out}}
<
===ES6===
====Statistical====
=====Using a dictionary=====
<
'use strict';
Line 1,749:
// --> 'DBAC'
})();</
{{Out}}
Line 1,757:
=====Composing functional primitives=====
{{Trans|Haskell}}
<
'use strict';
Line 1,852:
// -> "DBAC"
})();</
{{Out}}
<pre>DBAC</pre>
Line 1,858:
====XOR====
Folding an xor operator over the list of character codes:
<
'use strict';
Line 1,896:
return main()
})();</
{{Out}}
<pre>DBAC</pre>
Line 1,920:
If your version of jq has transpose/0, the definition given here
(which is the same as in [[Matrix_Transpose#jq]]) may be omitted.
<
if (.[0] | length) == 0 then []
else [map(.[0])] + (map(.[1:]) | transpose)
Line 1,941:
# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]):
def encode_string: [explode[] - 65];</
'''The task''':
<
{{Out}}
<
"DBAC"</
=={{header|Julia}}==
Line 1,955:
=== Obvious method ===
Calculate all possible permutations and return the first not included in the array.
<
function missingperm(arr::Vector)
Line 1,967:
"CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC",
"CBDA", "DBCA", "DCAB"]
@show missingperm(arr)</
{{out}}
Line 1,974:
=== Alternative method 1 ===
{{trans|Python}}
<
missperm = string()
for pos in 1:length(arr[1])
Line 1,986:
return missperm
end
</syntaxhighlight>
=== Alternative method 2 ===
{{trans|Raku}}
<
len = length(arr[1])
xorval = zeros(UInt8, len)
Line 2,006:
@btime missingperm1(arr)
@btime missingperm2(arr)
</
<pre>
missingperm(arr) = "DBAC"
Line 2,017:
=={{header|K}}==
<
g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB")
Line 2,040:
p2@&~p2 _lin p
"DBAC"</
Alternative approach:
<
table:{b@<b:(x@*:'a),'#:'a:=x}
,/"ABCD"@&:'{5=(table p[;x])[;1]}'!4
"DBAC"</
Third approach (where p is the given set of permutations):
<syntaxhighlight lang="k">
,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p
</syntaxhighlight>
=={{header|Kotlin}}==
<
fun <T> permute(input: List<T>): List<List<T>> {
Line 2,087:
for (perm in missing) println(perm.joinToString(""))
}
}</
{{out}}
Line 2,096:
=={{header|Lua}}==
Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight
<
local permList, pStr = {
"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
Line 2,105:
pStr = table.concat(perm)
if not tablex.find(permList, pStr) then print(pStr) end
end</
{{out}}
<pre>DBAC</pre>
=={{header|Maple}}==
<
perm := table():
for letter in "ABCD" do
Line 2,120:
end do:
end do:
print(StringTools:-Join(ListTools:-Flatten([indices(perm)], 4)[sort(map(x->60-x, ListTools:-Flatten([entries(perm)],4)),'output=permutation')], "")):</
{{Out|Output}}
<pre>"DBAC"</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC",
"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"};
Line 2,132:
->{"DBAC"}</
=={{header|MATLAB}}==
This solution is designed to work on a column vector of strings. This will not work with a cell array or row vector of strings.
<
permsList = perms(list(1,:)); %Generate all permutations of the 4 letters
Line 2,163:
end %for
end %fingMissingPerms</
{{out}}
<
'CABD';
'ACDB';
Line 2,220:
ans =
DBAC</
=={{header|Nim}}==
{{trans|Python}}
<
proc missingPermutation(arr: openArray[string]): string =
Line 2,242:
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB""".splitWhiteSpace()
echo missingPermutation(given)</
{{out}}
<pre>DBAC</pre>
Line 2,249:
some utility functions:
<
let rec insert x = function
| [] -> [[x]]
Line 2,266:
(* convert a char list to a string *)
let string_of_chars cl =
String.concat "" (List.map (String.make 1) cl)</
resolve the task:
<
"ABCD";"CABD";"ACDB";"DACB";
"BCDA";"ACBD";"ADCB";"CDAB";
Line 2,285:
let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms
let () = List.iter print_endline results</
Alternate method : if we had all permutations,
Line 2,293:
of the number of occurences of each letter.
The following program works with permutations of at least 3 letters:
<
let n = String.length s in
Array.init n (fun i -> int_of_char s.[i] - 65);;
Line 2,322:
find_missing deficient_perms;;
(* - : string = "DBAC" *)</
=={{header|Octave}}==
<
'BCDA';'ACBD';'ADCB';'CDAB'; ...
'DABC';'BCAD';'CADB';'CDBA'; ...
Line 2,339:
bits(there) = 0;
missing = dec2base(find(bits)-1,'ABCD')
</syntaxhighlight>
=={{header|Oz}}==
Using constraint programming for this problem may be a bit overkill...
<
GivenPermutations =
["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"
Line 2,362:
{System.showInfo "Missing: "#P}
end
end</
=={{header|PARI/GP}}==
<
v=apply(u->permtonum(apply(n->n-64,Vec(Vecsmall(u)))),v);
t=numtoperm(4, binomial(4!,2)-sum(i=1,#v,v[i]));
Strchr(apply(n->n+64,t))</
{{out}}
<pre>%1 = "DBAC"</pre>
Line 2,374:
=={{header|Pascal}}==
like [[c]], summation, and [[Raku]] XORing
<
{$MODE DELPHI} //for result
Line 2,436:
writeln(CountOccurences,' is missing');
writeln(CheckXOR,' is missing');
end.</
DBAC is missing</pre>
Line 2,444:
the first missing rotation is the target.
<
my %hash; @hash{@_} = ();
for my $s (@_) { exists $hash{$_} or return $_
Line 2,453:
@perms = qw(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB);
print check_perm(@perms), "\n";</
{{out}}
Line 2,463:
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 :)
<
or if you don't like eval...
<
print '';</
Every permutation has a "reverse", just take all reverses and remove the "normals".
<
my %h = map { $_, '' } reverse =~ /\w+/g;
delete @h{ /\w+/g };
print %h, "\n";</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"ABCD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CABD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ACDB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DACB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"BCDA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ACBD"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"ADCB"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"CDAB"</span><span style="color: #0000FF;">,</span>
Line 2,523:
<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>
<!--</
{{out}}
<pre>
Line 2,533:
=={{header|PHP}}==
<
$finalres = Array();
function permut($arr,$result=array()){
Line 2,553:
permut($given);
print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC )
</syntaxhighlight>
=={{header|Picat}}==
Line 2,559:
All assume that the variables P1 and/or Perms has been defined:
<
"ADCB","CDAB","DABC","BCAD","CADB","CDBA",
"CBAD","ABDC","ADBC","BDCA","DCBA","BACD",
Line 2,565:
Perms = permutations("ABCD"),
% ...
</syntaxhighlight>
===Very imperative===
<
Missing = _,
foreach(P in Perms, Missing = _)
Line 2,581:
end
end,
println(missing1=Missing).</
===Somewhat less imperative===
<
Missing2 = _,
foreach(P in Perms, Missing2 = _)
Line 2,591:
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 <code>ordsets</code> must be imported,
<
% ...
println(missing5=subtract(new_ordset(Perms),new_ordset(P1))).</
===List comprehension===
List comprehension with <code>membchk/1</code> 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. <code>zip/2</code> requires that the length of the two lists are the same, hence the "dummy".
<
PermsSorted = Perms.sort(),
P1Sorted = P1.sort(),
Line 2,637:
% shorter
println(missing10=[P:{P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"]), P != PP].first()),</
===Constraint modelling===
The <code>cp</code> module must be imported.
<
% ...
Line 2,654:
solve(Missing3),
ABCD2 = "ABCD",
println(missing11=[ABCD2[I] : I in Missing3]).</
===Matrix approach===
<
PermsLen = Perms.length,
P1Len = P1.length,
Line 2,664:
A2[I,J] := 1
end,
println(missing12=[Perms[I] : I in 1..PermsLen, sum([A2[I,J] : J in 1..P1Len])=0]).</
===Xor variant===
{{trans|Raku}}
<
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.
{{trans|K}}
<
println(missing14=[[O:O=5 in Occ]:Occ in [occurrences([P[I]:P in P1]):I in 1..4]]),
Line 2,704:
% 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:
Line 2,731:
=={{header|PicoLisp}}==
<
(mapcar chop
(quote
Line 2,745:
(rot L) )
(unless (member Lst *PermList) # Check
(prinl Lst) ) ) ) )</
{{out}}
<pre>DBAC</pre>
Line 2,752:
{{works with|PowerShell|4.0}}
<syntaxhighlight lang="powershell">
function permutation ($array) {
function generate($n, $array, $A) {
Line 2,809:
)
$perm | where{-not $find.Contains($_)}
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 2,816:
=={{header|PureBasic}}==
<
Define.i i, j
Define.s a
Line 2,854:
Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA"
Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"
EndDataSection</
Based on the [[Permutations#PureBasic|Permutations]] task,
the solution could be:
<
NewList a.s()
findPermutations(a(), "ABCD", 4)
Line 2,872:
Print(#CRLF$ + "Press ENTER to exit"): Input()
EndIf</
=={{header|Python}}==
===Python: Calculate difference when compared to all permutations===
{{works with|Python|2.6+}}
<
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
Line 2,884:
allPerms = [''.join(x) for x in permutations(given[0])]
missing = list(set(allPerms) - set(given)) # ['DBAC']</
===Python:Counting lowest frequency character at each position===
Line 2,890:
i.e. it never needs to generate the full set of expected permutations.
<
def missing_permutation(arr):
"Find the missing permutation in an array of N! - 1 permutations."
Line 2,921:
print missing_permutation(given)
</syntaxhighlight>
===Python:Counting lowest frequency character at each position: functional===
Uses the same method as explained directly above,
but calculated in a more functional manner:
<
>>> given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'''.split()
>>> ''.join(Counter(x).most_common()[-1][0] for x in zip(*given))
'DBAC'
>>> </
;Explanation
Line 2,940:
created by the call to <code>most_common()</code>
is the least common character.
<
>>> pp(list(zip(*given)), width=120)
[('A', 'C', 'A', 'D', 'B', 'A', 'A', 'C', 'D', 'B', 'C', 'C', 'C', 'A', 'A', 'B', 'D', 'B', 'B', 'B', 'C', 'D', 'D'),
Line 2,957:
>>> ''.join([Counter(x).most_common()[-1][0] for x in zip(*given)])
'DBAC'
>>> </
===Python:Folding XOR over the set of strings===
Surfacing the missing bits:
{{Trans|JavaScript}}
<
from functools import reduce
Line 2,984:
[0, 0, 0, 0]
)
]))</
{{Out}}
<pre>DBAC</pre>
Line 2,992:
Credit to [[#Raku|Raku]] for the method, and noting that the strings are valid hexadecimal numbers.
<
ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD
Line 3,001:
0 swap witheach ^
number$ echo$
base release</
{{out}}
Line 3,009:
=={{header|R}}==
This uses the "combinat" package, which is a standard R package:
<syntaxhighlight lang="text">
library(combinat)
Line 3,022:
setdiff(perms3, incomplete)
</syntaxhighlight>
{{out}}
Line 3,030:
=={{header|Racket}}==
<
#lang racket
Line 3,066:
c))
;; -> '(D B A C)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
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;</
{{out}}<pre>DBAC</pre>
Of course, all of these solutions are working way too hard,
when you can just xor all the bits,
and the missing one will just pop right out:
<syntaxhighlight lang="raku"
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB>;</
{{out}}<pre>DBAC</pre>
=={{header|RapidQ}}==
<syntaxhighlight lang="vb">
Dim PList as QStringList
PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB"
Line 3,110:
showmessage MPerm
'= DBAC
</syntaxhighlight>
=={{header|REXX}}==
<
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.*/
Line 3,141:
call permSet ?+1 /*call self recursively. */
end /*x*/
return</
{{out|output|text= when using the default input:}}
<pre>
Line 3,148:
=={{header|Ring}}==
<
list = "ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB"
Line 3,162:
next
next
</syntaxhighlight>
Output:
<pre>
Line 3,170:
=={{header|Ruby}}==
{{works with|Ruby|2.0+}}
<
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
Line 3,177:
all = given[0].chars.permutation.collect(&:join)
puts "missing: #{all - given}"</
{{out}}
<pre>
Line 3,184:
=={{header|Run BASIC}}==
<
for a = asc("A") to asc("D")
Line 3,199:
next c
next b
next a</
{{out}}
<pre>DBAC missing</pre>
Line 3,206:
{{trans|Go}}
Xor method suggested by Raku contributor:
<
"ABCD",
"CABD",
Line 3,245:
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,254:
{{libheader|Scala}}
{{works with|Scala|2.8}}
<
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {
val n = a.size
Line 3,293:
DBCA
DCAB""".stripMargin.split("\n")
println(findMissingPerm(perms(0), perms))</
===Scala 2.9.x===
{{works with|Scala|2.9.1}}
<
--"ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB".stripMargin.split(" ").toSet))</
=={{header|Seed7}}==
<
const func string: missingPermutation (in array string: perms) is func
Line 3,333:
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",
"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB")));
end func;</
{{out}}
Line 3,342:
=={{header|Sidef}}==
{{trans|Perl}}
<
var hash = Hash()
hash.set_keys(arr...)
Line 3,356:
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB)
say check_perm(perms)</
{{out}}
<pre>
Line 3,363:
=={{header|TI-83 BASIC}}==
<
"ABCD"→Str1
length(Str0)→L
Line 3,396:
sub(Str4,2,4)→Str4
Disp "MISSING"
Disp Str4</
=={{header|Tcl}}==
{{tcllib|struct::list}}
<
package require struct::list
Line 3,414:
}
}
</syntaxhighlight>
=={{header|Ursala}}==
Line 3,420:
and needn't be reinvented, but its definition is shown here in the interest of
comparison with other solutions.
<
The <code>~&j</code> operator computes set differences.
<
#show+
Line 3,450:
CBDA
DBCA
DCAB]-</
{{out}}
<pre>
Line 3,458:
=={{header|VBScript}}==
Uses the 3rd method approach by adding the columns.
<syntaxhighlight lang="vb">
arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_
Line 3,483:
WScript.StdOut.WriteLine missing
</syntaxhighlight>
{{Out}}
Line 3,492:
{{libheader|Wren-set}}
{{libheader|Wren-perm}}
<
import "./perm" for Perm
Line 3,516:
System.print("There are %(missing.count) missing permutations, namely:\n")
System.print(missing)
}</
{{out}}
Line 3,527:
missperm <missperm.txt
<
int P, I;
[P:= 0;
for I:= 1 to 24-1 do P:= P xor HexIn(1);
HexOut(0, P);
]</
{{out}}
Line 3,541:
=={{header|zkl}}==
Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution.
<
"DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA",
"DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB");
Utils.Helpers.permute(["A".."D"]).apply("concat").copy().remove(data.xplode());</
Copy creates a read/write list from a read only list.
xplode() pushes all elements of data as parameters to remove.
Line 3,553:
=={{header|ZX Spectrum Basic}}==
<
20 LET length=LEN l$
30 FOR a= CODE "A" TO CODE "D"
Line 3,566:
120 NEXT i
130 PRINT x$;" is missing"
140 NEXT d: NEXT c: NEXT b: NEXT a</
|