2
$\begingroup$

I need to calculate all $k$-possible subsets$(k:1,L)$ of matrix with size $L$. I am using subset function as following,

L = 10;
Do[
   t = L!/(k! (L - k)!);
   tstmat = RandomReal[L, {L, L}];
   config = Subsets[Range[Length@tstmat], {k}];
   Print[{k, t}]
   , 
   {k, 1, L}
];

this is working fine up to $L=24$, but for big sizes I am running into memory issues,

L | mem

25 | 2.152 G

26 | 3.600 G

27 | 6.470 G

28 | 12.418 G

29 | 23.641 G

I am assuming the huge memory is related to part of code where it's calculating the different subsets and keeps all of different configuration, for example for size L=30 and L=40 this becomes on the order of 10^9 and 10^12 sub-lists, respectively. Is there any way to decrease the memory, for example by keeping subsets once at a time? Or maybe is there any other function in Mathematica to calculate the all possible subsets?

$\endgroup$
  • $\begingroup$ @Arnoud Buzing: Do you need to store all these subsets, or can you perform your test or processing of them individually and reject (not store) elements that are not needed? $\endgroup$ – David G. Stork Apr 8 '15 at 19:06
  • $\begingroup$ See for example reference.wolfram.com/mathematica/Combinatorica/ref/… . But there are other questions on this site about this problem. Search for them! $\endgroup$ – Dr. belisarius Apr 8 '15 at 19:18
  • $\begingroup$ Hi Arnould, I don't need to store all the subsets but I need to do calculation on each element of subset where I construct the new sub-matrices with eliminating the rows and columns related to the each sub-list and calculate the determinant and move to the next subset. So in practice I need to calculate the det of number of matrices equal to the number of all subsets with max size(L!)/(k!*(L-k)!). $\endgroup$ – setareh Apr 8 '15 at 19:20
  • $\begingroup$ At the end of the Do loop config={Range @L}, the code seems not compute anything else on the sublists $\endgroup$ – penguin77 Apr 8 '15 at 20:26
  • $\begingroup$ @penguin77: I have not iclude that part of the code, but this is waht it looks like,Do[Prob1 = Det[tstmat[[#, #]]] & /@ Subsets[Range[Length@tstmat], {k}]; Sh1 = -Prob1.Log[Prob1] + Sh1, {k, 1, L}]; $\endgroup$ – setareh Apr 8 '15 at 21:19
1
$\begingroup$

I would suggest to take out of Do any evaluation that need to be done only once and make sure to clear variables between successive runs.

Clear[L, LL, k, config]
L = 50; LL = L!;  
Do[t = LL/(k! (L - k)!); Print[{k, t}], {k, 1, L}]

As an alternative for using Do you may consider

 {Range @ L, Table[k! (L - k)!, {k, 1, L}]  // L!/# &} // Thread

The result of config, when Do reaches end is

config=Subsets[Range[Length@RandomReal[L, {L, L}]],{L}]

therefore it can be calculated separately

$\endgroup$
  • $\begingroup$ Hi' Thanks for suggesting the method, I have run the method and using {Range @ L, Table[k! (L - k)!, {k, 1, L}] // L!/# &} // Thread, it actually increases the memory that we need, here is the new scaling [L=25, mem=4.84] compare it with the original scaling, I would say that the main part that it takes a lot of memory is subsets, I am looking for some function to avoid to keep all subset list in subset function and take each one and do some calculation(which I have not written in above code)and move to the next subset. $\endgroup$ – setareh Apr 8 '15 at 21:11
  • $\begingroup$ @setareh, you are right, I have noticed Subsets makes some troubles. Memory use for other code is minimal. Sorry did not first understand your intention for "real code" involving subsets. $\endgroup$ – penguin77 Apr 8 '15 at 22:12
1
$\begingroup$

This is a quick kludge to do what you're after. You'd probably want to properly modularize it for actual code use (i.e., not carrying around globals) or better yet incorporate the NextKSubset and your code into a Nest, NestList, Fold or FoldList as appropriate:

Block[{$ContextPath}, Needs["Combinatorica`"]];

fss[lst_, siz_] := (tmp1 = stop = Take[lst, siz]; 
   nss := (tmp = Combinatorica`NextKSubset[lst, tmp1]; tmp1 = tmp; 
     If[tmp === stop, {}, tmp]); tmp1);

Use:

(* get first subset of some range of some size *)
fss[Range@40,10]
(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} *)

(* get subsequent 10 subsets *)
Table[nss, {10}]
(*
{{1, 2, 3, 4, 5, 6, 7, 8, 9, 11}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 12}, {1,
   2, 3, 4, 5, 6, 7, 8, 9, 13}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 14}, {1, 
  2, 3, 4, 5, 6, 7, 8, 9, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 16}, {1, 2,
   3, 4, 5, 6, 7, 8, 9, 17}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 18}, {1, 2, 
  3, 4, 5, 6, 7, 8, 9, 19}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 20}}
*)

The use of the Block in setting up Combinatorica avoids clashes with built-ins, and necessitates the fully qualified name use.

$\endgroup$
  • $\begingroup$ thanks for the reply, I started to using the function you have defined, so this is psudo code for L=4 and k=2, so, Block[{$ContextPath}, Needs["Combinatorica"]]; L = 4; KSubsets[Range@L, 2] {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}} fss[lst_, siz_] := (tmp1 = stop = Take[lst, siz]; nss := (tmp = CombinatoricaNextKSubset[lst, tmp1]; tmp1 = tmp; If[tmp === stop, {}, tmp]); tmp1); tstmat = RandomInteger[L, {L, L}]; k = 2; t = L!/(k! (L - k)!); config = Table[nss, {5}] {{1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}} $\endgroup$ – setareh Apr 9 '15 at 3:21
  • $\begingroup$ I suppose this function will create a big list as k increases. So is there a way to just access the nth element of subsets, to keep the usage of memory as low as possible? For example I would like to access the first element {1,2} and build new matrix such as Prob1 = Det[tstmat[[#, #]]] & /@{1,2}+Prob1 and then move to the second element and similarly calculate Prob1 = Det[tstmat[[#, #]]] & /@{1,3}+Prob1 and so on .... $\endgroup$ – setareh Apr 9 '15 at 3:29
  • $\begingroup$ @setareh that is precisely what this does. One element of subsets at time. No intermediate lists are used. $\endgroup$ – ciao Apr 9 '15 at 3:40
1
$\begingroup$

Thanks all for replying and sharing comments for this post, considering all comments I came up with my own solution, see the code below,

    ClearAll[tsmat, lst, k, i, t, L, s];
    L = 20;
    tstmat = RandomInteger[L, {L, L}];
    lst = Range@L;
    Do[t = L!/(k! (L - k)!);
          Print[{k, t}];
      s = Range[k];
        Do[
       s = NextKSubset[lst, s], {i, 1, t}];
    , {k, 1, L}];

and here is new scaling for memory,

 L | mem
25 | 1.399 G
26 | 2.008 G
27 | 3.735 G
28 | 8.785 G

and the time scaling also is much faster than before(L=28,time=2 min!). But still I would like to decrease the memory as much as possible to run for bigger L. As a beginner in Mathematica I don't know that much of optimizing code, I would greatly appreciate any suggestion.

$\endgroup$
1
$\begingroup$

I finally found a better way using NthSubset function available in Combinatoria package, here is the code,

     << Combinatorica`;
Block[{$ContextPath}, Needs["Combinatorica`"]];                                                  ClearAll[tsmat, k, L, s, i];
L = 4;
tstmat = RandomInteger[L, {L, L}];
lst = Range@L;
Do[
 config = NthSubset[i, lst];
 Print[{i, config}], {i, 1, 2^L - 1}]                                                                             

The memory is dramatically lower than previous case, it almost stays around 703 MB up to size L=30!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.