找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
public static void main(String[] args) throws IOException {
hello h = new hello();
h.printcomp();
}
int fact=1;
public void factrec(int a,int k){
if(a>=k)
{fact=fact*k;
k++;
factrec(a,k);
}
else
{System.out.println("The string will have "+fact+" permutations");
}
}
public void printcomp(){
String str;
int k;
Scanner in = new Scanner(System.in);
System.out.println("enter the string whose permutations has to b found");
str=in.next();
k=str.length();
factrec(k,1);
String[] arr =new String[fact];
char[] array = str.toCharArray();
while(p<fact)
printcomprec(k,array,arr);
// if incase u need array containing all the permutation use this
//for(int d=0;d<fact;d++)
//System.out.println(arr[d]);
}
int y=1;
int p = 0;
int g=1;
int z = 0;
public void printcomprec(int k,char array[],String arr[]){
for (int l = 0; l < k; l++) {
for (int b=0;b<k-1;b++){
for (int i=1; i<k-g; i++) {
char temp;
String stri = "";
temp = array[i];
array[i] = array[i + g];
array[i + g] = temp;
for (int j = 0; j < k; j++)
stri += array[j];
arr[z] = stri;
System.out.println(arr[z] + " " + p++);
z++;
}
}
char temp;
temp=array[0];
array[0]=array[y];
array[y]=temp;
if (y >= k-1)
y=y-(k-1);
else
y++;
}
if (g >= k-1)
g=1;
else
g++;
}
}
其他回答
这可以通过简单地在前面部分结果的所有位置依次插入字符串的每个字母来迭代完成。
我们以[A]开头,与B连成[BA, AB],与C连成[CBA, BCA, BAC, CAB等]。
运行时间将是O(n!),对于测试用例ABCD,它是1 x 2 x 3 x 4。
在上面的乘积中,1是A, 2是B,以此类推。
飞镖示例:
void main() {
String insertAt(String a, String b, int index)
{
return a.substring(0, index) + b + a.substring(index);
}
List<String> Permute(String word) {
var letters = word.split('');
var p_list = [ letters.first ];
for (var c in letters.sublist(1)) {
var new_list = [ ];
for (var p in p_list)
for (int i = 0; i <= p.length; i++)
new_list.add(insertAt(p, c, i));
p_list = new_list;
}
return p_list;
}
print(Permute("ABCD"));
}
下面是一个简单的Java递归解决方案:
public static ArrayList<String> permutations(String s) {
ArrayList<String> out = new ArrayList<String>();
if (s.length() == 1) {
out.add(s);
return out;
}
char first = s.charAt(0);
String rest = s.substring(1);
for (String permutation : permutations(rest)) {
out.addAll(insertAtAllPositions(first, permutation));
}
return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
ArrayList<String> out = new ArrayList<String>();
for (int i = 0; i <= s.length(); ++i) {
String inserted = s.substring(0, i) + ch + s.substring(i);
out.add(inserted);
}
return out;
}
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实现打印给定字符串的所有排列,考虑重复字符,只打印唯一字符,如下所示:
import java.util.Set;
import java.util.HashSet;
public class PrintAllPermutations2
{
public static void main(String[] args)
{
String str = "AAC";
PrintAllPermutations2 permutation = new PrintAllPermutations2();
Set<String> uniqueStrings = new HashSet<>();
permutation.permute("", str, uniqueStrings);
}
void permute(String prefixString, String s, Set<String> set)
{
int n = s.length();
if(n == 0)
{
if(!set.contains(prefixString))
{
System.out.println(prefixString);
set.add(prefixString);
}
}
else
{
for(int i=0; i<n; i++)
{
permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
}
}
}
}
串的排列:
public static void main(String args[]) {
permu(0,"ABCD");
}
static void permu(int fixed,String s) {
char[] chr=s.toCharArray();
if(fixed==s.length())
System.out.println(s);
for(int i=fixed;i<s.length();i++) {
char c=chr[i];
chr[i]=chr[fixed];
chr[fixed]=c;
permu(fixed+1,new String(chr));
}
}
推荐文章
- 在流中使用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