There is a question in Art of Computer Programming by Knuth which needs us to prove that input-restricted deques and output-restricted deques can form the same number of (and possibly individually same) permutations. The solution is

By operating backwards, we can get the reverse of the inverse of the reverse of any input-restricted permutation with an output-restricted deque, and conversely. This rule sets up a one-to-one correspondence between the two sets of permutations.

Which doesn't seem very clear. Can someone explain the answer in English?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.