avatar
Z*Z
1
给一个数组和一个random number generator,写一个函数,返回这个数组的一个permut
ation, 要求任何可能的permutation都被等概率返回。
怎么做?
avatar
m*g
2
你这个rand gen 产生的数的范围跟数组大小一致贝
avatar
Z*Z
3
然后呢?
我的想法是,比如数组大小为N,random number i的范围应该是1到N!,然后返回第i个
permutation
只是这第i个permutation不太好直接做吧?

【在 m*****g 的大作中提到】
: 你这个rand gen 产生的数的范围跟数组大小一致贝
avatar
l*a
4
next permutation

i个

【在 Z*****Z 的大作中提到】
: 然后呢?
: 我的想法是,比如数组大小为N,random number i的范围应该是1到N!,然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧?

avatar
h*6
5
可以连续除以(N-1)!, (N-2)!, (N-3)!然后取商取余

i个

【在 Z*****Z 的大作中提到】
: 然后呢?
: 我的想法是,比如数组大小为N,random number i的范围应该是1到N!,然后返回第i个
: permutation
: 只是这第i个permutation不太好直接做吧?

avatar
x*m
6
参见著名的洗牌问题
avatar
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都被等概率返回。
: 怎么做?

avatar
l*e
8
next_permutation + reservoir sampling (will handle the duplicate cases)
avatar
Z*Z
9
哦,用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢?

【在 l******e 的大作中提到】
: next_permutation + reservoir sampling (will handle the duplicate cases)
avatar
P*b
10
coask

【在 Z*****Z 的大作中提到】
: 哦,用洗牌的办法我明白了。如何用reservoir sampling来对付重复呢?
avatar
P*l
11
你的想法是对的。但是实现起来还是优点麻烦。
如果一个数组的长度是n,那末,一共有n!种排列. 每种都可以写成基数{n, n-1, ..
., 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不太好直接做吧?

avatar
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-1, ..
: ., 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

avatar
P*l
14
这种方法还是可以处理重复的情况的,但是不方便。具体一点,假设有1 1 1 3 3 5.
可以先分组成abc=<1 1 1><3 3><5>,a=<111>,etc. c是1选1,b是三选2,a是6选3. 需
要进行两轮的取商取余。第一轮,在abc上。第二轮,在各自的组内对组合记数。最后
得到一个序列以后,再来计算排列。
应该有更好的方法。

【在 p********7 的大作中提到】
: 你没考虑有重复的情况比如 数据是 1,1,3,5
:
: ..
: ..
: http://code.google.com/p/sureinterview/source/browse/src/lib/combination/P
: ermutationImpl.java

avatar
c*h
15
这题的trick在哪?我感觉就是把数组shuffle一下就好了吧
for (int i=size; i>1; i--)
 swap(array, i-1, rnd.nextInt(i));
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。