找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
基于Mark Byers的回答,我想出了这个解决方案:
JAVA
public class Main {
public static void main(String[] args) {
myPerm("ABCD", 0);
}
private static void myPerm(String str, int index)
{
if (index == str.length()) System.out.println(str);
for (int i = index; i < str.length(); i++)
{
char prefix = str.charAt(i);
String suffix = str.substring(0,i) + str.substring(i+1);
myPerm(prefix + suffix, index + 1);
}
}
}
C#
我还使用新的c# 8.0范围操作符在c#中编写了该函数
class Program
{
static void Main(string[] args)
{
myPerm("ABCD", 0);
}
private static void myPerm(string str, int index)
{
if (index == str.Length) Console.WriteLine(str);
for (int i = index; i < str.Length; i++)
{
char prefix = str[i];
string suffix = str[0..i] + str[(i + 1)..];
myPerm(prefix + suffix, index + 1);
}
}
我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:
/*
myPerm("ABCD",0)
prefix = "A"
suffix = "BCD"
myPerm("ABCD",1)
prefix = "B"
suffix = "ACD"
myPerm("BACD",2)
prefix = "C"
suffix = "BAD"
myPerm("CBAD",3)
prefix = "D"
suffix = "CBA"
myPerm("DCBA",4)
Console.WriteLine("DCBA")
*/
其他回答
我们可以用阶乘来计算有多少字符串以某个字母开头。
示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。
static public int facts(int x){
int sum = 1;
for (int i = 1; i < x; i++) {
sum *= (i+1);
}
return sum;
}
public static void permutation(String str) {
char[] str2 = str.toCharArray();
int n = str2.length;
int permutation = 0;
if (n == 1) {
System.out.println(str2[0]);
} else if (n == 2) {
System.out.println(str2[0] + "" + str2[1]);
System.out.println(str2[1] + "" + str2[0]);
} else {
for (int i = 0; i < n; i++) {
if (true) {
char[] str3 = str.toCharArray();
char temp = str3[i];
str3[i] = str3[0];
str3[0] = temp;
str2 = str3;
}
for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
if (j != n-1) {
char temp1 = str2[j+1];
str2[j+1] = str2[j];
str2[j] = temp1;
} else {
char temp1 = str2[n-1];
str2[n-1] = str2[1];
str2[1] = temp1;
j = 1;
} // end of else block
permutation++;
System.out.print("permutation " + permutation + " is -> ");
for (int k = 0; k < n; k++) {
System.out.print(str2[k]);
} // end of loop k
System.out.println();
} // end of loop j
} // end of loop i
}
}
在这里和其他论坛给出的所有解决方案中,我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案,因为我是新手。 无论如何,这是我对他的描述的实现
public class PermTest {
public static void main(String[] args) throws Exception {
String str = "abcdef";
StringBuffer strBuf = new StringBuffer(str);
doPerm(strBuf,0);
}
private static void doPerm(StringBuffer str, int index){
if(index == str.length())
System.out.println(str);
else { //recursively solve this by placing all other chars at current first pos
doPerm(str, index+1);
for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
swap(str,index, i);
doPerm(str, index+1);
swap(str,i, index);//restore back my string buffer
}
}
}
private static void swap(StringBuffer str, int pos1, int pos2){
char t1 = str.charAt(pos1);
str.setCharAt(pos1, str.charAt(pos2));
str.setCharAt(pos2, t1);
}
}
我更喜欢这个解决方案,而不是第一个解决方案,因为这个解决方案使用StringBuffer。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建,其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说,由于额外的“交换”,它已经滞后了)
简单的递归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
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','')
另一种简单的方法是遍历字符串,选择尚未使用的字符并将其放入缓冲区,继续循环,直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案,因为:
容易理解 容易避免重复 输出是排序的
下面是java代码:
List<String> permute(String str) {
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
Arrays.sort(chars);
helper(chars, used, sb, res);
return res;
}
void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}
// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);
helper(chars, used, sb, res);
// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
str输入:1231
输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}
注意,输出是排序的,没有重复的结果。
推荐文章
- 在流中使用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