生成随机矩阵，每个数字0..k

给定一个整数k，我正在寻找pythonic的方式来生成nxm矩阵（或嵌套列表），其中每个整数从0..k-1，但没有整数出现多次在每个行。生成随机矩阵，每个数字0..k

目前我正在做这样的事情

random.sample(list(combinations(xrange(k), m)), n)

，但这并不能保证从0..k-1每个数字包括，只是没有整数似乎比每排一次。而且这具有明显不合需要的组合复杂性。

谢谢。

来源

2014-08-31 tiao

代码是否需要缩短一行？ – ciechowoj 2014-08-31 16:31:03

你可能会给出一个例子你的输出应该是什么样子？即对于一个4x4的矩阵 – jrsm 2014-08-31 16:31:29

你不清楚你问什么，如果每行都包含所有数字，'k'，'m'和'n'之间的关系是什么？ – 2014-08-31 16:33:00

您想要生成一个随机的n*m矩阵整数1..k与每个使用的整数，并没有整数在任何行中使用两次。而且你想有效地做到这一点。

如果您只是想生成一个合理的答案，相当快，您可以通过随机选择元素并将其放入随机顺序来生成行。 numpy.random.random_sample和numpy.random.shuffle可以做到这一点。您将避免重复的元素问题。如果你不能使用所有的元素，那么你可以做的就是随机地将它“演化”为一个正确的解决方案，在每一步中，识别在矩阵中不止一次重复的所有元素，随机选择一个元素，并将其转换为一个尚未使用的整数，从1..k。这不会在行内造成重复，并且最多可以在步骤k中为您提供所需表单的矩阵。

可能性是，这是一个足够好的答案，你想要什么，而且是你应该做的。但它是不完美的 - 这种形式的矩阵并不全都以完全相等的概率发生。（特别是有很多元素只出现一次的情况会比他们应该显示的稍微多一点）。如果你需要一个完美均匀的分布，那么你将不得不做更多的工作。

为了达到那里你需要一点理论。如果你有这个理论，那么你可以把答案理解为：“动态编程解决方案转而寻找所有可能解决方案的计数，然后运行这个解决方案，做出随机决定以识别随机解决方案。”可能性是你没有那个理论。

我不打算详细解释这个理论。我只会概述你的工作。

你开始与琐碎的说法，“有n!/(n-m)!方式，我可以有1排满足使用k整数m我的条件的矩阵，其中没有使用更多。”

对于i从1..n，为j从m到k，你搞清楚在其中，你可以建立一个使用k整数ji行方式计数。您还要跟踪其中有多少种方式来自前一行的j以前的值。（稍后您将需要。）此步骤可以在双循环中完成。

请注意，您刚才为j=k和i=n生成的表格中的值是满足您所有条件的矩阵的数量。我们将自下而上地随机构建一个。

首先你为矩阵的最后一行生成一个随机的行 - 所有的行都是相同的。

对于每一行，直到您到达顶部，您使用您建立的表来随机决定您在最后一行中使用的元素将永远不会再次使用。随机决定哪些元素将是。从您仍在使用的整数中生成一个随机行。

当你到达最高层时，你会选择一个满足你的描述的随机矩阵，而不会产生任何偏见。

来源

2014-08-31 17:42:53 btilly

您是否尝试过使用numpy？使用numpy.random.shuffle这个简单的代码会给你包含整数0至仅一次K A随机列表：

import numpy as np 
import numpy.random as npr 

k = 7 # or whatever you like 
thisrow = np.arange(k) 
npr.shuffle(thisrow)

，你想获得一个矩阵可以重复此多次。

import numpy as np 
import numpy.random as npr 

k = 7 # row length 
m = 23 # number of rows 
mymatrix = np.zeros((m, k)) 

for i in range(m): 
    mymatrix[i] = np.arange(k) 
    npr.shuffle(mymatrix[i])

我同意上面CommuSoft你已经在你的问题尚未得以k，m和n之间的关系。包含随机顺序中的每个整数0..k-1的行恰好一次具有长度k。也许你给的例子没有给出范围内的所有整数，因为n<k？

来源

2014-08-31 17:08:40 morrna

请参阅我上面关于我认为问题所在的评论。如果该评论是正确的，那么你还没有成功解决它。 – btilly 2014-08-31 17:15:08

你是对的@btilly。底线是没有被问及具有足够特异性的问题。恭喜我猜想正确地猜测意图;这是你以前见过的应用程序吗？ – morrna 2014-08-31 17:58:58

没有涉及猜测。只有一组约束可以添加到所陈述的问题中，使其有意义，因此可以合理地假设应该添加该约束。请记住，有问题的人通常会正确地陈述自己的问题。他们并不总是包含他们思考过程中的一切。因此，最好假设有一些缺失，而不是以随机的方式解释所说的内容。 – btilly 2014-08-31 18:32:09

取每个数字1..k并将其分配给矩阵的某一行。

对于矩阵的每一行，填充间隙而不重复。随机播放每一行也保持随机性。

它看起来非常直接和高效。

编辑：

import random 

k = 10 
kset = set(range(k)) 
m = 4 
n = 5 

matrix = [] 
for i in range(m): 
    matrix.append(set()) 

for i in range(k): 
    matrix[random.randint(0,m-1)].add(i) 

for i in range(m): 
    presents = matrix[i] 
    newelements = random.sample(kset-presents, n-len(presents)) 
    matrix[i] = random.sample(matrix[i] | set(newelements), n)

来源

2014-08-31 20:07:47 MariusSiuram

以下的效率取决于k的相对值，n和m，但如果你知道n*m比k大得多，它可能是一样快，你会得到。它也具有简单的优点和缺偏压：

from functools import reduce 
from itertools import chain 
from operator import ior 
from random import sample 

def gen(k,m,n): 
    if m > k or k > m*n: 
    raise ValueError("Unsatisfiable constraint") 
    while True: 
    mat = [sample(range(k), m) for i in range(n)] 
    if reduce(ior, (1<<i for i in chain(*mat))) == (1<<k) - 1: 
     yield mat

发电机gen反复计算的长度m的n列表，其中每个成员列表由range(k)独特的元素的和，直到的所述n*m元素的列表组合列表包括range(k)的所有元素。一旦满足该约束条件，就会生成成功的矩阵，并在下一次迭代中继续循环。

可能需要生成大量候选矩阵才能找到满足约束条件的候选矩阵。一般来说，k和m的值很大。例如，对于k=10, n=4 and m=6，很少有必要生成两个以上的矩阵，并且通常第一个可以工作。但是，对于k=100, n=40, m=6，每成功一个就会丢弃数百个矩阵，而对于k=100, n=4, m=60，需要花费数万次才能找到一个兼容矩阵。

来源

2014-09-01 05:40:21 rici

生成随机矩阵，每个数字0..k

回答

相关问题