This paper addresses the problem of the nD-hypercube interconnection networks rearrangeability that is the capability of such networks to route optimally arbitrary permutations under queueless communication constraints. To that purpose, the paper exploits the recursive structure of nD-hypercube as two (n-1)D-hypercubes and proposes the k-partitioning paradigm. For n = 4, the paper characterizes permutations that do not admit 1-partitioning. It then exhibits representatives of some of the subclasses of such permutations. Each representative is then proved to admit 2-partitioning and one of its corresponding routing strategies is exhibited. Such routing strategy is obtained as a concatenation of a routing strategy of one of the upstream permutations of the considered permutation and a routing strategy of each of the two downstream permutations induced by the considered upstream permutation.