找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
简单的递归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
其他回答
这是另一个更简单的方法来做一个字符串的排列。
public class Solution4 {
public static void main(String[] args) {
String a = "Protijayi";
per(a, 0);
}
static void per(String a , int start ) {
//bse case;
if(a.length() == start) {System.out.println(a);}
char[] ca = a.toCharArray();
//swap
for (int i = start; i < ca.length; i++) {
char t = ca[i];
ca[i] = ca[start];
ca[start] = t;
per(new String(ca),start+1);
}
}//per
}
Java中一个非常基本的解决方案是使用递归+设置(以避免重复),如果你想存储和返回解决方案字符串:
public static Set<String> generatePerm(String input)
{
Set<String> set = new HashSet<String>();
if (input == "")
return set;
Character a = input.charAt(0);
if (input.length() > 1)
{
input = input.substring(1);
Set<String> permSet = generatePerm(input);
for (String x : permSet)
{
for (int i = 0; i <= x.length(); i++)
{
set.add(x.substring(0, i) + a + x.substring(i));
}
}
}
else
{
set.add(a + "");
}
return set;
}
让我们以输入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());
}
}
}
这里有一个优雅的,非递归的O(n!)解:
public static StringBuilder[] permutations(String s) {
if (s.length() == 0)
return null;
int length = fact(s.length());
StringBuilder[] sb = new StringBuilder[length];
for (int i = 0; i < length; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int times = length / (i + 1);
for (int j = 0; j < times; j++) {
for (int k = 0; k < length / times; k++) {
sb[j * length / times + k].insert(k, ch);
}
}
}
return sb;
}
这是一个具有O(n!)时间复杂度的算法,具有纯递归和直观。
public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
words obj = new words();
String str="premandl";
obj.getcombination(str, str.length()-1, "");
System.out.println(arrlist);
}
public void getcombination(String str, int charIndex, String output) {
if (str.length() == 0) {
arrlist.add(output);
return ;
}
if (charIndex == -1) {
return ;
}
String character = str.toCharArray()[charIndex] + "";
getcombination(str, --charIndex, output);
String remaining = "";
output = output + character;
remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);
getcombination(remaining, remaining.length() - 1, output);
}
}
推荐文章
- 在流中使用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