Find the missing permutation
![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.
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( const 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 const 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( ) {
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>
C++
<lang Cpp>#include <algorithm>
- include <vector>
- include <iostream>
- include <string>
// These are lexicographically ordered static const std::string GivenPermutations[] = {
"ABCD", "ABDC", "ACBD", "ACDB", "ADBC", "ADCB", "BACD", "BADC", "BCAD", "BCDA", "BDAC", "BDCA", "CABD", "CADB", "CBAD", "CBDA", "CDAB", "CDBA", "DABC", "DACB", "DBCA", "DCAB", "DCBA"
}; static const size_t NumGivenPermutations = sizeof(GivenPermutations) / sizeof(std::string);
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.begin() + 4); if(p == permutations.front()) break; permutations.push_back(p); }
std::vector<std::string> missing; std::set_difference(permutations.begin(), permutations.end(), GivenPermutations, GivenPermutations + NumGivenPermutations, std::back_insert_iterator< std::vector<std::string> >(missing)); std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}</lang>
Clojure
<lang clojure> (use 'clojure.contrib.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)) </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
J
<lang J>deficientPermsList=: }: ] ;. _1 LF, 0 : 0 ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB )
permutations=: A.~ i.@!@# missingPerms =:-.~ permutations @ {.</lang> Or putting things together: <lang j>missingPerms =: -.~ (A.~ i.@!@#) @ {.</lang> Use:
missingPerms deficientPermsList DBAC
JavaScript
The permute() function taken from http://snippets.dzone.com/posts/show/1032 <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(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</lang>
OCaml
some utility functions: <lang ocaml>(* insert x at all positions into li and return the list of results *) let rec insert x li = match li with
| [] -> x | a::m -> (x::li) :: (List.map (fun y -> a::y) (insert x m))
(* list of all permutations of li *) let rec permutations li = match li with
| a::m -> List.flatten (List.map (insert a) (permutations m)) | _ -> [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)</lang>
resolve the task:
<lang ocaml>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</lang>
Oz
Using constraint programming for this problem may be a bit overkill...
<lang oz>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</lang>
PicoLisp
<lang 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) ) ) ) )</lang>
Output:
DBAC
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
I prefer to wrap the raw permutation generator up though: <lang tcl>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]</lang>
Ursala
The permutation generating function is imported from the standard library below
and needn't be reinvented, but its definition is shown here the interest of
comparison with other solutions.
<lang Ursala>permutations = ~&itB^?a\~&aNC *=ahPfatPRD refer ^C/~&a ~&ar&& ~&arh2falrtPXPRD</lang>
The ~&j
operator computes set differences.
<lang Ursala>#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]-</lang> output:
DBAC