Find the missing permutation
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.
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
C
Much of this code duplicates code from Permutation Sort task. Here ElementType is a char instead of a char *. <lang c>#include <stdlib.h>
- include <stdio.h>
- include <string.h>
typedef struct pi *Permutations;
typedef char ElementType;
struct pi {
short list_size; short *counts; ElementType *crntperm;
};
Permutations PermutationIterator( ElementType *list, short listSize) {
int ix; Permutations p = (Permutations)malloc(sizeof(struct pi)); p->list_size = listSize; p->counts = (short *)malloc( p->list_size * sizeof(short)); p->crntperm = (ElementType *)malloc( p->list_size * sizeof(ElementType));
for (ix=0; ix<p->list_size; ix++) {
p->counts[ix] = ix;
p->crntperm[ix] = list[ix];
}
return p;
}
void FreePermutations( Permutations p) {
if (NULL == p) return; if (p->crntperm) free(p->crntperm); if (p->counts) free(p->counts); free(p);
}
- define FREE_Permutations(pi) do {\
FreePermutations(pi); pi=NULL; } while(0)
ElementType *FirstPermutation(Permutations p)
{
return p->crntperm;
}
ElementType *NextPermutation( Permutations p) {
int ix, j; ElementType *crntp, t;
crntp = p->crntperm;
ix = 1;
do {
t = crntp[0];
for(j=0; j<ix; j++) crntp[j] = crntp[j+1];
crntp[ix] = t;
if (p->counts[ix] > 0) break;
ix += 1;
} while (ix < p->list_size);
if (ix == p->list_size) return NULL;
p->counts[ix] -= 1;
while(--ix) {
p->counts[ix] = ix;
}
return crntp;
}
static char *pmList[] = {
"ABCD","CABD","ACDB","DACB", "BCDA","ACBD","ADCB","CDAB", "DABC","BCAD","CADB","CDBA", "CBAD","ABDC","ADBC","BDCA", "DCBA","BACD","BADC","BDAC", "CBDA","DBCA","DCAB" };
- define LISTSIZE (sizeof(pmList)/sizeof(pmList[0]))
int main( int argc, char *argv[] ) {
short size =4; ElementType *prm; ElementType mx[] = "ABCD"; int k; char ss[8];
Permutations pi = PermutationIterator(mx, size);
for ( prm = FirstPermutation(pi); prm; prm = NextPermutation(pi)) {
strncpy(ss, prm, 4); ss[4] = 0;
for (k=0; k<LISTSIZE; k++) {
if (0 == strcmp(pmList[k], ss)) break;
}
if (k==LISTSIZE) {
printf("Permutation %s was not in list\n", ss);
break;
}
}
FreePermutations( pi); return 0;
}</lang>
Haskell
<lang haskell>import Data.List import Control.Monad import Control.Arrow
deficientPermsList =
["ABCD","CABD","ACDB","DACB", "BCDA","ACBD","ADCB","CDAB", "DABC","BCAD","CADB","CDBA", "CBAD","ABDC","ADBC","BDCA", "DCBA","BACD","BADC","BDAC", "CBDA","DBCA","DCAB"]
missingPerm :: (Eq a) => a -> a missingPerm = (\\) =<< permutations . nub. join</lang> Use:
missingPerm deficientPermsList
Python
<lang python>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']</lang>
Ruby
<lang 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].split(//).permutation.collect {|perm| perm.join()}
missing = all - given # ["DBAC"]</lang>
Tcl
<lang tcl>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"</lang> Outputs
missing permutation(s): DBAC