Find the missing permutation: Difference between revisions

From Rosetta Code
Content added Content deleted
No edit summary
No edit summary
Line 320: Line 320:
end
end
end</lang>
end</lang>
=={{header|PHP}}==

<lang 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 )
</lang>
=={{header|Perl 6}}==
=={{header|Perl 6}}==
Tested using Rakudo #25 Minneapolis.
Tested using Rakudo #25 Minneapolis.

Revision as of 14:11, 9 April 2010

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. 

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>

  1. include <stdio.h>
  2. 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);

}

  1. 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" };
  1. 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>

  1. include <vector>
  2. include <iostream>
  3. 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

Works with: GHC version 6.10+

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

PHP

<lang 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 ) </lang>

Perl 6

Tested using Rakudo #25 Minneapolis.

<lang perl6># The givens from Rosetta Code: 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";

  1. Get all the unique permutations of ABCD

my @letters = <A B C D>; my @perms = (@letters X~ @letters X~ @letters X~ @letters).grep: { .chars == .split().uniq.elems };

  1. Print out the missing value:

for @perms { .say if $_ eq none(@givens); }</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

PureBasic

<lang 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</lang>

Outputs 

DBAC is missing.

Python

Works with: Python version 2.6+

<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

Works with: Ruby version 1.8.7+

<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

Library: tcllib

<lang tcl>package require struct::list package require struct::set

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

}

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

}

  1. Get the real list of permutations...

set all [allCharPerms [lindex $have 0]]

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

  1. 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
Retrieved from "https://rosettacode.org/wiki/Find_the_missing_permutation?oldid=135012"