找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
下面是一个java实现:
/* All Permutations of a String */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Complexity O(n*n!) */
class Ideone
{
public static ArrayList<String> strPerm(String str, ArrayList<String> list)
{
int len = str.length();
if(len==1){
list.add(str);
return list;
}
list = strPerm(str.substring(0,len-1),list);
int ls = list.size();
char ap = str.charAt(len-1);
for(int i=0;i<ls;i++){
String temp = list.get(i);
int tl = temp.length();
for(int j=0;j<=tl;j++){
list.add(temp.substring(0,j)+ap+temp.substring(j,tl));
}
}
while(true){
String temp = list.get(0);
if(temp.length()<len)
list.remove(temp);
else
break;
}
return list;
}
public static void main (String[] args) throws java.lang.Exception
{
String str = "abc";
ArrayList<String> list = new ArrayList<>();
list = strPerm(str,list);
System.out.println("Total Permutations : "+list.size());
for(int i=0;i<list.size();i++)
System.out.println(list.get(i));
}
}
http://ideone.com/nWPb3k
其他回答
使用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));
基于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")
*/
import java.io.*;
public class Anagram {
public static void main(String[] args) {
java.util.Scanner sc=new java.util.Scanner(System.in);
PrintWriter p=new PrintWriter(System.out,true);
p.println("Enter Word");
String a[],s="",st;boolean flag=true;
int in[],n,nf=1,i,j=0,k,m=0;
char l[];
st=sc.next();
p.println("Anagrams");
p.println("1 . "+st);
l=st.toCharArray();
n=st.length();
for(i=1;i<=n;i++){
nf*=i;
}
i=1;
a=new String[nf];
in=new int[n];
a[0]=st;
while(i<nf){
for(m=0;m<n;m++){
in[m]=n;
}j=0;
while(j<n){
k=(int)(n*Math.random());
for(m=0;m<=j;m++){
if(k==in[m]){
flag=false;
break;
}
}
if(flag==true){
in[j++]=k;
}flag=true;
}s="";
for(j=0;j<n;j++){
s+=l[in[j]];
}
//Removing same words
for(m=0;m<=i;m++){
if(s.equalsIgnoreCase(a[m])){
flag=false;
break;
}
}
if(flag==true){
a[i++]=s;
p.println(i+" . "+a[i-1]);
}flag=true;
}
}
}
这就是我通过对排列和递归函数调用的基本理解所做的。虽然要花点时间,但都是独立完成的。
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]。
//插入每个字符到数组列表中
static ArrayList al = new ArrayList();
private static void findPermutation (String str){
for (int k = 0; k < str.length(); k++) {
addOneChar(str.charAt(k));
}
}
//insert one char into ArrayList
private static void addOneChar(char ch){
String lastPerStr;
String tempStr;
ArrayList locAl = new ArrayList();
for (int i = 0; i < al.size(); i ++ ){
lastPerStr = al.get(i).toString();
//System.out.println("lastPerStr: " + lastPerStr);
for (int j = 0; j <= lastPerStr.length(); j++) {
tempStr = lastPerStr.substring(0,j) + ch +
lastPerStr.substring(j, lastPerStr.length());
locAl.add(tempStr);
//System.out.println("tempStr: " + tempStr);
}
}
if(al.isEmpty()){
al.add(ch);
} else {
al.clear();
al = locAl;
}
}
private static void printArrayList(ArrayList al){
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
}
推荐文章
- 创建正则表达式匹配数组
- 我如何在Java中初始化一个全零的数组列表?
- 主体、使用者和主体之间的意义和区别是什么?
- 将字节转换为十六进制
- HashSet和HashMap的区别?
- 我如何有效地解析HTML与Java?
- Java构造函数继承
- 如何在Java中将int[]转换为Integer[] ?
- 你能解释一下流的概念吗?
- 导致java.lang.VerifyError错误的原因
- 如何在Java中监控计算机的CPU、内存和磁盘使用情况?
- 如何设置超时在改造库?
- java lambda可以有一个以上的参数吗?
- HashMap -获取第一个键值
- 使用Jackson将JSON字符串转换为漂亮的打印JSON输出