n******r 发帖数: 869 | 1 实在太落后了。看了解法还是不会写。
Design an algorithm to print all permutations of a string. For simplicity,
assume all characters are unique.
Test String: abcdefg
Case “a” --> {a}
Case “ab” --> {ab, ba}
Case “abc” --> ?
This is the first “interesting” case. If we had the answer to P(“ab”),
how could we generate P(“abc”). Well, the additional letter is “c”, so
we can just stick c in at every possible point. That is:
merge(c, ab) --> cab, acb, abc
merge(c, ba) --> cba, bca, bac
Algorithm: Use a recursive algorithm. Generate all permutations of a string
by “chopping off” the last character and generating all permutations of s[
1… n-1]. Then, insert s[n] into every location of the string. | h**i 发帖数: 219 | 2 The simplest method is by recursion: if you have k letters, then print the
first letter, call the function on the remaining (k-1) letters;
then second letter, and so on. | x*******6 发帖数: 262 | | t******i 发帖数: 483 | 4 public static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i)
+ str.substring(i + 1, n));
}
}
} | x******a 发帖数: 6336 | 5 is it ok to use the stl? | p*****2 发帖数: 21240 | 6 我写了一个练练
val str="abc"
str.permutations.foreach(println)
output:
abc
acb
bac
bca
cab
cba | l*****a 发帖数: 14598 | 7 whether null is supported in this language?
whether null.permutation is legal?
【在 p*****2 的大作中提到】 : 我写了一个练练 : val str="abc" : str.permutations.foreach(println) : output: : abc : acb : bac : bca : cab : cba
| p*****2 发帖数: 21240 | 8
obviously. you have no idea about scala. null is java thing
【在 l*****a 的大作中提到】 : whether null is supported in this language? : whether null.permutation is legal?
| l*****a 发帖数: 14598 | 9 anything can match null in scala?
【在 p*****2 的大作中提到】 : : obviously. you have no idea about scala. null is java thing
| n******r 发帖数: 869 | 10 有落后了
what is scala:
Scala is a general purpose programming language designed to express common
programming patterns in a concise, elegant, and type-safe way. It smoothly
integrates features of object-oriented and functional languages, enabling
Java and other programmers to be more productive. Code sizes are typically
reduced by a factor of two to three when compared to an equivalent Java
application. | | | d**********x 发帖数: 4083 | 11 四月一起学这个吧!
https://www.coursera.org/course/progfun
【在 n******r 的大作中提到】 : 有落后了 : what is scala: : Scala is a general purpose programming language designed to express common : programming patterns in a concise, elegant, and type-safe way. It smoothly : integrates features of object-oriented and functional languages, enabling : Java and other programmers to be more productive. Code sizes are typically : reduced by a factor of two to three when compared to an equivalent Java : application.
| n******r 发帖数: 869 | 12
思路好像跟开始不大一样,不过试了abc例子好像work的
str.length最小为1吧?
该了2行
if (n == 0) 改成 if (n == 1)
permutation(prefix + str.charAt(i), str.substring(0, i)
+ str.substring(i + 1, n)); 中的str.substring(0, i)改成str.substring(0, i
-1)
不知对不对
以abc为例
permutation(null, abc)
--> P(a,bc),P(b,ac),P(c,ab)
-->P(a,P(b,c)),P(a,P(c,b)),P(b,P(a,c)),P(a,P(c,a)),P(c,P(a,b)),P(c,P(b,a))
【在 t******i 的大作中提到】 : public static void permutation(String prefix, String str) { : int n = str.length(); : if (n == 0) : System.out.println(prefix); : else { : for (int i = 0; i < n; i++) { : permutation(prefix + str.charAt(i), str.substring(0, i) : + str.substring(i + 1, n)); : } : }
| n******r 发帖数: 869 | 13 就是觉得还绕啊,写写就左右为难。
【在 x*******6 的大作中提到】 : 经典算法,直接背下来吧,10行左右。
| p*****2 发帖数: 21240 | 14
大牛准备要学吗?
【在 d**********x 的大作中提到】 : 四月一起学这个吧! : https://www.coursera.org/course/progfun
| d**********x 发帖数: 4083 | 15 Orz
我不是大牛啊,最近在反思,感觉弱爆了。。
我打算学,不过不急,到时候跟课程了
【在 p*****2 的大作中提到】 : : 大牛准备要学吗?
| p*****2 发帖数: 21240 | 16
我也准备跟课程了。对FP的性能心里没底。现在还是不敢搞纯的。也许是水平太差了。
不过听说scala的library里边都是imperative的。我最近也觉得报弱。可是比你差远的
,还没有好好反思。
【在 d**********x 的大作中提到】 : Orz : 我不是大牛啊,最近在反思,感觉弱爆了。。 : 我打算学,不过不急,到时候跟课程了
| h*****a 发帖数: 1718 | 17 Knuth有个很牛的算法,还可以handle重复字符。大概30行。
【在 n******r 的大作中提到】 : 实在太落后了。看了解法还是不会写。 : Design an algorithm to print all permutations of a string. For simplicity, : assume all characters are unique. : Test String: abcdefg : Case “a” --> {a} : Case “ab” --> {ab, ba} : Case “abc” --> ? : This is the first “interesting” case. If we had the answer to P(“ab”), : how could we generate P(“abc”). Well, the additional letter is “c”, so : we can just stick c in at every possible point. That is:
|
|