6
$\begingroup$

Assume list is packed.

I expect Subsets[] is a structural operation because it depends on the number of elements, not on what the elements are. The output for Subsets[list] is ragged, and this is why it will not be packed. However, Subsets[list,{n}] does not have this problem. It seems to be a structural operation whose output is rectangular. Why is the output not packed? Moreover, Subsets[list,{n}] does not unpack (which can be determined using On["Packing"]).

The same can be asked about the related function Subsequences[list,{n}] whose output is not packed, and the output of IntegerPartitions[m,{n}] ($m>n$) is not packed as well.

Subsets[Range[10], {3}] // PackedArrayQ
Subsequences[Range[10], {3}] // PackedArrayQ
IntegerPartitions[10, {3}] // PackedArrayQ

(*False*)
(*False*)
(*False*)

On the other hand, the related functions Tuples[list,n] and Permutations[list,n] have packed outputs.

Moreover, it seems like there are many ways to make a program that does what Subsets[list,{n}] but with an output that is packed (nested loops, Map[], Table[], removing elements from Tuples[list,n] or from Permutations[list,{n}] all come to mind).

$\endgroup$
6
  • $\begingroup$ Just to clarify, I see two issues: Why is list unpacked? and, Why is the output not packed? The focus of the question seems to be on the second (that is, on the output). To my mind "to unpack" means to transform from packed to not packed and is an expensive operation. Unpacking does not happen in these three cases, so I take the question to be, Why is the output not generated as a packed array? $\endgroup$
    – Michael E2
    Aug 2, 2020 at 15:09
  • $\begingroup$ If f[list] is computed as Join @@ Table[f[list, {n}], {n, 0, Length@list}], then you wouldn't want them packed, since you would waste time unpacking them when joined. One might write a separate function for the special case with a different core routine, as you say, but perhaps they didn't want to. The internal workings and reasonings are probably only known (and perhaps now forgotten) by WRI developers. $\endgroup$
    – Michael E2
    Aug 2, 2020 at 15:34
  • $\begingroup$ @MichaelE2 Regarding your comment "Unpacking does not happen in these three cases...", perhaps I misunderstand you, but how is it possible for the input (list) to be packed, the output be not packed, and yet the input list is not unpacked by the operation? $\endgroup$ Aug 2, 2020 at 21:58
  • $\begingroup$ list is unpacked (at least by one of the commands, I forget which). Use On["Packing"] and execute your examples to see. As to how the input can be packed and the output not, try list = Range@5; Table[list[[k ;; k + 2]], {k, 1, Length@list - 2}] // DeveloperPackedArrayQ` (with the "Packing" messages on.). Then try it with list = Range@500. The output being packed or not has nothing to do with list be unpacked or not. $\endgroup$
    – Michael E2
    Aug 2, 2020 at 22:36
  • 3
    $\begingroup$ We're thinking of "unpacking" in two senses. There is a technical sense of "unpacking" used on this site and in the Developer`FromPackedArray::unpack message. It refers to transforming a packed array to the same array, but unpacked. The operation involves copying the data from a C-style array, to a List structure with pointers to expressions representing each number in the array. It seems that the question is, "Why is the output not packed?" My response, not an answer, was, "The internal workings and reasonings are probably only known (and perhaps now forgotten) by WRI developers." $\endgroup$
    – Michael E2
    Aug 3, 2020 at 1:11

1 Answer 1

4
$\begingroup$

I don't know why, but there is a workaround.

ClearAll[subsets];
subsets[n_Integer, k_Integer] :=
  Module[{res = GroupTheory`Tools`Multisets[Range[n - k + 1], k]},
   Statistics`Library`MatrixRowTranslate[res, Range[0, k - 1]];
   res
   ];

subsets[A_List, k_Integer] := Partition[A[[Flatten@subsets[Length@A, k]]], k];

Test cases

subsets[5, 2]

{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}

Developer`PackedArrayQ[%]

True

subsets[{"a", "b", "c", "d", "e"}, 3]

{{a,b,c},{a,b,d},{a,b,e},{a,c,d},{a,c,e},{a,d,e},{b,c,d},{b,c,e},{b,d,e},{c,d,e}}

r1 = subsets[26, 10]; // AbsoluteTiming
r2 = subsets[Range[26], 10]; // AbsoluteTiming
r3 = Subsets[Range[26], {10}]; // AbsoluteTiming
SameQ[r1, r2, r3]

{0.132365, Null}
{0.592547, Null}
{0.862341, Null}
True

You can also use GroupTheory`Tools`MultiSubsets, but it's not very efficient.

See also
https://mathematica.stackexchange.com/a/268721/2090

$\endgroup$

Your Answer

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

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