找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
这是一个更快的解决方案,因为它不受字符串连接计算复杂度O(n^2)的影响。另一方面它是无循环的,完全递归的
public static void main(String[] args) {
permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}
private static void permutation(String str) {
char[] stringArray = str.toCharArray();
printPermutation(stringArray, 0, stringArray.length, 0, 1);
}
private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) {
// Stop condition
if (loopCounter == length)
return;
/*
When reaching the end of the array:
1- Reset loop indices.
2- Increase length counter.
*/
if (indexTo == length) {
indexFrom = 0;
indexTo = 1;
++loopCounter;
}
// Print.
System.out.println(string);
// Swap from / to indices.
char temp = string[indexFrom];
string[indexFrom] = string[indexTo];
string[indexTo] = temp;
// Go for next iteration.
printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo);
}
其他回答
使用Es6的字符串排列
使用reduce()方法
Const排列= STR => { If (str.length <= 2) 返回str.length === 2 ?[str, str[1] + str[0]]: [str]; 返回str .split (") .reduce ( (acc, letter, index) => acc.concat(排列(str。Slice (0, index) + str.slice(index + 1))。Map (val =>字母+ val)), [] ); }; console.log(排列(STR));
python实现
def getPermutation(s, prefix=''):
if len(s) == 0:
print prefix
for i in range(len(s)):
getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )
getPermutation('abcd','')
我定义了左右两个字符串。一开始,左边是输入字符串,右边是“”。我递归地从左边选择所有可能的字符,并将其添加到右边的末尾。然后,在left-charAt(I)和right+charAt(I)上调用递归函数。我定义了一个类来跟踪生成的排列。
import java.util.HashSet;
import java.util.Set;
public class FindPermutations {
static class Permutations {
Set<String> permutations = new HashSet<>();
}
/**
* Building all the permutations by adding chars of left to right one by one.
*
* @param left The left string
* @param right The right string
* @param permutations The permutations
*/
private void findPermutations(String left, String right, Permutations permutations) {
int n = left.length();
if (n == 0) {
permutations.permutations.add(right);
}
for (int i = 0; i < n; i++) {
findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations);
}
}
/**
* Gets all the permutations of a string s.
*
* @param s The input string
* @return all the permutations of a string s
*/
public Permutations getPermutations(String s) {
Permutations permutations = new Permutations();
findPermutations(s, "", permutations);
return permutations;
}
public static void main(String[] args) {
FindPermutations findPermutations = new FindPermutations();
String s = "ABC";
Permutations permutations = findPermutations.getPermutations(s);
printPermutations(permutations);
}
private static void printPermutations(Permutations permutations) {
for (String p : permutations.permutations) {
System.out.println(p);
}
}
}
我希望这能有所帮助。
简单的递归c++实现如下所示:
#include <iostream>
void generatePermutations(std::string &sequence, int index){
if(index == sequence.size()){
std::cout << sequence << "\n";
} else{
generatePermutations(sequence, index + 1);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1);
std::swap(sequence[index], sequence[i]);
}
}
}
int main(int argc, char const *argv[])
{
std::string str = "abc";
generatePermutations(str, 0);
return 0;
}
输出:
abc
acb
bac
bca
cba
cab
更新
如果想要存储结果,可以将vector作为函数调用的第三个参数传递。此外,如果您只想要唯一的排列,您可以使用集合。
#include <iostream>
#include <vector>
#include <set>
void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){
if(index == sequence.size()){
//std::cout << sequence << "\n";
v.push_back(sequence);
} else{
generatePermutations(sequence, index + 1, v);
for(int i = index + 1 ; i < sequence.size() ; ++i){
std::swap(sequence[index], sequence[i]);
generatePermutations(sequence, index + 1, v);
std::swap(sequence[index], sequence[i]);
}
}
}
int main(int argc, char const *argv[])
{
std::string str = "112";
std::vector <std::string> permutations;
generatePermutations(str, 0, permutations);
std::cout << "Number of permutations " << permutations.size() << "\n";
for(const std::string &s : permutations){
std::cout << s << "\n";
}
std::set <std::string> uniquePermutations(permutations.begin(), permutations.end());
std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n";
for(const std::string &s : uniquePermutations){
std::cout << s << "\n";
}
return 0;
}
输出:
Number of permutations 6
112
121
112
121
211
211
Number of unique permutations 3
112
121
211
让我们以输入abc为例。
从集合(["c"])中的最后一个元素(c)开始,然后将最后第二个元素(b)添加到它的前面,末尾和中间的每个可能位置,使其["bc", "cb"],然后以同样的方式将后面的下一个元素(a)添加到集合中的每个字符串中,使其:
"a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"]
因此整个排列:
["abc", "bac", "bca","acb" ,"cab", "cba"]
代码:
public class Test
{
static Set<String> permutations;
static Set<String> result = new HashSet<String>();
public static Set<String> permutation(String string) {
permutations = new HashSet<String>();
int n = string.length();
for (int i = n - 1; i >= 0; i--)
{
shuffle(string.charAt(i));
}
return permutations;
}
private static void shuffle(char c) {
if (permutations.size() == 0) {
permutations.add(String.valueOf(c));
} else {
Iterator<String> it = permutations.iterator();
for (int i = 0; i < permutations.size(); i++) {
String temp1;
for (; it.hasNext();) {
temp1 = it.next();
for (int k = 0; k < temp1.length() + 1; k += 1) {
StringBuilder sb = new StringBuilder(temp1);
sb.insert(k, c);
result.add(sb.toString());
}
}
}
permutations = result;
//'result' has to be refreshed so that in next run it doesn't contain stale values.
result = new HashSet<String>();
}
}
public static void main(String[] args) {
Set<String> result = permutation("abc");
System.out.println("\nThere are total of " + result.size() + " permutations:");
Iterator<String> it = result.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
推荐文章
- 在流中使用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