在 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
。現在,迴圈通過在不同位置新增 B
和 C
來重複。因此,我們將 BC
和 CB
作為 Set
詞中的兩個元素。
在這一點上,我們退出迴圈並獲得 initial
值作為 A
。我們進一步重複這個過程,並在我們之前的排列中的可能位置插入初始字元 A
。首先,對於 BC
,我們得到 ABC
BAC
和 BCA
。類似地,對於第二個排列 CB
,我們做同樣的事情:在可能的位置插入第一個字母並得到 ACB
、CAB
和 CBA
。
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]
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