Permutation一问# JobHunting - 待字闺中
Z*Z
1 楼
给一个数组和一个random number generator,写一个函数，返回这个数组的一个permut
ation, 要求任何可能的permutation都被等概率返回。
怎么做？
ation, 要求任何可能的permutation都被等概率返回。
怎么做？
m*g
2 楼
你这个rand gen 产生的数的范围跟数组大小一致贝
Z*Z
3 楼
然后呢？
我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
permutation
只是这第i个permutation不太好直接做吧？
【在 m*****g 的大作中提到】
: 你这个rand gen 产生的数的范围跟数组大小一致贝
我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
permutation
只是这第i个permutation不太好直接做吧？
【在 m*****g 的大作中提到】
: 你这个rand gen 产生的数的范围跟数组大小一致贝
l*a
4 楼
next permutation
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
h*6
5 楼
可以连续除以(N-1)!, (N-2)!, (N-3)!然后取商取余
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
x*m
6 楼
参见著名的洗牌问题
t*n
7 楼
permut
这个可以这样做,假设数组元素从A[0]到A[n-1]
我们先取A[0]放入一个double linked list
对于A[1],用一个生成0或者1的random generator产生0或者1,0就把A[1]插入到A[0]的
左边,否则就右边.
现在list里面有A[0]和A[1],他们的左边右边中间有三个位置可以插入.....依次类推,
对于A[n-1],有N个位置可以插入
最后的算法可以是直接产生一个0到N!-1的随机数n, 然后把它mod2, mod 3, ...
这题有个陷阱就是如果数组有重复元素该怎么办...我得想想
【在 Z*****Z 的大作中提到】
: 给一个数组和一个random number generator,写一个函数，返回这个数组的一个permut
: ation, 要求任何可能的permutation都被等概率返回。
: 怎么做？
l*e
8 楼
next_permutation + reservoir sampling (will handle the duplicate cases)
Z*Z
9 楼
哦，用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢？
【在 l******e 的大作中提到】
: next_permutation + reservoir sampling (will handle the duplicate cases)
【在 l******e 的大作中提到】
: next_permutation + reservoir sampling (will handle the duplicate cases)
P*b
10 楼
coask
【在 Z*****Z 的大作中提到】
: 哦，用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢？
【在 Z*****Z 的大作中提到】
: 哦，用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢？
P*l
11 楼
你的想法是对的。但是实现起来还是优点麻烦。
如果一个数组的长度是n，那末，一共有n!种排列. 每种都可以写成基数｛n, n-１, ..
., 2, 1, 0}的格式。比如，第一个到第三个是{0,0...,1,0}，{0,0...1,0,0}，{0,0..
.2,1,0}.
这个序列的含义是左边有多少个数比当前的数大。
比如，给定一个排列 {3,2,1,4}, 那末对应的序列是{2,1,0,0}.
根据这种方法，对于一个随机数，可以在o(n)内产生对应的排列。
代码：
完整的代码在：
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/PermutationImpl.java
看看有问题没？
@Override
public T[] get(Long index) {
// adjust to 1-based.
index++;
// parse the index to {n-1, n-2, ... 3, 2, 1, 0}-based number.
// For example, 10 = {1, 1, 1, 1, 0}. The meaning of each digits is
the
// number of digits on the left greater than current digit. For
example,
// in object list {a, b, d, c, e}, The corresponding index = {0, 0,
1,
// 0, 0}. Because c has d on the left.
Integer[] permArr = new Integer[n];
for (int i = n - 1; i >= 0; i--) {
permArr[i] = (int) ((index % (n - i)));
index /= n - i;
}
// keep objList2 as a reference.
T[] objList2 = Arrays.copyOf(objList, n);
for (int objIdx = 0; objIdx < n; objIdx++) {
int pos = 0;
// get current object obj and find its current position in the
// object list.
T obj = objList2[objIdx];
for (int i = 0; i < n; i++) {
if (obj.equals(objList[i])) {
pos = i;
break;
}
}
// the number of objects in reversed order (objects on the left
and
// greater than current object.)
int revOrd = permArr[objIdx];
for (int i = 0; i < n; i++) {
// no object in reversed order. done.
if (revOrd <= 0)
break;
// pass if the objects in list are smaller than current obj
if (obj.compareTo(objList[i]) >= 0)
continue;
// move to larger objects to the left to fulfill "revOrd"
number
// of objects in reversed order.
if (i > pos) {
objList[pos] = objList[i];
pos = i;
}
revOrd--;
if (revOrd <= 0) {
// put obj back for the last one
objList[pos] = obj;
break;
}
}
}
return objList;
}
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
如果一个数组的长度是n，那末，一共有n!种排列. 每种都可以写成基数｛n, n-１, ..
., 2, 1, 0}的格式。比如，第一个到第三个是{0,0...,1,0}，{0,0...1,0,0}，{0,0..
.2,1,0}.
这个序列的含义是左边有多少个数比当前的数大。
比如，给定一个排列 {3,2,1,4}, 那末对应的序列是{2,1,0,0}.
根据这种方法，对于一个随机数，可以在o(n)内产生对应的排列。
代码：
完整的代码在：
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/PermutationImpl.java
看看有问题没？
@Override
public T[] get(Long index) {
// adjust to 1-based.
index++;
// parse the index to {n-1, n-2, ... 3, 2, 1, 0}-based number.
// For example, 10 = {1, 1, 1, 1, 0}. The meaning of each digits is
the
// number of digits on the left greater than current digit. For
example,
// in object list {a, b, d, c, e}, The corresponding index = {0, 0,
1,
// 0, 0}. Because c has d on the left.
Integer[] permArr = new Integer[n];
for (int i = n - 1; i >= 0; i--) {
permArr[i] = (int) ((index % (n - i)));
index /= n - i;
}
// keep objList2 as a reference.
T[] objList2 = Arrays.copyOf(objList, n);
for (int objIdx = 0; objIdx < n; objIdx++) {
int pos = 0;
// get current object obj and find its current position in the
// object list.
T obj = objList2[objIdx];
for (int i = 0; i < n; i++) {
if (obj.equals(objList[i])) {
pos = i;
break;
}
}
// the number of objects in reversed order (objects on the left
and
// greater than current object.)
int revOrd = permArr[objIdx];
for (int i = 0; i < n; i++) {
// no object in reversed order. done.
if (revOrd <= 0)
break;
// pass if the objects in list are smaller than current obj
if (obj.compareTo(objList[i]) >= 0)
continue;
// move to larger objects to the left to fulfill "revOrd"
number
// of objects in reversed order.
if (i > pos) {
objList[pos] = objList[i];
pos = i;
}
revOrd--;
if (revOrd <= 0) {
// put obj back for the last one
objList[pos] = obj;
break;
}
}
}
return objList;
}
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
P*l
12 楼
Also here:
http://en.wikipedia.org/wiki/Permutation#Random_generation_of_permutations
BTW, this is first posted in May.
http://en.wikipedia.org/wiki/Permutation#Random_generation_of_permutations
BTW, this is first posted in May.
p*7
13 楼
你没考虑有重复的情况比如 数据是 1，1，3，5
..
..
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/P
ermutationImpl.java
【在 P********l 的大作中提到】
: 你的想法是对的。但是实现起来还是优点麻烦。
: 如果一个数组的长度是n，那末，一共有n!种排列. 每种都可以写成基数｛n, n-１, ..
: ., 2, 1, 0}的格式。比如，第一个到第三个是{0,0...,1,0}，{0,0...1,0,0}，{0,0..
: .2,1,0}.
: 这个序列的含义是左边有多少个数比当前的数大。
: 比如，给定一个排列 {3,2,1,4}, 那末对应的序列是{2,1,0,0}.
: 根据这种方法，对于一个随机数，可以在o(n)内产生对应的排列。
: 代码：
: 完整的代码在：
: http://code.google.com/p/sureinterview/source/browse/src/lib/combination/PermutationImpl.java
..
..
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/P
ermutationImpl.java
【在 P********l 的大作中提到】
: 你的想法是对的。但是实现起来还是优点麻烦。
: 如果一个数组的长度是n，那末，一共有n!种排列. 每种都可以写成基数｛n, n-１, ..
: ., 2, 1, 0}的格式。比如，第一个到第三个是{0,0...,1,0}，{0,0...1,0,0}，{0,0..
: .2,1,0}.
: 这个序列的含义是左边有多少个数比当前的数大。
: 比如，给定一个排列 {3,2,1,4}, 那末对应的序列是{2,1,0,0}.
: 根据这种方法，对于一个随机数，可以在o(n)内产生对应的排列。
: 代码：
: 完整的代码在：
: http://code.google.com/p/sureinterview/source/browse/src/lib/combination/PermutationImpl.java
P*l
14 楼
这种方法还是可以处理重复的情况的，但是不方便。具体一点，假设有1 1 1 3 3 5.
可以先分组成abc=<1 1 1><3 3><5>，a=<111>,etc. c是1选1,b是三选２,a是６选3. 需
要进行两轮的取商取余。第一轮，在abc上。第二轮，在各自的组内对组合记数。最后
得到一个序列以后，再来计算排列。
应该有更好的方法。
【在 p********7 的大作中提到】
: 你没考虑有重复的情况比如 数据是 1，1，3，5
:
: ..
: ..
: http://code.google.com/p/sureinterview/source/browse/src/lib/combination/P
: ermutationImpl.java
可以先分组成abc=<1 1 1><3 3><5>，a=<111>,etc. c是1选1,b是三选２,a是６选3. 需
要进行两轮的取商取余。第一轮，在abc上。第二轮，在各自的组内对组合记数。最后
得到一个序列以后，再来计算排列。
应该有更好的方法。
【在 p********7 的大作中提到】
: 你没考虑有重复的情况比如 数据是 1，1，3，5
:
: ..
: ..
: http://code.google.com/p/sureinterview/source/browse/src/lib/combination/P
: ermutationImpl.java
c*h
15 楼
这题的trick在哪？我感觉就是把数组shuffle一下就好了吧
for (int i=size; i>1; i--)
swap(array, i-1, rnd.nextInt(i));
for (int i=size; i>1; i--)
swap(array, i-1, rnd.nextInt(i));
相关阅读
leetcode的run time error一道概率题马上onsite求bless发包子有人在香港签过H1b的工作签证吗？知道那里最快多久可以拿到护照？俺认识的几个越南人老美高技术工人3组织联合反烙印签证工 (转载)LCA processing time请教一个设计题(同求位大牛的blog)一起学习Coursera的算法Re: 问大家一个感受，关于放弃以前学的 (转载)twitter这种网站，实现起来的难点在哪？我怎么找不到问一个时间复杂度的问题，求教求教The 39 Most Important People In Cloud Computing (转载)apple的hardware design组on-site多久出结果啊G家 找工作面试常考哪些java的design patternBackground checkHR觉得要价高，现在加一轮面试看看是否适合下一个level的职位阿里巴巴投tango2亿求推荐palo alto附近的apartment！