在 Java 中查詢給定字串的所有排列

Rupam Yadav 2021年7月1日
在 Java 中查詢給定字串的所有排列

排列是一種數學技術,用於在排列順序很重要時確定集合中可能排列的數量。

使用遞迴的字串排列

函式 permutationFinder(String str) 是遞迴的,它列印傳遞的字串的每個排列。Set 變數用於儲存 Java 字串的排列,以便自動刪除重複項。我們砍掉我們的單詞,在我們的字串中一次取一個字母,並分別處理剩餘的字母。

insertChar 函式插入第一個字元以獲取我們傳遞的字串的完整排列列表。

我們從字串 ABC 開始,我們遍歷它,一次一個字母。我們將初始字元 A 分開,其餘字元是 BC。現在我們遍歷 rem 並找到剩餘字母的排列。下面進一步解釋該過程。

permutationFinder() 函式被觸發,直到我們沒有任何東西可以砍;這就是為什麼我們得到 rem = ""。在這一點上,我們將 "" 新增到 perms 並返回它,它被進一步儲存到 Set 變數 words 中。另外,請記住此時我們的初始字元是 C

我們迴圈遍歷 Set 單詞中的每個字串。我們有 strNew 作為""空字串,在這種情況下它進入第二個 for 迴圈,我們有 i=0,它等於 strNew.length();因此,我們使用該點的引數呼叫 insertChar("",C,0) 方法。此呼叫返回 C,將其新增到 perm

我們打破迴圈並檢查我們是否有未完成的工作。因此,在這一點上,我們的 initial 值為 B,而 words 有一個元素,即 C。現在,迴圈通過在不同位置新增 BC 來重複。因此,我們將 BCCB 作為 Set 詞中的兩個元素。

在這一點上,我們退出迴圈並獲得 initial 值作為 A。我們進一步重複這個過程,並在我們之前的排列中的可能位置插入初始字元 A。首先,對於 BC,我們得到 ABC BACBCA。類似地,對於第二個排列 CB,我們做同樣的事情:在可能的位置插入第一個字母並得到 ACBCABCBA

import java.util.HashSet;
import java.util.Set;

public class PermutationFinder {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); 
        String rem = str.substring(1);
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(insertChar(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String insertChar(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }
    public static void main(String args[]){
        String s1 = "ABC";
        System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
    }

}

這些是字串 ABC 的所有可能排列。

輸出:

Permutations for ABC are: 
[ACB, BCA, ABC, CBA, BAC, CAB]
Author: Rupam Yadav
Rupam Yadav avatar Rupam Yadav avatar

Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.

LinkedIn

相關文章 - Java String