Re: Re: random matrix from row and column sums
- To: mathgroup at smc.vnet.net
- Subject: [mg53609] Re: [mg53598] Re: random matrix from row and column sums
- From: DrBob <drbob at bigfoot.com>
- Date: Thu, 20 Jan 2005 03:47:50 -0500 (EST)
- References: <csinpt$njk$1@smc.vnet.net> <200501190700.CAA06903@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Random procedures that don't first identify ALL solutions can certainly be faster. This works well, for instance: Clear@randomFill randomFill[rowSums:{__Integer?Positive}, colSums:{__Integer?Positive}]:=Module[{r=Length@rowSums,c= Length@colSums,m,gaps,p,i,j}, m=Table[0,{r},{c}];zeroes=0m; While[(gaps=Table[Min[rowSums[[i]]-Tr@m[[i]], colSums[[j]]-Tr@m[[All,j]]],{i,r},{j,c}])!=zeroes, p=Position[gaps,_?Positive];{i,j}=p[[Random[Integer,{1,Length@p}]]]; m[[i,j]]+=Random[Integer,{1,gaps[[i,j]]}] ];m ] randomFill[{7,3,2,1},{2,9,2}] {{0,6,1},{2,1,0},{0,1,1},{0,1,0}} However, I don't think solutions are chosen with equal frequency, under any such scheme. For instance: Timing[f=Frequencies[Array[randomFill[Range@4,Range@4]&,{20000}]][[All,1]]] Through[{Length,Min,Max}@f] {36.734 Second,{103,204,45,72, 155,102,105,105,77,69,157,55,57,45,18,58,67,51,74,37,73,36,28, 71,143,96,60,55,91,110,97,100,49,73,127,40,26,82,74,18,41,67,31,44,56,43, 82,28,41,43,24,55,52,23,70,35,39,184,73,78,196,147,79,105,85,73,158,88, 30,50,144,77,113,53,94,62,36,67,85,82,116,28,43,115,93,34,55,93,98,94, 35,96,103,103,103,76,101,60,51,107,94,44,30,32,65,71,58,58,33,42,71,146, 62,125,120,83,171,58,30,53,49,25,54,57,23,60,44,39,67,36,65, 43,35,41,49,96,171,91,107,115,98,178,132,54,105,44,28,55,94,76,102,70,30, 48,80,155,80,39,58,47,34,111,64,72,139,117,57,76,130,75,91,110,70,101, 35,51,51,31,59,66,30,60,42,43,145,95,80,90,83,81,92,125,120,47,50,112,80, 41,59,64,39,67,67,43,91,127,42,48,121,87,43,65,91,47,67,67,54,107,116, 56,56,151,108,96,169,113,46,65,175,111,107,45,77,34,22,47,73,75,145, 119,75,58,112,158,115,33,30,107,73,36,42,73,32,54,58,35,90,190,88,73,182}} {261,18,204} #.# &[f - Mean@f]/Mean@f ChiSquarePValue[%,261] 50351983/10000 OneSidedPValue -> 0. Bobby On Wed, 19 Jan 2005 02:00:27 -0500 (EST), Paul Abbott <paul at physics.uwa.edu.au> wrote: > In article <csinpt$njk$1 at smc.vnet.net>, adiggle at agric.wa.gov.au wrote: > >> Is there an efficient method in Mathematica to generate random tables >> of nonnegative integers from a list of row sums and a list of column >> sums? >> >> For example for row sums of {7,3,2} and column sums of {2,9,1} the >> following two tables satisfy the constraints: >> >> {{2, 5, 0}, {0, 2, 1}, {0, 2, 0}} >> and >> >> {{1, 6, 0}, {1, 2, 0}, {0, 1, 1}} > > Here is one way to do this. The following module > > [1] constructs an arbitrary matrix of dimension implied by the row and > column sums (need not be square); > > [2] uses Reduce to apply the conditions that the entries are nonnegative > integers to determine all possible solutions; > > [3] turns this output into a list of replacement rules; and > > [4] returns a list of _all_ matrices satisfying the constraints. > > NonnegativeIntegerMatrices[rows_, cols_] := Module[ > {mat, r, c, a, vars, cond, red, m = Length[rows], n = Length[cols]}, > mat = Table[a[i, j], {i, m}, {j, n}]; > r = Thread[Plus @@ Transpose[mat] == rows]; > c = Thread[Plus @@ mat == cols]; > vars = Flatten[mat]; > cond = Thread[Flatten[mat] >= 0]; > red = {ToRules[Reduce[Join[r, c, cond], vars, Integers]]}; > If[red != {}, mat /. red, {}] > ] > > Once you have the complete list of solutions, say > > sols = NonnegativeIntegerMatrices[{7,3,2}, {2,9,1}] > > it is easy to select one at random > > sols[[ Random[Integer, {1, Length[sols]}] ]] > > However, this approach is not optimal if you have to work with large > numbers of different row and column sums. Also, computing all solutions > can be slow even for rather small matrices, e.g., try > > sols = NonnegativeIntegerMatrices[Range[4], Range[4]] > > In such cases a random search method will be more efficient -- and I'm > confident that other posters will help you here. > > Cheers, > Paul > -- DrBob at bigfoot.com www.eclecticdreams.net
- References:
- Re: random matrix from row and column sums
- From: Paul Abbott <paul@physics.uwa.edu.au>
- Re: random matrix from row and column sums