Find the missing permutation: Difference between revisions
Content added Content deleted
(moved PHP below perl, addded Phix) |
m (→{{header|Phix}}: added a bit more explanation) |
||
Line 1,490: | Line 1,490: | ||
r = sq_sub(max(r)+'A',r) |
r = sq_sub(max(r)+'A',r) |
||
puts(1,r&'\n') |
puts(1,r&'\n') |
||
-- based on the notion that missing = sum(full)-sum(partial) would be true, |
|||
-- and that sum(full) would be like {M,M,M,M} rather than a mix of numbers. |
|||
-- the final step is equivalent to eg {1528,1530,1531,1529} |
-- the final step is equivalent to eg {1528,1530,1531,1529} |
||
-- max-r[i] -> { 3, 1, 0, 2} |
-- max-r[i] -> { 3, 1, 0, 2} |
||
-- to chars -> { D, B, A, C} |
-- to chars -> { D, B, A, C} |
||
-- (but obviously |
-- (but obviously both done in one line) |
||
-- 2: the xor trick |
-- 2: the xor trick |
||
Line 1,501: | Line 1,503: | ||
end for |
end for |
||
puts(1,r&'\n') |
puts(1,r&'\n') |
||
-- (relies on the missing chars being present an odd number of times, non-missing chars an even number of times) |
|||
-- 3: find least frequent letters |
-- 3: find least frequent letters |
||
Line 1,512: | Line 1,515: | ||
end for |
end for |
||
puts(1,r&'\n') |
puts(1,r&'\n') |
||
-- (relies on the assumption that a full set would have each letter occurring the same number of times in each position) |
|||
-- 4: test all permutations |
-- 4: test all permutations |
||
Line 1,518: | Line 1,522: | ||
if not find(r,perms) then exit end if |
if not find(r,perms) then exit end if |
||
end for |
end for |
||
puts(1,r&'\n') |
puts(1,r&'\n') |
||
-- (relies on brute force(!) - but this is the only method that could be made to cope with >1 omission)</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |