找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
让我试着用Kotlin来解决这个问题:
fun <T> List<T>.permutations(): List<List<T>> {
//escape case
if (this.isEmpty()) return emptyList()
if (this.size == 1) return listOf(this)
if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))
//recursive case
return this.flatMap { lastItem ->
this.minus(lastItem).permutations().map { it.plus(lastItem) }
}
}
核心概念:将长链表分解成小链表+递归
长答案与示例列表[1,2,3,4]:
即使是一个4种组合的列表,在脑海中列出所有可能的排列已经有点令人困惑了,我们需要做的就是避免这种情况。我们很容易理解如何对大小为0、1和2的列表进行排列,因此我们所需要做的就是将它们分解为这些大小中的任何一个,并将它们正确地组合起来。想象一台头奖机器:这个算法将从右向左旋转,然后写下
当列表大小为0或1时,返回空/列表为1 当列表大小为2时处理(例如[3,4]),并生成2个排列([3,4]& [4,3]) 对于每一项,将其标记为最后一项中的最后一项,并找到列表中其余项目的所有排列。(例如,把[4]放在桌子上,把[1,2,3]重新排列) 现在对它的子元素进行所有的排列,把它自己放回列表的末尾(例如:[1,2,3][,4],[1,3,2][,4],[2,3,1][,4],…)
其他回答
/** Returns an array list containing all
* permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
ArrayList<String> perms = new ArrayList<>();
int slen = s.length();
if (slen > 0) {
// Add the first character from s to the perms array list.
perms.add(Character.toString(s.charAt(0)));
// Repeat for all additional characters in s.
for (int i = 1; i < slen; ++i) {
// Get the next character from s.
char c = s.charAt(i);
// For each of the strings currently in perms do the following:
int size = perms.size();
for (int j = 0; j < size; ++j) {
// 1. remove the string
String p = perms.remove(0);
int plen = p.length();
// 2. Add plen + 1 new strings to perms. Each new string
// consists of the removed string with the character c
// inserted into it at a unique location.
for (int k = 0; k <= plen; ++k) {
perms.add(p.substring(0, k) + c + p.substring(k));
}
}
}
}
return perms;
}
没有递归的Java实现
public Set<String> permutate(String s){
Queue<String> permutations = new LinkedList<String>();
Set<String> v = new HashSet<String>();
permutations.add(s);
while(permutations.size()!=0){
String str = permutations.poll();
if(!v.contains(str)){
v.add(str);
for(int i = 0;i<str.length();i++){
String c = String.valueOf(str.charAt(i));
permutations.add(str.substring(i+1) + c + str.substring(0,i));
}
}
}
return v;
}
倒计时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,因为泛型不能很好地使用数组。
//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--]);
}
}
}
以下是我在《破解编程面试》(P54)一书中提出的解决方案:
/**
* List permutations of a string.
*
* @param s the input string
* @return the list of permutations
*/
public static ArrayList<String> permutation(String s) {
// The result
ArrayList<String> res = new ArrayList<String>();
// If input string's length is 1, return {s}
if (s.length() == 1) {
res.add(s);
} else if (s.length() > 1) {
int lastIndex = s.length() - 1;
// Find out the last character
String last = s.substring(lastIndex);
// Rest of the string
String rest = s.substring(0, lastIndex);
// Perform permutation on the rest string and
// merge with the last character
res = merge(permutation(rest), last);
}
return res;
}
/**
* @param list a result of permutation, e.g. {"ab", "ba"}
* @param c the last character
* @return a merged new list, e.g. {"cab", "acb" ... }
*/
public static ArrayList<String> merge(ArrayList<String> list, String c) {
ArrayList<String> res = new ArrayList<>();
// Loop through all the string in the list
for (String s : list) {
// For each string, insert the last character to all possible positions
// and add them to the new list
for (int i = 0; i <= s.length(); ++i) {
String ps = new StringBuffer(s).insert(i, c).toString();
res.add(ps);
}
}
return res;
}
字符串"abcd"的运行输出:
第一步:合并[a]和b: [ba, ab] 步骤2:Merge [ba, ab]和c: [cba, bca, bac, cab, acb, abc] 第三步:Merge [cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbad, cbca, bdcad
推荐文章
- 在流中使用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