找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
简单的解决方案,利用swift语言的特点,数组是值类型。
func permutation(chrs: [String], arr: [String], result: inout [[String]]) {
if arr.count == chrs.count {
result.append(arr)
return
}
for chr in chrs {
var arr = arr
if !arr.contains(chr) {
arr.append(chr)
permutation(chrs: chrs, arr: arr, result: &result)
}
}
}
func test() {
var result = [[String]]()
let chrs = ["a", "b", "c", "d"]
permutation(chrs: chrs, arr: [], result: &result)
}
复杂度O(n * n!)
其他回答
//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合
public class Permutation {
//Act as a queue
private List<Character> list;
//To remove the duplicates
private Set<String> set = new HashSet<String>();
public Permutation(String s) {
list = new LinkedList<Character>();
int len = s.length();
for(int i = 0; i < len; i++) {
list.add(s.charAt(i));
}
}
public List<String> getStack(Character c, List<Character> list) {
LinkedList<String> stack = new LinkedList<String>();
stack.add(""+c);
for(Character ch: list) {
stack.add(""+ch);
}
return stack;
}
public String printCombination(String s1, String s2) {
//S1 will be a single character
StringBuilder sb = new StringBuilder();
String[] strArr = s2.split(",");
for(String s: strArr) {
sb.append(s).append(s1);
sb.append(",");
}
for(String s: strArr) {
sb.append(s1).append(s);
sb.append(",");
}
return sb.toString();
}
public void printPerumtation() {
int cnt = list.size();
for(int i = 0; i < cnt; i++) {
Character c = list.get(0);
list.remove(0);
List<String> stack = getStack(c, list);
while(stack.size() > 1) {
//Remove the top two elements
String s2 = stack.remove(stack.size() - 1);
String s1 = stack.remove(stack.size() - 1);
String comS = printCombination(s1, s2);
stack.add(comS);
}
String[] perms = (stack.remove(0)).split(",");
for(String perm: perms) {
set.add(perm);
}
list.add(c);
}
for(String s: set) {
System.out.println(s);
}
}
}
/*
* eg: abc =>{a,bc},{b,ac},{c,ab}
* =>{ca,b},{cb,a}
* =>cba,cab
* =>{ba,c},{bc,a}
* =>bca,bac
* =>{ab,c},{ac,b}
* =>acb,abc
*/
public void nonRecpermute(String prefix, String word)
{
String[] currentstr ={prefix,word};
Stack<String[]> stack = new Stack<String[]>();
stack.add(currentstr);
while(!stack.isEmpty())
{
currentstr = stack.pop();
String currentPrefix = currentstr[0];
String currentWord = currentstr[1];
if(currentWord.equals(""))
{
System.out.println("Word ="+currentPrefix);
}
for(int i=0;i<currentWord.length();i++)
{
String[] newstr = new String[2];
newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
newstr[1] = currentWord.substring(0, i);
if(i<currentWord.length()-1)
{
newstr[1] = newstr[1]+currentWord.substring(i+1);
}
stack.push(newstr);
}
}
}
递归Python解决方案
def permute(input_str):
_permute("", input_str)
def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)
else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])
if __name__ == '__main__':
permute('foobar')
这就是我通过对排列和递归函数调用的基本理解所做的。虽然要花点时间,但都是独立完成的。
public class LexicographicPermutations {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="abc";
List<String>combinations=new ArrayList<String>();
combinations=permutations(s);
Collections.sort(combinations);
System.out.println(combinations);
}
private static List<String> permutations(String s) {
// TODO Auto-generated method stub
List<String>combinations=new ArrayList<String>();
if(s.length()==1){
combinations.add(s);
}
else{
for(int i=0;i<s.length();i++){
List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
for (String string : temp) {
combinations.add(s.charAt(i)+string);
}
}
}
return combinations;
}}
生成输出为[abc, acb, bac, bca, cab, cba]。
它背后的基本逻辑是
对于每个字符,将其视为第一个字符,并找出剩余字符的组合。例[abc](abc的组合)->。
a->[bc](a x Combination of (bc))->{abc,acb} b->[ac](b x组合(ac))->{bac,bca} c->[ab](c x Combination of (ab))->{cab,cba}
然后递归地分别调用每个[bc],[ac]和[ab]。
使用递归的简单python解决方案。
def get_permutations(string):
# base case
if len(string) <= 1:
return set([string])
all_chars_except_last = string[:-1]
last_char = string[-1]
# recursive call: get all possible permutations for all chars except last
permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)
# put the last char in all possible positions for each of the above permutations
permutations = set()
for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
for position in range(len(all_chars_except_last) + 1):
permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
permutations.add(permutation)
return permutations
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap