We study Ni80Fe20-based permalloys with the relativistic spin-polarized Korringa-Kohn-Rostoker electronic structure method. Treating the compositional disorder with the coherent potential approximation, we investigate how the magnetocrystalline anisotropy, K, and magnetostriction, lambda, of Ni-rich Ni-Fe alloys vary with the addition of small amounts of non-magnetic transition metals, Cu and Mo. From our calculations we follow the trends in K and lambda and find the compositions of Ni-Fe-Cu and Ni-Fe-Mo where both are near zero. These high permeability compositions of Ni-Fe-Cu and Ni-Fe-Mo match well with those discovered experimentally. We monitor the connection of the magnetic anisotropy with the number of minority spin electrons, Nmin. By raising Nmin via artificially increasing the band-filling of Ni80Fe20, we are able to reproduce the key features that underpin the magnetic softening we find in the ternary alloys. The effect of band-filling on the dependence of magnetocrystalline anisotropy on atomic short-range order in Ni80Fe20 is also studied. Our calculations, based on a static concentration wave theory, indicate that the susceptibility of the high permeability of the Ni-Fe-Cu and Ni-Fe-Mo alloys to their annealing conditions is also strongly dependent on the alloys compositions. An ideal soft magnet appears from these calculations.