# 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? – J. M. Feb 16 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. – N.J.Evans Feb 16 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}]]]]. – J. M. Feb 16 at 21:38
You guys know that answer's field is below? – Kuba Feb 16 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. – J. M. Feb 16 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? – Mr.Wizard Feb 16 at 22:42
@Mr.Wizard Nope. Perhaps they renamed/ghosted some Combinatorica functions to prevent name clashing? – Dr. belisarius Feb 16 at 22:54
Default Permutations[{1, 1, 0, 0}] works OK here too. – Mr.Wizard Feb 16 at 22:58
@Mr.Wizard Ok, thanks. Answer updated – Dr. belisarius Feb 16 at 23:05
This appeared to be most robust in different scenarious (in some general form that calculates the permutation lists). – garej Feb 17 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 :)) – garej Feb 16 at 21:28
Somehow, Tuples[] looks to me like it would consume more memory than Subsets[]... – J. M. Feb 16 at 21:30
@J.M. That's why I put a comment. – Kuba Feb 16 at 21:46
@J.M. added something more efficient – Kuba Feb 16 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}]. – J. M. Feb 16 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. :-) – Mr.Wizard Feb 17 at 13:25
@Mr.Wizard your thoughts always inspire me. You don't imagine how much I learn from you:-) – Algohi Feb 17 at 16:53