生成隨機矩陣，每個數字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

回答

相關問題