由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 谁能帮我写写这道题? print all permutations of a string
相关主题
今天才整明白Permutation的最优解!?问一个题目
关于排列组合的题目的算法谁能贴一下求nth permutation 和已知permutation 求rank的code
Exposed上一道string permutation的题请教 怎样存下这个string
Given a string, find all its permutations without any repetition?T家电面面经并且不解为何被秒拒
Permutation leetcode-求问个G家面试题
大家能说说(leecode) Permutation Sequence这道题后的数学思路吗?String permunation question (CS)
leetcode 的 permutations 一题 oj 怎么不过Non-recursive permutation
谁能猜猜,这是个什么 algorithm?一道amazon题
相关话题的讨论汇总
话题: string话题: case话题: abc话题: ab
进入JobHunting版参与讨论
1 (共1页)
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
3
经典算法,直接背下来吧,10行左右。
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.
相关主题
大家能说说(leecode) Permutation Sequence这道题后的数学思路吗?问一个题目
leetcode 的 permutations 一题 oj 怎么不过谁能贴一下求nth permutation 和已知permutation 求rank的code
谁能猜猜,这是个什么 algorithm?请教 怎样存下这个string
进入JobHunting版参与讨论
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:

1 (共1页)
进入JobHunting版参与讨论
相关主题
一道amazon题Permutation leetcode-
这两道leetcode题有更好的答案吗?大家能说说(leecode) Permutation Sequence这道题后的数学思路吗?
一道面试碰到的概率题leetcode 的 permutations 一题 oj 怎么不过
youtube, tripadvisor的onsite面经谁能猜猜,这是个什么 algorithm?
今天才整明白Permutation的最优解!?问一个题目
关于排列组合的题目的算法谁能贴一下求nth permutation 和已知permutation 求rank的code
Exposed上一道string permutation的题请教 怎样存下这个string
Given a string, find all its permutations without any repetition?T家电面面经并且不解为何被秒拒
相关话题的讨论汇总
话题: string话题: case话题: abc话题: ab