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

Listed above are   all-but-one   of the permutations of the symbols   A,   B,   C,   and   D,   except   for one permutation that's   not   listed.



Task

Find that missing permutation.



Methods

 Obvious method: 
        enumerate all permutations of   A,  B,  C,  and  D,  
        and then look for the missing permutation. 

 alternate method:
        Hint:  if all permutations were shown above,  how many 
        times would  A  appear in each position?     
        What is the  parity  of this number?

 another alternate method:
        Hint:  if you add up the letter values of each column, 
        does a missing letter   A,  B,  C,  and  D   from each
        column cause the total value for each column to be unique?



Related task

   Permutations)


// version 1.1.2
 
fun <T> permute(input: List<T>): List<List<T>> {
    if (input.size == 1) return listOf(input)
    val perms = mutableListOf<List<T>>()
    val toInsert = input[0]
    for (perm in permute(input.drop(1))) {
        for (i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, toInsert)
            perms.add(newPerm)
        }
    }
    return perms
}
 
fun <T> missingPerms(input: List<T>, perms: List<List<T>>) = permute(input) - perms
 
fun main(args: Array<String>) {
    val input = listOf('A', 'B', 'C', 'D')
    val strings = listOf(
        "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB",
        "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA",
        "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DBCA", "DCAB"
    )
    val perms = strings.map { it.toList() }
    val missing = missingPerms(input, perms)
    if (missing.size == 1)
        print("The missing permutation is ${missing[0].joinToString("")}")
    else {
        println("There are ${missing.size} missing permutations, namely:\n")
        for (perm in missing) println(perm.joinToString(""))
    }
}