Find the missing permutation: Difference between revisions

Content added Content deleted
(Add 8086 assembly)
(→‎{{header|Picat}}: Moved into subsections.)
Line 2,557: Line 2,557:
=={{header|Picat}}==
=={{header|Picat}}==
Here are several approaches, including constraint modelling, sets (ordset), and permutations.
Here are several approaches, including constraint modelling, sets (ordset), and permutations.
<lang picat>import util.
import ordset.
import cp.


All assume that the variables P1 and/or Perms has been defined:
main => go.
<lang picat> P1 = ["ABCD","CABD","ACDB","DACB","BCDA","ACBD",

go =>

P1 = ["ABCD","CABD","ACDB","DACB","BCDA","ACBD",
"ADCB","CDAB","DABC","BCAD","CADB","CDBA",
"ADCB","CDAB","DABC","BCAD","CADB","CDBA",
"CBAD","ABDC","ADBC","BDCA","DCBA","BACD",
"CBAD","ABDC","ADBC","BDCA","DCBA","BACD",
"BADC","BDAC","CBDA","DBCA","DCAB"],
"BADC","BDAC","CBDA","DBCA","DCAB"],
Perms = permutations("ABCD"),
Perms = permutations("ABCD"),
% ...
</lang>


% very imperative
===Very imperative===
<lang Picat> % ...
Missing = _,
foreach(P in Perms, Missing = _)
Missing = _,
Found = false,
foreach(P in Perms, Missing = _)
foreach(T in P1)
Found = false,
foreach(T in P1)
if P == T then
Found := true
if P == T then
end
Found := true
end,
if not Found then
Missing := P
end
end
end,
end,
if not Found then
println(missing1=Missing),
Missing := P
end
end,
println(missing1=Missing).</lang>


% somewhat less imperative
===Somewhat less imperative===
<lang Picat> % ...
Missing2 = _,
foreach(P in Perms, Missing2 = _)
Missing2 = _,
foreach(P in Perms, Missing2 = _)
if not member(P,P1) then
if not member(P,P1) then
Missing2 := P
end
Missing2 := P
end,
end
end,
println(missing2=Missing2),
println(missing2=Missing2).</lang>


===Using findall===
<lang Picat> % ...
println(missing3=difference(Perms,P1)).


difference(Xs,Ys) = findall(X,(member(X,Xs),not(member(X,Ys)))).</lang>
% using findall (predicate)
println(missing3=difference(Perms,P1)),


% findall approach as a one-liner
===findall approach as a one-liner===
<lang Picat> % ...
println(missing4=findall(X,(member(X,Perms),not(member(X,P1))))),
println(missing4=findall(X,(member(X,Perms),not(member(X,P1))))).</lang>


% using ordsets
===Using ordsets===
The module <code>ordsets</code> must be imported,
println(missing5=subtract(new_ordset(Perms),new_ordset(P1))),
<lang Picat>import ordsets.
% ...
println(missing5=subtract(new_ordset(Perms),new_ordset(P1))).</lang>


% list comprehension (and member for the check)
===List comprehension===
List comprehension with <code>membchk/1</code> for the check)
println(missing6=[P:P in Perms,not member(P,P1)]),
<lang Picat> % ...
println(missing6=[P:P in Perms,not membchk(P,P1)])</lang>


% maps
===Using maps===
<lang Picat> % ...
Map = new_map(),
Map = new_map(),
foreach(P in P1) Map.put(P,1) end,
println(missing7=[P: P in Perms, not Map.has_key(P)]),
foreach(P in P1) Map.put(P,1) end,
println(missing7=[P: P in Perms, not Map.has_key(P)]).</lang>


==="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".
<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"])],
% "merge sort" variant, using sorted lists
println(missing9=[PermsSorted[I] : I in 1..PermsSorted.length, A[I] = 0].first()),
% (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,


% shorter
% variant with list comprehension
A = [cond(P == PP,1,0) : {P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"])],
println(missing10=[P:{P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"]), P != PP].first()),</lang>
println(missing9=[PermsSorted[I] : I in 1..PermsSorted.length, A[I] = 0].first()),


===Constraint modelling===
% shorter
The <code>cp</code> module must be imported.
println(missing10=[P:{P,PP} in zip(PermsSorted,P1Sorted ++ ["DUMMY"]), P != PP].first()),
<lang Picat>import cp.


% ...
% CP variant
ABCD = new_map(['A'=1,'B'=2,'C'=3,'D'=4]),
ABCD = new_map(['A'=1,'B'=2,'C'=3,'D'=4]),

% convert to integers (for the table constraint)
% convert to integers (for the table constraint)
P1Table = [ [ABCD.get(C,0) : C in P].to_array() : P in P1],
P1Table = [ [ABCD.get(C,0) : C in P].to_array() : P in P1],
Line 2,643: Line 2,654:
solve(Missing3),
solve(Missing3),
ABCD2 = "ABCD",
ABCD2 = "ABCD",
println(missing11=[ABCD2[I] : I in Missing3]),
println(missing11=[ABCD2[I] : I in Missing3]).</lang>


% matrix approach
===Matrix approach===
<lang Picat> % ...
PermsLen = Perms.length,
PermsLen = Perms.length,
P1Len = P1.length,
P1Len = P1.length,
Line 2,653: Line 2,664:
A2[I,J] := 1
A2[I,J] := 1
end,
end,
println(missing12=[Perms[I] : I in 1..PermsLen, sum([A2[I,J] : J in 1..P1Len])=0]),
println(missing12=[Perms[I] : I in 1..PermsLen, sum([A2[I,J] : J in 1..P1Len])=0]).</lang>


===Xor variant===
{{trans|Raku}}
<lang Picat> % ...
println(missing13=to_fstring("%X",reduce(^,[parse_term("0x"++P):P in P1]))).</lang>


===Count occurrences===
% inspired by the Perl 6 xor variant
Count the character with the least occurrence (=5) for each positions (1..4). Some variants.
println(missing13=to_fstring("%X",reduce(^,[parse_term("0x"++P):P in P1]))),
{{trans|K}}

<lang Picat> % ...
% count the character with the least occurrence (=5) for each positions (1..4)
% (based on my K version)
println(missing14=[[O:O=5 in Occ]:Occ in [occurrences([P[I]:P in P1]):I in 1..4]]),
println(missing14=[[O:O=5 in Occ]:Occ in [occurrences([P[I]:P in P1]):I in 1..4]]),


% variant using sorting the occurrences
% 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]]]),
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
% transpose instead of array index
println(missing15b=[C:C=_ in [sort2(O).first():T in transpose(P1),O=occurrences(T)]]),
println(missing15b=[C:C=_ in [sort2(O).first():T in transpose(P1),O=occurrences(T)]]),

% extract the values with first
% extract the values with first
println(missing15c=[sort2(O).first():T in transpose(P1),O=occurrences(T)].map(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(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))]),


println(missing15e=[S[1,1]:T in transpose(P1),S=sort2(occurrences(T))]).
% delete/2

% 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,
Perms2 = Perms,
foreach(P in P1) Perms2 := delete(Perms2,P) end,
foreach(P in P1) Perms2 := delete(Perms2,P) end,
Line 2,678: Line 2,701:


nl.
nl.


difference(Xs,Ys) = findall(X,(member(X,Xs),not(member(X,Ys)))).

% 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.


% sort a map according to values
% sort a map according to values
Line 2,693: Line 2,706:
</lang>
</lang>


Running all these snippets:
Output:
{{out}}

<pre>
<pre>
missing1 = DBAC
missing1 = DBAC
Line 2,715: Line 2,728:
missing15d = DBAC
missing15d = DBAC
missing15e = DBAC
missing15e = DBAC
missing16 = [DBAC]
missing16 = [DBAC]</pre>
</pre>


=={{header|PicoLisp}}==
=={{header|PicoLisp}}==
Retrieved from "https://rosettacode.org/wiki/Find_the_missing_permutation"