Find the missing permutation

From Rosetta Code

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

[edit] C

Much of this code duplicates code from Permutation Sort task. Here ElementType is a char instead of a char *.

#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;
}

[edit] C++

#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"));
}

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

[edit] Haskell

Works with: GHC version 6.10+

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

Use:

missingPerm deficientPermsList

[edit] 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 @ {.

Or putting things together:

missingPerms =: -.~ (A.~ i.@!@#) @ {.

Use:

   missingPerms deficientPermsList
DBAC

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

some utility functions:

(* 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)

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

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

Outputs

DBAC is missing.

[edit] Python

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

Library: tcllib

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"

Outputs

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

Find the missing permutation

From Rosetta Code

Contents

[edit] C

[edit] C++

[edit] Clojure

[edit] Haskell

[edit] J

[edit] JavaScript

[edit] OCaml

[edit] Oz

[edit] PicoLisp

[edit] PureBasic

[edit] Python

[edit] Ruby

[edit] Tcl

[edit] Ursala

Views

Personal tools

Browse

Participate

Community

Google AdSense

Search

Toolbox