我想构造一个双射函数f(k, n, seed)从[1,n]到[1,n],其中1<=k<=n和1<=f(k, n, seed)<=n对每个给定的seed和n。函数实际上应该从1,2,...,n的随机排列返回一个值。随机性由seed决定。不同的seed可能对应于不同的排列。我希望f(k, n, seed)函数的时间复杂度对于每个1<=k<=n和任何给定的seed都是O(1)。
谁知道我怎么能构造这样的函数呢?随机性允许为伪随机性.n可以非常大(例如,>= 1e8)。
假设我有一个任意长度k的Python列表。现在,假设我想要一个n的随机样本,(其中n <= k!) 这个列表的不同的排列。我很想尝试:
import random
import itertools
k = 6
n = 10
mylist = list(range(0, k))
j = random.sample(list(itertools.permutations(mylist)), n)
for i in j:
print(i)
但是,自然地,当k变得太大时,这段代码变得非常慢。考虑到我可能正在寻找的n排列的数量相对于排列的总数相对较少,计算所有的排列是不必要的。然而,重
我知道以下PyTorch API可以对一维数组0、.、n-1执行全局随机洗牌
torch.randperm(n)
但是,我对如何快速生成随机排列感到困惑,这样杂乱数组中的每个元素都令人满意:
K = 10 # should be positive
shuffled_array = rand_perm_func(n, K) # a mysterious function
for i in range(n):
print(abs(shuffled_array[i] - i) < K) # should be True for each i
这意味着每个元素的移动距离小于K,是否
我在寻找一种随机采样所有排列的固定长度子集的方法。
import itertools
from random import shuffle
mylist = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R',
我有一个大小为n的输入流,我想生成一个大小为k的输出流,它包含输入流的不同随机元素,而不需要为样本选择的元素提供任何额外的内存。
我将要使用的算法基本上如下所示:
for each element in input stream
if random()<k/n
decrement k
output element
if k = 0
halt
end if
end if
decrement n
end for
函数random()在随机分布上从[0..1]生成一个数字,我相信算法
生成4x12个字母/空格网格:
每个模具应精确出现一次,位置随机选择。位置应该近似于骰子的均匀随机排列。显示每个模具的随机(同样,近似均匀)面。左对脸在三个字符窗口。例如,
A E A A
E C D E
D A Qu E
E A H D
是一个我想要的格式的非随机板。允许拖尾空间。
骰子:
A A E E G N
E L R T T Y
A O O T T W
A B B J O O
E H R T V W
C I M O T U
D I S T T Y
E I O S S T
D E
我有以下表格的数据框架:
1 2 3 4 5 6 7 8
A C C T G A T C
C A G T T A D N
Y F V H Q A F D
我需要随机选择一个列k倍,其中k是给定样本中的列数。我的程序创建了一个大小为k的空列表,然后随机地从dataframe中选择一个列来附加到列表中。每个列表必须是唯一的,不能有重复的。
从上面的示例dataframe来看,预期的输出应该如下所示:
[[2][4][6][1][7][3][5][8]]
然而,我所取得的结果如下:
[[1][1][3][6][7][8][8][2]]
做这件事最重要的方法是什么?以下是我的遗憾尝试:
k = le
我需要有效地插入一个5个字符的随机字符串到数据库中,同时也确保它是唯一的。生成随机字符串不是问题,但目前我要做的是生成字符串,然后检查数据库是否已经存在……如果是这样,我会从头开始。
有没有更有效的方法来完成这个过程?
请注意,我不想使用GUID或任何其他超过5个字符的内容...我必须坚持5个字符。
PS:我不认为这有什么不同,但我的字符串都区分大小写。
下面是"Random String“部分
Public Function GetRandomNumbers(ByVal numChars As Integer) As String
Dim chars As Strin
在向量p中,我有一个指数的总体w和相应的权重。我想从这个群体中得到k样本,而不需要替换,在这里,选择与随机权重成正比。
我知道可以用来进行替换选择
J = randsample(p,k,true,w)
但是当我用参数false而不是true调用它时,
??? Error using ==> randsample at 184
Weighted sampling without replacement is not supported.
我编写了我自己的函数
p = 1:n;
J = zeros(1,k);
for i = 1:k
J(i) = randsample(p,1,tru
我试图在neo4j中执行流导入,然后遇到内存不足错误(以及随后的崩溃),跟踪如下:
2016-06-05 03:51:35.218+0000 INFO o.n.k.i.t.l.p.LogPruningImpl日志旋转5:开始日志剪枝。2016-06-05 03:51:35.218+0000 INFO o.n.k.i.t.l.p.LogPruningImpl日志旋转5:日志修剪完成。2016-06-05 03:53:58.140+0000 INFO o.n.k.i.a.i.s.OnlineIndexSamplingJob抽样索引:节点(NodeId),平均大小为415290个唯一值,样本为41
我需要在范围k中随机选择0 to n-1元素。n可达10^9,而k可从1 to n-1起。我可以在O(n)时间内完成这一任务,只需对包含值0 to n-1的数组进行洗牌并从中选择第一个k元素即可。但是当k很小时,这种方法的时间和内存都是无效的。这个问题有O(k)解吗?
注意:选定的k数字必须是不同的。
我在想一个解决办法。有两种方法我能想到。让R是要返回的集合。
在范围内选择一个随机值并将其添加到R中。继续这样做,直到|R| = k。这个过程需要sum(n/i) for n+1-k <= i <= n时间和O(k)空间。
在数组中插入0到n-1,对其进行洗牌,从数组中获取第
我试图理解生成数组排列的算法的时间和空间复杂性。给定一个部分构建的排列,其中已经从k元素中选择了n元素,该算法从其余的n-k元素中选择元素k+1,并调用自己来选择其余的n-k-1元素:
public static List<List<Integer>> permutations(List<Integer> A) {
List<List<Integer>> result = new ArrayList<>();
permutations(A, 0, result);
return result;