Extracting statistical insights from extensive distributed datasets is a significant challenge. Local Differential Privacy (LDP) provides a means to estimate the frequencies of confidential data while preserving privacy. LDP allows each individual to modify their data on their own device to maintain privacy, albeit introducing some error into frequency estimations. Practically, under LDP, frequency estimation varies with the data’s scope and the desired precision. The challenge is to minimize variance while maximizing accuracy in frequency estimations without reducing privacy levels. LDP-compliant frequency estimation consists of encoding, perturbation, and aggregation. This study concentrates on enhancing the perturbation phase. We introduce the Simmons mechanism without replacement (SWOR) and the Kuk mechanism without replacement (KWOR). Both theoretical analyses and simulations on a synthetic Zipf distribution dataset comparing with a classical baseline suggest that the Simmons mechanism without replacement decreases variance by about an order of magnitude, while the Kuk mechanism without replacement reduces variance by about two orders. Examples of two real datasets support our methodology. Lastly, we explore real-world deployments example of the Kuk mechanism without replacement. Our source code, data, and supplementary materials are available at https://github.com/ssjhf/encoding_and_perturbing