Z*****Z
发帖数: 723 | 1 给一个数组和一个random number generator,写一个函数，返回这个数组的一个permut
ation, 要求任何可能的permutation都被等概率返回。
怎么做？ | m*****g
发帖数: 226 | 2 你这个rand gen 产生的数的范围跟数组大小一致贝 | Z*****Z
发帖数: 723 | 3 然后呢？
我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
permutation
只是这第i个permutation不太好直接做吧？
【在 m*****g 的大作中提到】
: 你这个rand gen 产生的数的范围跟数组大小一致贝
| l*****a
发帖数: 14598 | 4 next permutation
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
| h**6
发帖数: 4160 | 5 可以连续除以(N-1)!, (N-2)!, (N-3)!然后取商取余
i个
【在 Z*****Z 的大作中提到】
: 然后呢？
: 我的想法是，比如数组大小为N，random number i的范围应该是1到N！，然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧？
| x*****m
发帖数: 29 | | t**n
发帖数: 272 | 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
发帖数: 6 | 8 next_permutation + reservoir sampling (will handle the duplicate cases) | Z*****Z
发帖数: 723 | 9 哦，用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢？
【在 l******e 的大作中提到】
: next_permutation + reservoir sampling (will handle the duplicate cases)
| P*******b
发帖数: 1001 | 10 coask
【在 Z*****Z 的大作中提到】
: 哦，用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢？
| | | P********l
发帖数: 452 | 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不太好直接做吧？
| P********l
发帖数: 452 | | p********7
发帖数: 549 | 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
| P********l
发帖数: 452 | 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
| c*****h
发帖数: 166 | 15 这题的trick在哪？我感觉就是把数组shuffle一下就好了吧
for (int i=size; i>1; i--)
swap(array, i-1, rnd.nextInt(i)); |
|
