# Efficient way to make subsets of list with placeholders

I have an arbitrary list of unique elements:

lst = {a, b, c, d}


Documentation allows finding subsets with same number of elements, say 2:

Subsets[lst, {2}]
(* {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}} *)


What I need is to add some placeholder, i.e. 0, to each subset.

{{a, b, 0, 0}, {a, 0, c, 0}, {a, 0, 0, d}, {0, b, c, 0}, {0, b, 0, d}, {0, 0, c, d}}

Replacements work slow (even freeze) for large lists and many subsets.

lst /. # & /@ (Thread[# -> 0] & /@ Complement[list, #] & /@ Subsets[lst, {2}])


I'd like to have a better way.

(Application - intertemporal choice problems with discrete time).

• So, ReplacePart[ConstantArray[0, Length[lst]], Thread[# -> lst[[#]]]] & /@ Subsets[Range[Length[lst]], {2}] doesn't work for you? Commented Feb 16, 2016 at 21:23
• Another option Normal@SparseArray[ MapThread[First@Position[lst, #] -> # &, Transpose@{#}] , Length@lst ] & /@ Subsets[lst, {2}], pretty similar to J.M.'s solution, but you can keep it in sparse form to save some memory for large lists. i.e. remove Normal if you want. Commented Feb 16, 2016 at 21:27
• Another way to do @N.J.'s idea: SparseArray[Flatten[MapIndexed[Map[Function[k, Append[#2, k] -> lst[[k]]], #1] &, Subsets[Range[Length[lst]], {2}]]]]. Commented Feb 16, 2016 at 21:38
• You guys know that answer's field is below?
– Kuba
Commented Feb 16, 2016 at 21:49
• @Kuba, I wanted the OP to test the damn things first before committing to an answer. "Replacements work slow (even freeze) for large lists" made me ask if the replacement-based method I gave would also be inappropriate. Commented Feb 16, 2016 at 21:53

{a, b, c, d} # & /@ Permutations[{1, 1, 0, 0}]


Or

<< Combinatorica

{a, b, c, d} # & /@ CombinatoricaPermutations[{1, 1, 0, 0}]
(*{{a, b, 0, 0}, {a, 0, c, 0}, {a, 0, 0, d}, {0, b, c, 0}, {0, b, 0, d}, {0, 0, c, d}}*)

• CombinatoricaPermutations[{1, 1, 0, 0}] is not working here, in 10.2 -- can you think of a reason I'm forgetting? Commented Feb 16, 2016 at 22:42
• @Mr.Wizard Nope. Perhaps they renamed/ghosted some Combinatorica functions to prevent name clashing? Commented Feb 16, 2016 at 22:54
• Default Permutations[{1, 1, 0, 0}] works OK here too. Commented Feb 16, 2016 at 22:58
• @Mr.Wizard Ok, thanks. Answer updated Commented Feb 16, 2016 at 23:05
• This appeared to be most robust in different scenarious (in some general form that calculates the permutation lists). Commented Feb 17, 2016 at 13:18

Not the smartest, but working:

GroupBy[
Count[0]
][2] (*here 2 is length @ lst - 2*)

{{a, b, 0, 0}, {a, 0, c, 0}, {a, 0, 0, d}, {0, b, c, 0}, {0, b, 0, d}, {0, 0, c, d}}


or

Function[lst,
ReplacePart[0 lst, #] & /@ MapThread[
Rule, Subsets[#, {2}] & /@ {Range@Length@lst, lst}, 2
]
]


The second method is 2000x times and MaxMemoryUsed is around 150KB in comparison to 500MB of the first one.

• looks good, and smart :)) Commented Feb 16, 2016 at 21:28
• Somehow, Tuples[] looks to me like it would consume more memory than Subsets[]... Commented Feb 16, 2016 at 21:30
• @J.M. That's why I put a comment.
– Kuba
Commented Feb 16, 2016 at 21:46
• @J.M. added something more efficient
– Kuba
Commented Feb 16, 2016 at 22:14
Normal@({a, b, c, d} SparseArray[ # -> 1 & /@ #, 4]) & /@
Subsets[Range[4], {2}]


{{a, b, 0, 0}, {a, 0, c, 0}, {a, 0, 0, d}, {0, b, c, 0}, {0, b, 0, d}, {0, 0, c, d}}

• Normal @ ({a, b, c, d} SparseArray[Thread[# -> 1], 4]) & /@ Subsets[Range[4], {2}] is equivalent. Another possibility is Normal @ SparseArray[Thread[# -> {a, b, c, d}[[#]]], 4] & /@ Subsets[Range[4], {2}]. Commented Feb 16, 2016 at 22:20

Taking the idea from Mr.Wizard answer

rules = Join[Thread[# -> #], {_ -> 0}] & /@ Subsets[lst, {2}];
Replace[lst, #, 1] & /@ rules


Or

Lookup[Thread[#->#],lst,0]&/@Subsets[lst,{2}]
`
• I wouldn't have thought to use this method here. +1 for expanding my thinking. :-) Commented Feb 17, 2016 at 13:25
• @Mr.Wizard your thoughts always inspire me. You don't imagine how much I learn from you:-) Commented Feb 17, 2016 at 16:53