First of all I would like to thank everyone who shared their solutions for out-shuffle problem with the rest of us and submitted any comments related to this problem. Looking back in time it was actually three years ago when we tried to find an efficient answer to this particular programming challenge. After we were puzzled and didn’t make any progress for some time I contacted the most knowledgeable person in my circle of acquaintances when it comes to algorithms and data structures. His name is Ahto Truu and he is GodOfAlgorithmsAndDataStructures ;-)
Ahto writes regular column about programming puzzles for one of the Estonian IT magazines and as a natural result he composed an article about this particular problem. The original article in Estonian is published here. On Monday Ahto sent me an updated English translation of this article. The PDF file can be downloaded from here. Here’s the table of contents:
- The Problem
- The Setup
- A Memory-Hungry Solution
- A Time-Hungry Solution
- A Divide’n’Conquer Solution
- A Combinatorial Solution
- Acknowledgments
As also pointed out in Ahto’s article, this paper by Ellis, Krahn, and Fan describes an algorithm that solves out-shuffle problem in O(N) time and O(log N) space.
Read full article from Gunnar Kudrjavets - The out-shuffle problem: solutions and acknowledgments
No comments:
Post a Comment