Previous transmission techniques for fading channels that exploit signal space diversity (SSD) are based on rotation or precoding of an original signal constellation. In this work, we follow a completely different approach to design full diversity multidimensional codebooks whose implementation has low complexity and requires little storage. The design consists of finding good permutations of the labels of points in a fixed grid. We consider both the uniform and the Gaussian-shaped grids. An ensemble average performance based on an enumerative analysis of the error events is presented, which brings some insight into the problem. Three low-complexity algorithms are then proposed to find good permutations sets. Both analytical and simulation results confirm the good performance of the proposed codebooks, which can be considered as good candidates for practical communications systems.