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?

Improve this question
$\endgroup$
7
  • $\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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 at 21:19

4 Answers 4

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Apr 9, 2015 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
    Commented Apr 9, 2015 at 3:29
  • $\begingroup$ @setareh that is precisely what this does. One element of subsets at time. No intermediate lists are used. $\endgroup$
    – ciao
    Commented Apr 9, 2015 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.

Improve this answer
$\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!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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