Anonymous user
Find the missing permutation: Difference between revisions
→{{header|Julia}}: A new entry for Julia
(→{{header|jq}}: simplify) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 840:
<lang sh>$ jq -R . Find_the_missing_permutation.txt | jq -s -f Find_the_missing_permutation.jq
"DBAC"</lang>
=={{header|Julia}}==
<tt>find_missing_permutations</tt> accepts a list of strings and finds any permutations of the first string in the list that are missing from the list. If the list contains any strings that are not such permutations (including the first item), the function throws a <tt>DomainError</tt>. Duplicated permutations are silently ignored.
I chose to solve this task by permutation enumeration because Julia provides good native functions for creating and processing list permutations. Also, this function detects multiple missing permutations and tolerates duplicated items in the input list. The function will fail if the length of the strings exceeds 20. This failure occurs because the number of possible permutations then exceeds <tt>typemax(Int64)</tt>. But good luck with this sort of task when the strings approach such lengths.
'''Function'''
<lang Julia>
function find_missing_permutations{T<:String}(a::Array{T,1})
std = unique(sort(split(a[1], "")))
needsperm = trues(factorial(length(std)))
for s in a
b = split(s, "")
p = map(x->findfirst(std, x), b)
isperm(p) || throw(DomainError())
needsperm[nthperm(p)] = false
end
mperms = T[]
for i in findn(needsperm)[1]
push!(mperms, join(nthperm(std, i), ""))
end
return mperms
end
</lang>
'''Main'''
<lang Julia>
test = ["ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD",
"ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA",
"CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD",
"BADC", "BDAC", "CBDA", "DBCA", "DCAB"]
missperms = find_missing_permutations(test)
print("The test list is:\n ")
i = 0
for s in test
print(s, " ")
i += 1
i %= 5
i != 0 || print("\n ")
end
i == 0 || println()
if length(missperms) > 0
println("The following permutations are missing:")
for s in missperms
println(" ", s)
end
else
println("There are no missing permutations.")
end
</lang>
{{out}}
<pre>
The test list is:
ABCD CABD ACDB DACB BCDA
ACBD ADCB CDAB DABC BCAD
CADB CDBA CBAD ABDC ADBC
BDCA DCBA BACD BADC BDAC
CBDA DBCA DCAB
The following permutations are missing:
DBAC
</pre>
=={{header|K}}==
| |||