In the current work, we present two generalizations of the Parallel Tempering algorithm, inspired by the so-called continuous-time Infinite Swapping algorithm, which found its origins in the molecular dynamics community, and can be understood as the continuous-time limit of a Parallel Tempering algorithm with state-dependent swapping rates. In the current work, we extend this idea to the context of time-discrete Markov chains and present two Markov chain Monte Carlo algorithms that follow the same paradigm as the continuous-time infinite swapping procedure. We present results on the reversibility and ergodicity properties of our generalized PT algorithms. Numerical results on sampling from different target distributions originating from Bayesian inverse problems, show that the proposed methods significantly improve sampling efficiency over more traditional sampling algorithms such as Random Walk Metropolis and (standard) Parallel Tempering.