Permutation-based partial-correlation tests guarantee finite-sample Type I error control under any fixed design and exchangeable noise, yet their power can collapse when the permutation-augmented design aligns too closely with the covariate of interest. We remedy this by fixing a design-driven subset of rows and permuting only the remainder. The fixed rows are chosen by a greedy algorithm that maximizes a lower bound on power. This strategy reduces covariate-permutation collinearity while preserving worst-case Type I error control. Simulations confirm that this refinement maintains nominal size and delivers substantial power gains over original unrestricted permutations, especially in high-collinearity regimes.