# How can I get every distinct size-n combination of a list?

Let's say I have a list:

{a, b, c}


I would like to, for say $n=2$ get every distinct pair from that list. That is, the expected result should be, for some function choose:

choose[{a, b, c}, 2]
(* {{a, b}, {a, c}, {b, c}} *)


My attempt at this was like so:

choose[list_, n_] :=
DeleteDuplicates[Permutations[list, {n}], Union[#1, #2] == #1 &]


And it does give the expected result for this example. There are, however, some problems in which I would like some help addressing:

1. Permutations creates more combinations that I need, which forces me to use DeleteDuplicates. Is there away to directly arrive at all combinations?
2. The DeleteDuplicates operation is very costly. Is there a way I could use the structure of the Permutations result to my advantage to get rid of the unwanted repeats?
3. My function DOES make an error when there are supposed to be intended repeats. For instance, choose[{b, b, c}, 2] should give {{b,b}, {b, c}, {c, b}} - as every element in the list is considered "distinct" even though the values could be equal - but instead, the duplicate deletion removes the {c, b}.

EDIT I have figured out a way to address #3. If I create a symbolic list tempList in which every element is unique, then replace that with the list, I am able to preserve "distinct" combinations even though they have the same value:

choose[list_, n_] :=
With[{tempList = Array[Unique[] &, Length@list]},
DeleteDuplicates[
Permutations[tempList, {n}],
Union[#1, #2] == #1 &] /. Thread[tempList -> list]]


However, there's still room for improvement as having to use the replacement is not great for larger list lengths and values of $n$.

-
Possible duplicate: (1) and Related: (2). – Mr.Wizard Jan 4 '13 at 22:10
@Mr.Wizard I expected there to be answers with the same results for different questions, but my approach to what I was looking for was different than what the authors of those linked questions had (that's why I couldn't find those questions before I posted). Users who are need of this function (which they don't know exists, like in this case) are more likely to find it if their interpretation of what they need is similar to mine. – VF1 Jan 5 '13 at 0:07
(cont.) In other words, when they search "choose combinations from a list" or something along those lines, this will come up. – VF1 Jan 5 '13 at 0:13
You will notice that I didn't Close this question, and furthermore I would not Delete it if I (or someone else) had. Frankly I'm considering closing #3461 in favor of this one as I think it's much more likely to be found. The second linked question is not a duplicate; I should have instead said Related: (I'll fix that now.) – Mr.Wizard Jan 5 '13 at 18:14
@Mr.Wizard gotcha, I wasn't trying to be too defensive. – VF1 Jan 22 '13 at 21:02

I think there is a built-in function for what you need:

Subsets[{a, b, c, d}, {2}]

-
Ah! Exactly what I was looking for! Thanks. – VF1 Jan 4 '13 at 7:28

Some of the points in the question were never well addressed.

1. Permutations creates more combinations that I need, which forces me to use DeleteDuplicates. Is there away to directly arrive at all combinations?
2. The DeleteDuplicates operation is very costly. Is there a way I could use the structure of the Permutations result to my advantage to get rid of the unwanted repeats?

Permutations is "smart" enough not to produce needless duplicates if you ask it for the right thing: it recognizes identical elements as such and does not produce repetitious output. Therefore your mask may be had with:

Permutations[{1, 1, 0}]

{{1, 1, 0}, {1, 0, 1}, {0, 1, 1}}


And applied with Pick:

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

{{a, b}, {a, c}, {b, c}}


This method inherently addresses point #3 as well.

-
+1, this is very nice. – nickjamesuk Aug 7 '13 at 11:39