10秒之内，把蔡依林从这堆凤姐中找出来！ (转) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

10秒之内，把蔡依林从这堆凤姐中找出来！ (转)

10秒之内，把蔡依林从这堆凤姐中找出来！ (转)# Joke - 肚皮舞运动

e*e2012-10-11 07:10

1 楼

多谢lolhaha大牛指点，non-duplicate修订版如下。
client invoke: permute( new char[]{'a', 'b', 'c'}, 0 );
void permute(char[] perm, int level）{
if ( level == perm.length ) {
System.out.println( new String( perm ) );
for ( int i = level, i < perm.length; i++ ) {
if ( level != i )
swap( perm, level, i );
permute( perm, level + 1 );
if ( level != i )
swap( perm, level, i );
}
}
void swap(char[] arr, int i, int j) {...}

F*o2012-10-11 07:10

2 楼

提交了RFE,收到通知（网站上状态显示也是）说60天会出结果，但是现在超过60天了，
还是一点消息都没有，正常吗？谢谢啦

C*a2012-10-11 07:10

3 楼

Need to do home inspection. Heard some inspectors can use infrared camera to
find out if a finished basement has water leakage. Just wondering if the
tool can find small damp area or very minor leakage. Can anyone comment on
the usefulness to inspect finished basement with infrared camera?
Thanks.

r*r2012-10-11 07:10

4 楼

Cutter 天然杀虫喷雾的deal，41% off，link:
https://t.co/BLRWxfpl6i

c*72012-10-11 07:10

5 楼

l*a2012-10-11 07:10

6 楼

please change == to !=
thanks

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点，non-duplicate修订版如下。
: client invoke: permute( new char[]{'a', 'b', 'c'}, 0 );
: void permute(char[] perm, int level）{
: if ( level == perm.length ) {
: System.out.println( new String( perm ) );
: for ( int i = level, i < perm.length; i++ ) {
: if ( level != i )
: swap( perm, level, i );
: permute( perm, level + 1 );
: if ( level != i )

F*a2012-10-11 07:10

7 楼

不一定的，
call 他们试一下

【在 F*******o 的大作中提到】

: 提交了RFE,收到通知（网站上状态显示也是）说60天会出结果，但是现在超过60天了，
: 还是一点消息都没有，正常吗？谢谢啦

s*t2012-10-11 07:10

8 楼

有点用处，但非常有限。 Inspector的经验更重要。

s*l2012-10-11 07:10

9 楼

那个是蔡依林？感觉还不如凤姐

l*a2012-10-11 07:10

10 楼

btw, seems 1 [] as parameter will be enough

【在 e****e 的大作中提到】

a*r2012-10-11 07:10

11 楼

众里寻她三五秒，眼眵睛转，那人却在行四列六笑。

e*e2012-10-11 07:10

12 楼

Changed. Thanks.

【在 l*****a 的大作中提到】

: please change == to !=
: thanks

j*g2012-10-11 07:10

13 楼

蔡本来就是个丑女，比凤姐强不了多少

e*e2012-10-11 07:10

14 楼

Totally. arr and level could extract from function signature and become a
global variable outside of the function. Thank you!

【在 l*****a 的大作中提到】

: btw, seems 1 [] as parameter will be enough

l*o2012-10-11 07:10

15 楼

20秒

【在 a*******r 的大作中提到】

: 众里寻她三五秒，眼眵睛转，那人却在行四列六笑。

l*a2012-10-11 07:10

16 楼

no, for the logic inside the function,u don;t need arr

【在 e****e 的大作中提到】

: Totally. arr and level could extract from function signature and become a
: global variable outside of the function. Thank you!

i*02012-10-11 07:10

17 楼

双生？

e*e2012-10-11 07:10

18 楼

按照permuation的规律交换arr中的两个元素？

【在 l*****a 的大作中提到】

: no, for the logic inside the function,u don;t need arr

e*e2012-10-11 07:10

19 楼

多谢lolhaha大牛指点。很有收获。

【在 l*****a 的大作中提到】

: no, for the logic inside the function,u don;t need arr

a*l2012-10-11 07:10

20 楼

你的最优是什么意思?速度最快?空间最小?程序代码最短?

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点。很有收获。

e*e2012-10-11 07:10

21 楼

Time and space complexity. 没有其他解法能比这个解答， use less time and
space.

【在 a****l 的大作中提到】

: 你的最优是什么意思?速度最快?空间最小?程序代码最短?

c*t2012-10-11 07:10

22 楼

我也才整明白，不容易想

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点。很有收获。

c*t2012-10-11 07:10

23 楼

能不能和下面解法对比一下优缺点？
public static void permutation(String str) {
permutation("", str);
}
private 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));
}
}

【在 e****e 的大作中提到】

: Time and space complexity. 没有其他解法能比这个解答， use less time and
: space.

e*e2012-10-11 07:10

24 楼

Time complexity is the same. The space complexity difference is huge. With
String, each recursion create two new strings. While with char array, it
only uses one copy of the char array throughout the program.

【在 c********t 的大作中提到】

: 能不能和下面解法对比一下优缺点？
: public static void permutation(String str) {
: permutation("", str);
: }
: private 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.

c*t2012-10-11 07:10

25 楼

是的。多谢！

【在 e****e 的大作中提到】

: Time complexity is the same. The space complexity difference is huge. With
: String, each recursion create two new strings. While with char array, it
: only uses one copy of the char array throughout the program.

a*l2012-10-11 07:10

26 楼

时间上不好说，不过空间上这个解法是要用到递归的，不见得比非递归的算法更省空间
吧？理论上应该非递归的iterative算法最快最省空间，每次仅把必须换的字符换掉，
别的算法应该不可能效率更高吧？

【在 e****e 的大作中提到】

: Time and space complexity. 没有其他解法能比这个解答， use less time and
: space.

e*e2012-10-11 07:10

27 楼

Thank you for your suggestion. I can see your point and 100% agree with you.
My question is how to implement the iterative solution. If the length is
fixed, we can do something like below. But if not, how to implement the
function void permute(char[] a) iteratively?
char[] arr = new char[]{'a', 'b', 'c'};
for ( int i = 0; i < 3; i++ ) {
for ( int j = 0; j < 3; j++ ) {
for ( int k = 0; k < 3; k++ ) {
if ( i != j && j != k && k != i )
System.out.println( arr[i] + arr[j] + arr[k] );
}
}
}

【在 a****l 的大作中提到】

: 时间上不好说，不过空间上这个解法是要用到递归的，不见得比非递归的算法更省空间
: 吧？理论上应该非递归的iterative算法最快最省空间，每次仅把必须换的字符换掉，
: 别的算法应该不可能效率更高吧？

p*22012-10-11 07:10

28 楼

用ruby练一下
a=[1,2,3]
p a.permutation.to_a

l*a2012-10-11 07:10

29 楼

牛！！！

【在 p*****2 的大作中提到】

: 用ruby练一下
: a=[1,2,3]
: p a.permutation.to_a

l*a2012-10-11 07:10

30 楼

所有二分的程序都是
Arrays.binarysearch()就搞定了吧？

【在 p*****2 的大作中提到】

: 用ruby练一下
: a=[1,2,3]
: p a.permutation.to_a

p*22012-10-11 07:10

31 楼

不好说吧？

【在 l*****a 的大作中提到】

: 所有二分的程序都是
: Arrays.binarysearch()就搞定了吧？

w*p2012-10-11 07:10

32 楼

我一直以为你们在讨论P (n, m)的所有String. 原来是 P(n, n). 看起来code 很简洁,
很赞。我再学习下。
有两处typo:
1) if ( level == perm.length ) {
: System.out.println( new String( perm ) );
"}" is missing
2) for ( int i = level, i < perm.length; i++ ) {
=> for ( int i = level; i < perm.length; i++ ) {

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点。很有收获。

e*e2012-10-11 07:10

33 楼

Thanks for your pointing out. I corrected it.

【在 w********p 的大作中提到】

: 我一直以为你们在讨论P (n, m)的所有String. 原来是 P(n, n). 看起来code 很简洁,
: 很赞。我再学习下。
: 有两处typo:
: 1) if ( level == perm.length ) {
: : System.out.println( new String( perm ) );
: "}" is missing
: 2) for ( int i = level, i < perm.length; i++ ) {
: => for ( int i = level; i < perm.length; i++ ) {

h*02012-10-11 07:10

34 楼

permutation用字典序比较好吧。这个recursive空间复杂度太高了。。

e*e2012-10-11 07:10

35 楼

what's 字典序? Details please. The space complexity is n. n is the length of
array. The length of the deepest recursion is also n.

【在 h*******0 的大作中提到】

: permutation用字典序比较好吧。这个recursive空间复杂度太高了。。

e*e2012-10-11 07:10

36 楼

多谢lolhaha大牛指点，non-duplicate修订版如下。
client invoke: permute( new char[]{'a', 'b', 'c'}, 0 );
void permute(char[] perm, int level）{
if ( level == perm.length )
System.out.println( new String( perm ) );
for ( int i = level; i < perm.length; i++ ) {
if ( level != i )
swap( perm, level, i );
permute( perm, level + 1 );
if ( level != i )
swap( perm, level, i );
}
}
void swap(char[] arr, int i, int j) {...}

l*a2012-10-11 07:10

37 楼

please change == to !=
thanks

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点，non-duplicate修订版如下。
: client invoke: permute( new char[]{'a', 'b', 'c'}, 0 );
: void permute(char[] perm, int level）{
: if ( level == perm.length )
: System.out.println( new String( perm ) );
: for ( int i = level; i < perm.length; i++ ) {
: if ( level != i )
: swap( perm, level, i );
: permute( perm, level + 1 );
: if ( level != i )

l*a2012-10-11 07:10

38 楼

btw, seems 1 [] as parameter will be enough

【在 e****e 的大作中提到】

e*e2012-10-11 07:10

39 楼

Changed. Thanks.

【在 l*****a 的大作中提到】

: please change == to !=
: thanks

e*e2012-10-11 07:10

40 楼

Totally. arr and level could extract from function signature and become a
global variable outside of the function. Thank you!

【在 l*****a 的大作中提到】

: btw, seems 1 [] as parameter will be enough

l*a2012-10-11 07:10

41 楼

no, for the logic inside the function,u don;t need arr

【在 e****e 的大作中提到】

: Totally. arr and level could extract from function signature and become a
: global variable outside of the function. Thank you!

e*e2012-10-11 07:10

42 楼

按照permuation的规律交换arr中的两个元素？

【在 l*****a 的大作中提到】

: no, for the logic inside the function,u don;t need arr

e*e2012-10-11 07:10

43 楼

多谢lolhaha大牛指点。很有收获。

【在 l*****a 的大作中提到】

: no, for the logic inside the function,u don;t need arr

a*l2012-10-11 07:10

44 楼

你的最优是什么意思?速度最快?空间最小?程序代码最短?

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点。很有收获。

e*e2012-10-11 07:10

45 楼

Time and space complexity. 没有其他解法能比这个解答， use less time and
space.

【在 a****l 的大作中提到】

: 你的最优是什么意思?速度最快?空间最小?程序代码最短?

c*t2012-10-11 07:10

46 楼

我也才整明白，不容易想

【在 e****e 的大作中提到】

: 多谢lolhaha大牛指点。很有收获。

c*t2012-10-11 07:10

47 楼

: Time and space complexity. 没有其他解法能比这个解答， use less time and
: space.

e*e2012-10-11 07:10

48 楼

c*t2012-10-11 07:10

49 楼

是的。多谢！

【在 e****e 的大作中提到】

a*l2012-10-11 07:10

50 楼

: Time and space complexity. 没有其他解法能比这个解答， use less time and
: space.

e*e2012-10-11 07:10

51 楼

p*22012-10-11 07:10

52 楼

用ruby练一下
a=[1,2,3]
p a.permutation.to_a

l*a2012-10-11 07:10

53 楼

牛！！！

【在 p*****2 的大作中提到】

: 用ruby练一下
: a=[1,2,3]
: p a.permutation.to_a

l*a2012-10-11 07:10

54 楼

所有二分的程序都是
Arrays.binarysearch()就搞定了吧？

【在 p*****2 的大作中提到】

: 用ruby练一下
: a=[1,2,3]
: p a.permutation.to_a

p*22012-10-11 07:10

55 楼

不好说吧？

【在 l*****a 的大作中提到】

: 所有二分的程序都是
: Arrays.binarysearch()就搞定了吧？

w*p2012-10-11 07:10

56 楼

: 多谢lolhaha大牛指点。很有收获。

e*e2012-10-11 07:10

57 楼

Thanks for your pointing out. I corrected it.

【在 w********p 的大作中提到】

h*02012-10-11 07:10

58 楼

permutation用字典序比较好吧。这个recursive空间复杂度太高了。。

e*e2012-10-11 07:10

59 楼

what's 字典序? Details please. The space complexity is n. n is the length of
array. The length of the deepest recursion is also n.

【在 h*******0 的大作中提到】

: permutation用字典序比较好吧。这个recursive空间复杂度太高了。。

b*72012-10-11 07:10

60 楼

字典序指的就是next permutation的顺序吧，从小到大。
如果有重复元素，要求不重复的permutation，这个方法就不适用了，那样什么又才是
最优解呢？

c*72012-10-11 07:10

61 楼

c# 来一个：
public static IEnumerable> P(IEnumerable list) {if (
list.Count() == 1)return new List> { list };return list.
Select((a, i1) => P(list.Where((b, i2) => i2 != i1)).Select(b => (new List> { a }).Union(b))).SelectMany(c => c);}

c*d2012-10-11 07:10

62 楼

dedup is doable too using this approach. just check whether you've seen the
item before swapping.
here is javascript version.
function dedup_perm(a){
var solutions = [];
if (!a || a.length == 0) return [];
return dedup_perm_helper(a, 0);
function dedup_perm_helper(a, start) {
if(start == a.length) solutions.push(a.slice(0));
var seen = {};
for(var i = start; i < a.length; i++){
if (!seen[a[i]]) { // this line ensures no dup permutations.
seen[a[i]] = 1;
swap(a, start, i);
dedup_perm_helper(a, start + 1);
swap(a, start, i);
}
}
return solutions;
}

function swap(a, i, j){
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
console.log(dedup_perm([1,2,3,2]));
/// output ///
[ [ 1, 2, 3, 2 ],
[ 1, 2, 2, 3 ],
[ 1, 3, 2, 2 ],
[ 2, 1, 3, 2 ],
[ 2, 1, 2, 3 ],
[ 2, 3, 1, 2 ],
[ 2, 3, 2, 1 ],
[ 2, 2, 3, 1 ],
[ 2, 2, 1, 3 ],
[ 3, 2, 1, 2 ],
[ 3, 2, 2, 1 ],
[ 3, 1, 2, 2 ] ]

【在 b*******7 的大作中提到】

: 字典序指的就是next permutation的顺序吧，从小到大。
: 如果有重复元素，要求不重复的permutation，这个方法就不适用了，那样什么又才是
: 最优解呢？

j*x2012-10-11 07:10

63 楼

又来调戏版友。。。

【在 p*****2 的大作中提到】

: 用ruby练一下
: a=[1,2,3]
: p a.permutation.to_a