Find the missing permutation

From Rosetta Code
Jump to: navigation, search
Task
Find the missing permutation
You are encouraged to solve this task according to the task description, using any language you may know.

These are all of the permutations of the symbols A, B, C and D, except for one that's not listed. Find that missing permutation.

(cf. Permutations)

There is an obvious method : enumerating all permutations of A, B, C, D, and looking for the missing one.

There is an alternate method. Hint : if all permutations were here, how many times would A appear in each position ? What is the parity of this number ?

ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB

Contents

[edit] 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;

[edit] 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)
}

[edit] 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

[edit] 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\[
 

[edit] 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

[edit] 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;
}

[edit] C#

Works with: C# version 2+
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);
}
}
}
}
}

[edit] 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)

[edit] 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

[edit] 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"

[edit] 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 Perl 6 (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

[edit] 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"]

[edit] 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

[edit] 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]));

[edit] 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 Perl 6 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

[edit] 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]

[edit] Haskell

Works with: GHC version 6.10+
import Data.List
import Control.Monad
import Control.Arrow
 
missingPerm :: Eq a => [[a]] -> [[a]]
missingPerm = (\\) =<< permutations . nub . join
 
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 = do
print $ missingPerm deficientPermsList
Output:
["DBAC"]

[edit] Icon and Unicon

link strings    # for permutes
 
procedure main()
givens := set![ "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB",
"CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"]
 
every insert(full := set(), permutes("ABCD")) # generate all permutations
givens := full--givens # and difference
 
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.

every x := permutes("ABCD") do                    # generate all permutations 
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:

link strings
 
procedure main()
givens := set("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD",
"BADC", "BDAC", "CBDA", "DBCA", "DCAB")
 
every p := permutes("ABCD") do
if not member(givens, p) then write(p)
 
end

member 'strings' provides permutes(s) which generates all permutations of a string

[edit] 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

[edit] 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 also get into the parity issues, but this task does not actually define a parity specific result (beyond finding the missing permutation). So let's just leave parity as food for thought. Because thoughts need chewy, tasty things to gnaw on.

[edit] 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());
}
}

[edit] JavaScript

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

[edit] 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"

[edit] Mathematica

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"}

[edit] 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

[edit] Nimrod

Translation of: Python
import strutils
 
proc missingPermutation(arr): 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""".split()
 
echo missingPermutation(given)
Output:
DBAC

[edit] 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" *)

[edit] 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')
 

[edit] 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

[edit] 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"

[edit] 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 )
 

[edit] 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

[edit] 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.tree.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 [~^] @givens;
Output:
DBAC

[edit] 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

[edit] 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

[edit] Python

[edit] Python: Calculate difference when compared to all permutations

Works with: Python version 2.6+
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']

[edit] 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)
 

[edit] 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'
>>>

[edit] 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"

[edit] 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)
 

[edit] REXX

/*REXX program finds a  missing permuation  from an internal list.      */
list = 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA',
'CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'
@.=
@abcU='ABCDEFGUIJKLMNOPQRSTUVWXYZ' /*an uppercase (Latin) alphabet. */
things=4
bunch =4
do j=1 for things /*build list of permutation obj. */
$.j=substr(@abcu,j,1)
end /*j*/
call permset 1
exit /*stick a fork in it, we're done.*/
/*─────────────────────────────────────PERMSET subroutine───────────────*/
permset: procedure expose $. @. bunch list things; parse arg ?
if ?>bunch then do
_=; do m=1 for bunch
_=_ || @.m
end /*m*/
 
if wordpos(_,list)==0 then say _ ' is missing from the list.'
end
else do x=1 for things /*construct a new permuation. */
 
do k=1 for ?-1
if @.k==$.x then iterate x
end /*k*/
@.?=$.x
call permset ?+1
end /*x*/
Output:
DBAC  is missing from the list.

[edit] Ruby

Works with: Ruby version 1.8.7+
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].split(//).permutation.collect {|perm| perm.join('')}
 
missing = all - given # ["DBAC"]

[edit] 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

[edit] Scala

Library: Scala
Works with: Scala version 2.8
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))

[edit] Scala 2.9.x

Works with: Scala version 2.9.1
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))

[edit] 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

[edit] Tcl

Library: Tcllib (Package: struct::list)
Library: Tcllib (Package: struct::set)
package require struct::list
package require struct::set
 
# Make complete list of permutations of a string of characters
proc allCharPerms s {
set perms {}
set p [struct::list firstperm [split $s {}]]
while {$p ne ""} {
lappend perms [join $p {}]
set p [struct::list nextperm $p]
}
return $perms
}
 
# The set of provided permutations (wrapped for convenience)
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
}
# Get the real list of permutations...
set all [allCharPerms [lindex $have 0]]
# Find the missing one(s)!
set missing [struct::set difference $all $have]
puts "missing permutation(s): $missing"
Output:
missing permutation(s): DBAC

I prefer to wrap the raw permutation generator up though:

package require struct::list
package require struct::set
 
proc foreachPermutation {varName listToPermute body} {
upvar 1 $varName v
set p [struct::list firstperm $listToPermute]
for {} {$p ne ""} {set p [struct::list nextperm $p]} {
set v $p; uplevel 1 $body
}
}
 
proc findMissingCharPermutations {set} {
set all {}
foreachPermutation charPerm [split [lindex $set 0] {}] {
lappend all [join $charPerm {}]
}
return [struct::set difference $all $set]
}
 
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
}
set missing [findMissingCharPermutations $have]

[edit] 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

[edit] 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

[edit] 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")
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox