The structural complexity of metamaterials is limitless, but, in practice, most designs comprise periodic architectures that lead to materials with spatially homogeneous features(1-11). More advanced applications in soft robotics, prosthetics and wearable technology involve spatially textured mechanical functionality, which requires aperiodic architectures. However, a naive implementation of such structural complexity invariably leads to geometrical frustration (whereby local constraints cannot be satisfied everywhere), which prevents coherent operation and impedes functionality. Here we introduce a combinatorial strategy for the design of aperiodic, yet frustration-free, mechanical metamaterials that exhibit spatially textured functionalities. We implement this strategy using cubic building blocks-voxels-that deform anisotropically, a local stacking rule that allows cooperative shape changes by guaranteeing that deformed building blocks fit together as in a three-dimensional jigsaw puzzle, and three-dimensional printing. These aperiodic metamaterials exhibit long-range holographic order, whereby the two-dimensional pixelated surface texture dictates the three-dimensional interior voxel arrangement. They also act as programmable shape-shifters, morphing into spatially complex, but predictable and designable, shapes when uniaxially compressed. Finally, their mechanical response to compression by a textured surface reveals their ability to perform sensing and pattern analysis. Combinatorial design thus opens up a new avenue towards mechanical metamaterials with unusual order and machine-like functionalities.