Find the missing permutation: Difference between revisions

 

<pre>

</pre>

 

 

* &nbsp; [[Permutations]])

<br><br>

 

=={{header|360 Assembly}}==

{{trans|BBC BASIC}}

PERMMISX CSECT

USING PERMMISX,R15 set base register

MISS DC 4XL1'00',C' is missing' buffer

YREGS

{{out}}

<pre>DBAC is missing</pre>

 

=={{header|Ada}}==

 

procedure Missing_Permutations is

subtype Permutation_Character is Character range 'A' .. 'D';

Ada.Text_IO.Put_Line ("Missing Permutation:");

Put (Missing_Permutation);

 

 

 

 

 

 

 

 

on run

"ADCB CDAB DABC BCAD CADB CDBA " & ¬

"CBAD ABDC ADBC BDCA DCBA BACD " & ¬

--> "DBAC"

 

 

 

 

end script

 

script

end script

end script

 

tell mReturn(f)

set lng to length of xs

repeat with i from 1 to lng

end repeat

end tell

 

tell mReturn(f)

set v to startValue

set lng to length of xs

end repeat

return v

end tell

 

set my text item delimiters to dlm

 

 

-- Lift 2nd class handler function into 1st class script wrapper

else

script

end script

end if

 

{{Out}}

<pre>"DBAC"</pre>

 

=={{header|AutoHotkey}}==

 

CompleteList := Perm( "ABCD" )

}

return substr(L, 1, -1)

 

=={{header|AWK}}==

This reads the list of permutations as standard input and outputs the missing one.

 

split($1,a,"");

for (i=1;i<=4;++i) {

}

print s[1]s[2]s[3]s[4]

 

{{Out}}

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

perms$() = "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", \

\ "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", \

NEXT

PRINT $$^miss&(0) " is missing"

{{out}}

<pre>

=={{header|Burlesque}}==

 

ln"ABCD"r@\/\\

 

(Feed permutations via STDIN. Uses the naive method).

the letters with the lowest frequency:

 

ln)XXtp)><)F:)<]u[/v\[

 

=={{header|C}}==

 

#define N 4

return 0;

{{out}}

<pre>Missing: DBAC</pre>

 

=={{header|C sharp|C#}}==

===By permutating===

{{works with|C sharp|C#|2+}}

using System.Collections.Generic;

 

}

}

===By xor-ing the values===

{{works with|C sharp|C#|3+}}

using System.Linq;

 

Console.WriteLine(string.Join("", values.Select(i => (char)i)));

}

 

=={{header|Clojure}}==

(use 'clojure.math.combinatorics)

(use 'clojure.set)

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

"DABC" "BCAD" "CADB" "CDBA" "CBAD" "ABDC" "ADBC" "BDCA"

"DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"])

(defn v->k [fqmap v] (->> fqmap (filter #(-> % second (= v))) ffirst))

 

 

=={{header|CoffeeScript}}==

 

missing_permutation = (arr) ->

# Find the missing permutation in an array of N! - 1 permutations.

console.log missing_permutation(arr)

 

{{out}}

 

=={{header|Common Lisp}}==

'("ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"

"CBAD" "ABDC" "ADBC" "BDCA" "DCBA" "BACD" "BADC" "BDAC" "CBDA" "DBCA" "DCAB"))

(cons (count letter occurs) letter))

letters))))))

{{out}}

<pre>ROSETTA> (missing-perm *permutations*)

 

=={{header|D}}==

import std.stdio, std.string, std.algorithm, std.range, std.conv;

 

 

// Version 2: xor all the ASCII values, the uneven one

enum len = 4;

char[len] b = 0;

perms[0][maxCode - code].write;

}

{{out}}

<pre>DBAC

DBAC

DBAC</pre>

 

=={{header|EchoLisp}}==

;; use the obvious methos

(lib 'list) ; for (permutations) function

(set-substract (make-set all-perms) (make-set perms))

→ { DBAC }

 

=={{header|Elixir}}==

def find_miss_perm(head, perms) do

all_permutations(head) -- perms

"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"]

 

 

{{out}}

=={{header|Erlang}}==

The obvious method. It seems fast enough (no waiting time).

-module( find_missing_permutation ).

 

is_different( [_H] ) -> true;

is_different( [H | T] ) -> not lists:member(H, T) andalso is_different( T ).

{{out}}

<pre>

 

=={{header|ERRE}}==

PROGRAM MISSING

 

PRINT("Solution is: ";SOL$)

END PROGRAM

{{out}}

<pre>

Solution is: DBAC

</pre>

 

=={{header|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.

 

implicit none

write (*, *)

 

{{out}}

<pre>DBAC</pre>

 

=={{header|GAP}}==

L :=

[ "ABCD", "CABD", "ACDB", "DACB", "BCDA",

# convert back to letters

s := "ABCD";

=={{header|Go}}==

Alternate method suggested by task description:

 

import (

}

fmt.Println(string(b))

b := make([]byte, len(given[0]))

for _, p := range given {

}

fmt.Println(string(b))

{{out}} in either case:

<pre>

=={{header|Groovy}}==

Solution:

def missingPerms

missingPerms = {List elts, List perms ->

: missingPerms(elts - e, ePerms).collect { [e] + it }

}.sum()

 

Test:

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)

 

{{out}}

 

=={{header|Haskell}}==

 

missingPerm = (\\) =<< permutations . nub . join

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

write("The difference is : ")

every write(!givens, " ")

 

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.

 

if member(givens,x) then delete(givens,x) # remove givens as they are generated

 

A still more efficient version is:

procedure main()

if not member(givens, p) then write(p)

 

{{libheader|Icon Programming Library}}

=={{header|J}}==

'''Solution:'''

'''Use:'''

<pre>data=: >;: 'ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA'

Or the above could be a single definition that works the same way:

 

 

Or the equivalent explicit (cf. tacit above) definition:

item=. {. y

y -.~ item A.~ i.! #item

 

Or, the solution could be obtained without defining an independent program:

 

 

Here, <code>'ABCD'</code> represents the values being permuted (their order does not matter), and <code>4</code> is how many of them we have.

Yet another alternative expression, which uses parentheses instead of the [http://www.jsoftware.com/help/dictionary/d220v.htm passive operator] (<code>~</code>), would be:

 

 

Of course the task suggests that the missing permutation can be found without generating all permutations. And of course that is doable:

 

 

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 use parity, as suggested in the task hints:

 

We could use arithmetic, as suggested in the task hints:

 

=={{header|Java}}==

Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]]

 

 

import com.google.common.base.Joiner;

System.out.println(joiner.join(cs));

}

 

{{out}}

Alternate version, based on checksumming each position:

 

{

public static void main(String[] args)

System.out.println("Missing permutation: " + missingPermutation.toString());

}

 

=={{header|JavaScript}}==

 

The permute() function taken from http://snippets.dzone.com/posts/show/1032

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;

 

missing = all.filter(function(elem) {return list.indexOf(elem) == -1});

 

====Functional====

 

 

// [a] -> [[a]]

'ABCD\nCABD\nACDB\nDACB\nBCDA\nACBD\nADCB\nCDAB\nDABC\nBCAD\nCADB\n\

CDBA\nCBAD\nABDC\nADBC\nBDCA\nDCBA\nBACD\nBADC\nBDAC\nCBDA\nDBCA\nDCAB'

 

{{Out}}

 

 

===ES6===

====Statistical====

'use strict';

 

return transpose(xs.split(' ')

.map(x => x.split('')))

.map(dct => { // character with frequency below mean of distribution ?

let ks = Object.keys(dct),

 

// --> 'DBAC'

 

{{Out}}

<pre>DBAC</pre>

If your version of jq has transpose/0, the definition given here

(which is the same as in [[Matrix_Transpose#jq]]) may be omitted.

if (.[0] | length) == 0 then []

else [map(.[0])] + (map(.[1:]) | transpose)

# encode a string (e.g. "ABCD") as an array (e.g. [0,1,2,3]):

 

'''The task''':

 

{{Out}}

 

=={{header|Julia}}==

 

 

end

end

 

 

 

end

end

end

 

<pre>

</pre>

 

=={{header|K}}==

 

g: ("ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB")

p2@&~p2 _lin p

 

Alternative approach:

table:{b@<b:(x@*:'a),'#:'a:=x}

,/"ABCD"@&:'{5=(table p[;x])[;1]}'!4

 

Third approach (where p is the given set of permutations):

,/p2@&~(p2:{x@m@&n=(#?:)'m:!n#n:#x}[*p]) _lin p

 

=={{header|Lua}}==

Using the popular Penlight extension module - https://luarocks.org/modules/steved/penlight

local permList, pStr = {

"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",

pStr = table.concat(perm)

if not tablex.find(permList, pStr) then print(pStr) end

{{out}}

<pre>DBAC</pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

"ADCB" , "CDAB", "DABC", "BCAD" , "CADB", "CDBA" , "CBAD" , "ABDC",

"ADBC" , "BDCA", "DCBA" , "BACD", "BADC", "BDAC" , "CBDA", "DBCA", "DCAB"};

 

 

 

=={{header|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.

 

 

permsList = perms(list(1,:)); %Generate all permutations of the 4 letters

end %for

 

{{out}}

'CABD';

'ACDB';

ans =

 

 

=={{header|Nim}}==

{{trans|Python}}

 

result = ""

if arr.len == 0: return

if arr.len == 1: return arr[0][1] & arr[0][0]

 

var s: set[char] = {}

for permutation in arr:

 

const given = """ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA

 

{{out}}

<pre>DBAC</pre>

 

some utility functions:

let rec insert x = function

| [] -> [[x]]

(* convert a char list to a string *)

let string_of_chars cl =

 

resolve the task:

 

"ABCD";"CABD";"ACDB";"DACB";

"BCDA";"ACBD";"ADCB";"CDAB";

let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms

 

 

Alternate method : if we had all permutations,

of the number of occurences of each letter.

The following program works with permutations of at least 3 letters:

let n = String.length s in

Array.init n (fun i -> int_of_char s.[i] - 65);;

 

find_missing deficient_perms;;

 

=={{header|Octave}}==

'BCDA';'ACBD';'ADCB';'CDAB'; ...

'DABC';'BCAD';'CADB';'CDBA'; ...

bits(there) = 0;

missing = dec2base(find(bits)-1,'ABCD')

 

=={{header|Oz}}==

Using constraint programming for this problem may be a bit overkill...

GivenPermutations =

["ABCD" "CABD" "ACDB" "DACB" "BCDA" "ACBD" "ADCB" "CDAB" "DABC" "BCAD" "CADB" "CDBA"

{System.showInfo "Missing: "#P}

end

=={{header|PARI/GP}}==

v=apply(u->permtonum(apply(n->n-64,Vec(Vecsmall(u)))),v);

t=numtoperm(4, binomial(4!,2)-sum(i=1,#v,v[i]));

{{out}}

<pre>%1 = "DBAC"</pre>

=={{header|Pascal}}==

{$MODE DELPHI} //for result

 

For row := low(tcol) to High(tcol) do

IF SumElemCol[col,row]=fibN_1 then

end;

 

For row := low(tmissPerm) to High(tmissPerm) do

For col := low(tcol) to High(tcol) do

end;

 

writeln(CountOccurences,' is missing');

writeln(CheckXOR,' is missing');

DBAC is missing</pre>

 

the first missing rotation is the target.

 

my %hash; @hash{@_} = ();

for my $s (@_) { exists $hash{$_} or return $_

@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);

 

{{out}}

<pre>DBAC</pre>

 

 

=={{header|Phix}}==

{{out}}

<pre>

 

=={{header|PHP}}==

$finalres = Array();

function permut($arr,$result=array()){

permut($given);

print_r(array_diff($finalres,$givenPerms)); // Array ( [20] => DBAC )

 

=={{header|PicoLisp}}==

(mapcar chop

(quote

(rot L) )

(unless (member Lst *PermList) # Check

{{out}}

<pre>DBAC</pre>

 

{{works with|PowerShell|4.0}}

function permutation ($array) {

function generate($n, $array, $A) {

)

$perm | where{-not $find.Contains($_)}

<b>Output:</b>

<pre>

 

=={{header|PureBasic}}==

Define.i i, j

Define.s a

Data.s "DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA"

Data.s "DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB"

 

Based on the [[Permutations#PureBasic|Permutations]] task,

the solution could be:

NewList a.s()

findPermutations(a(), "ABCD", 4)

Print(#CRLF$ + "Press ENTER to exit"): Input()

 

=={{header|Python}}==

===Python: Calculate difference when compared to all permutations===

{{works with|Python|2.6+}}

 

given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA

allPerms = [''.join(x) for x in permutations(given[0])]

 

 

===Python:Counting lowest frequency character at each position===

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

print missing_permutation(given)

 

===Python:Counting lowest frequency character at each position: functional===

Uses the same method as explained directly above,

but calculated in a more functional manner:

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

created by the call to <code>most_common()</code>

is the least common character.

>>> 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'),

>>> ''.join([Counter(x).most_common()[-1][0] for x in zip(*given)])

'DBAC'

 

=={{header|R}}==

This uses the "combinat" package, which is a standard R package:

library(combinat)

 

 

setdiff(perms3, incomplete)

 

{{out}}

 

=={{header|Racket}}==

#lang racket

 

c))

;; -> '(D B A C)

 

=={{header|RapidQ}}==

Dim PList as QStringList

PList.addItems "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB"

showmessage MPerm

'= DBAC

 

=={{header|REXX}}==

@.= /* [↓] needs to be as long as THINGS.*/

do j=1 for things /* [↓] only get a portion of alphabet.*/

end /*j*/ /* [↑] build a letter array for speed.*/

call permSet 1 /*invoke PERMSET subroutine recursively*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

if ?>bunch then do; _=

do m=1 for bunch /*build a permutation. */

end /*m*/

/* [↓] is in the list? */

else do x=1 for things /*build a permutation. */

do k=1 for ?-1

end /*k*/

end /*x*/

<pre>

DBAC is missing from the list.

 

=={{header|Ring}}==

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

next

next

Output:

<pre>

=={{header|Ruby}}==

{{works with|Ruby|2.0+}}

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].chars.permutation.collect(&:join)

{{out}}

<pre>

 

=={{header|Run BASIC}}==

 

for a = asc("A") to asc("D")

next c

next b

{{out}}

<pre>DBAC missing</pre>

 

=={{header|Scala}}==

{{libheader|Scala}}

{{works with|Scala|2.8}}

def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {

val n = a.size

DBCA

DCAB""".stripMargin.split("\n")

 

===Scala 2.9.x===

{{works with|Scala|2.9.1}}

 

=={{header|Seed7}}==

const func string: missingPermutation (in array string: perms) is func

"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC",

"BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB")));

 

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

arr.each { |s|

}

}

 

var perms = %w(ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA

 

{{out}}

<pre>

DBAC

</pre>

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

}

}

 

=={{header|Ursala}}==

and needn't be reinvented, but its definition is shown here in the interest of

comparison with other solutions.

The <code>~&j</code> operator computes set differences.

#show+

 

CBDA

DBCA

{{out}}

<pre>

=={{header|VBScript}}==

Uses the 3rd method approach by adding the columns.

arrp = Array("ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",_

"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",_

 

WScript.StdOut.WriteLine missing

 

{{Out}}

<pre>DBAC</pre>

 

=={{header|XPL0}}==

missperm <missperm.txt

 

int P, I;

[P:= 0;

for I:= 1 to 24-1 do P:= P xor HexIn(1);

HexOut(0, P);

 

{{out}}

=={{header|zkl}}==

Since I just did the "generate the permutations" task, I'm going to use it to do the brute force solution.

"DABC","BCAD","CADB","CDBA","CBAD","ABDC","ADBC","BDCA",

"DCBA","BACD","BADC","BDAC","CBDA","DBCA","DCAB");

Copy creates a read/write list from a read only list.

xplode() pushes all elements of data as parameters to remove.

 

=={{header|ZX Spectrum Basic}}==

20 LET length=LEN l$

30 FOR a= CODE "A" TO CODE "D"

120 NEXT i

130 PRINT x$;" is missing"