# Problem with creating a large list of tuples

This is a follow-up question from Sum of Multinomial Coefficients

I have thought about the meaning of the formula I mentioned and, with help, I implemented the following code:

supp[vec_] := Module[{support = {}, i},
Do[If[vec[[i]] != 0, AppendTo[support, i]], {i, 1, Length[vec]}];
support
];

calctrafo[n_, func_] := Module[{vecs, trafo = 0, i},
vecs = Tuples[Range[0, (n - 1)], n];
vecs = Select[vecs, Total[#] == (n - 1) &];
Do[trafo += (Multinomial @@ vecs[[i]])*func[supp[vecs[[i]]]], {i, 1, Length[vecs]}];
trafo
];

calctrafo[7, func]


The function supp gives me the support of the lists and func is a arbitrary function. This code works well for me, but I need the code to work for large n, n >= 100. The problem lies in the function Tuples, which crashes for n > 6. Is there a way to make this work for large n?

• As I understand you the problem is that your very large result list from tuples will not fit in memory. If that is the case, you could perhaps use an iterative approach and something like mathematica.stackexchange.com/questions/9554/… Mar 1, 2013 at 8:43
• @jVincent Thanks for the Link. But do I miss something, because I tried the first code in your answer but that it did not work. Mar 2, 2013 at 9:29
• There was a syntax change in the length test. You should be able to run it now. Mar 4, 2013 at 8:48
• Thanks! I edited my code and tried to create the tuples "on the fly" but for let's say for Tuples[Range[0,20],19] I loop through all possible Tuples. But there are approx. 19^20 Tuples and mathematica can't handle such a large number. Is there any other way? Mar 5, 2013 at 8:06
• Yes. If you go from the code in that question you could simply do allmyTuples=lazyTuples[Range@20,19]; which will not actually calculate them all yet, then if you call for instance allmyTuples[[21312312841789283727]] it will return only that one tuple, without having calculated all the others. If you want to iteraet over the tuples, the length can be found by calling Length[allmyTuples]. Mar 5, 2013 at 9:12

Instead of creating a list of all tuples and then selecting those whose total is n-1, you could start with the IntegerPartitions of n-1, pad them to length n with zeroes, and create all the permutations:

getvecs[n_] := Flatten[Permutations[PadRight[#, n]] & /@ IntegerPartitions[n - 1], 1]


I would also suggest using Position for the support function:

supp2[vec_] := Flatten @ Position[Unitize @ vec, 1]


and replacing the Do loop with Dot:

calctrafo2[n_, func_] := With[{vecs = getvecs[n]},
(Multinomial @@@ vecs).(func[supp2[#]] & /@ vecs)]


This is considerably faster:

Timing[calctrafo[7, Total]]
(*  {4.375, 1987804}  *)

Timing[calctrafo2[7, Total]]
(*  {0.031, 1987804}  *)

• Nice work! (But you don't need me to tell you that, do you.) Mar 1, 2013 at 10:40
• Good point @Mr.Wizard. Oh, and congratulations on passing 50k! Mar 1, 2013 at 20:14
• Thank you. Truly nice performance improvement! For the code to work for large n, I think I need to think about an iterative approach Mar 2, 2013 at 9:31