Problem with creating a large list of tuples

Question

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?

Answer 1

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}  *)