Ulam’s metric defines the minimal number of moves (extraction followed by re-insertion of permutation elements) to go between a given pair of permutations, and determination of moved elements resolves the Longest Common Subsequence problem. The extensive research that followed Ulam’s work provided many influential discoveries in computer science, mathematics, statistics and physics. In this paper, motivated by successful industrial applications of k-tuples of permutations, we extend Ulam’s original definition to provide a framework of multidimensional metric and study its complexity and approximability.