找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
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;
}
}
}
其他回答
倒计时Quickperm算法的通用实现,表示#1(可伸缩,非递归)。
/**
* Generate permutations based on the
* Countdown <a href="http://quickperm.org/">Quickperm algorithm</>.
*/
public static <T> List<List<T>> generatePermutations(List<T> list) {
List<T> in = new ArrayList<>(list);
List<List<T>> out = new ArrayList<>(factorial(list.size()));
int n = list.size();
int[] p = new int[n +1];
for (int i = 0; i < p.length; i ++) {
p[i] = i;
}
int i = 0;
while (i < n) {
p[i]--;
int j = 0;
if (i % 2 != 0) { // odd?
j = p[i];
}
// swap
T iTmp = in.get(i);
in.set(i, in.get(j));
in.set(j, iTmp);
i = 1;
while (p[i] == 0){
p[i] = i;
i++;
}
out.add(new ArrayList<>(in));
}
return out;
}
private static int factorial(int num) {
int count = num;
while (num != 1) {
count *= --num;
}
return count;
}
它需要list,因为泛型不能很好地使用数组。
基于Mark Byers的回答,我的python实现:
def permutations(string):
if len(string) == 1:
return [string]
permutations=[]
for i in range(len(string)):
for perm in permutations(string[:i]+string[i+1:]):
permutations.append(string[i] + perm)
return permutations
在python中
def perms(in_str, prefix=""):
if not len(in_str) :
print(prefix)
else:
for i in range(0, len(in_str)):
perms(in_str[:i] + in_str[i + 1:], prefix + in_str[i])
perms('ASD')
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
//Rotate and create words beginning with all letter possible and push to stack 1
//Read from stack1 and for each word create words with other letters at the next location by rotation and so on
/* eg : man
1. push1 - man, anm, nma
2. pop1 - nma , push2 - nam,nma
pop1 - anm , push2 - amn,anm
pop1 - man , push2 - mna,man
*/
public class StringPermute {
static String str;
static String word;
static int top1 = -1;
static int top2 = -1;
static String[] stringArray1;
static String[] stringArray2;
static int strlength = 0;
public static void main(String[] args) throws IOException {
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
str = bfr.readLine();
word = str;
strlength = str.length();
int n = 1;
for (int i = 1; i <= strlength; i++) {
n = n * i;
}
stringArray1 = new String[n];
stringArray2 = new String[n];
push(word, 1);
doPermute();
display();
}
public static void push(String word, int x) {
if (x == 1)
stringArray1[++top1] = word;
else
stringArray2[++top2] = word;
}
public static String pop(int x) {
if (x == 1)
return stringArray1[top1--];
else
return stringArray2[top2--];
}
public static void doPermute() {
for (int j = strlength; j >= 2; j--)
popper(j);
}
public static void popper(int length) {
// pop from stack1 , rotate each word n times and push to stack 2
if (top1 > -1) {
while (top1 > -1) {
word = pop(1);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 2);
}
}
}
// pop from stack2 , rotate each word n times w.r.t position and push to
// stack 1
else {
while (top2 > -1) {
word = pop(2);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 1);
}
}
}
}
public static void rotate(int position) {
char[] charstring = new char[100];
for (int j = 0; j < word.length(); j++)
charstring[j] = word.charAt(j);
int startpos = strlength - position;
char temp = charstring[startpos];
for (int i = startpos; i < strlength - 1; i++) {
charstring[i] = charstring[i + 1];
}
charstring[strlength - 1] = temp;
word = new String(charstring).trim();
}
public static void display() {
int top;
if (top1 > -1) {
while (top1 > -1)
System.out.println(stringArray1[top1--]);
} else {
while (top2 > -1)
System.out.println(stringArray2[top2--]);
}
}
}
推荐文章
- 在流中使用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