List the combinations of elements in a set

Question

Given a set of n elements, the challenge is to write a function who lists all the combinations of k elements of in this set.

Example

Set: [1, 7, 4]
Input: 2
Output: [1,7], [1,4], [7,4]

Example

Set: ["Charlie", "Alice", "Daniel", "Bob"]
Input: 2
Output ["Daniel", "Bob"], ["Charlie", "Alice"], ["Alice", "Daniel"], ["Charlie", "Daniel"], ["Alice", "Bob"], ["Charlie",  "Bob"]

Rules (Edited)

• The order of the output is of your choice.
• The input may be any type of data. But the output should be the same type as the input. If the input is a list of integers, the output should be a list of integers as well. If the input is a string (array of characters), the output should be a string as well.
• The code should work with any number of input variables.
• You can use any programming language.
• The answer should be able to use anything (string, int, double...) as input and output as well.
• Any built-in functions that is related to combinations and permutations are forbidden.
• Shortest code wins (in terms of bytes).
• Tiebreaker: votes.
• Duration: 1 week.

P.S. Be careful about the extreme inputs such as negative numbers, 0, etc.

Answer 1

Haskell - 57 46 bytes

Bring it on, golfscripters.

0%_=[[]]
n%(x:y)=map(x:)((n-1)%y)++n%y
_%_=[]

Use case (same function works polymorphicaly):

2%[1,2,3,4] ➔ [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

3%"cheat" ➔ ["che","cha","cht","cea","cet","cat","hea","het","hat","eat"]

2%["Charlie", "Alice", "Daniel", "Bob"] ➔ [["Charlie","Alice"],["Charlie","Daniel"],["Charlie","Bob"],["Alice","Daniel"],["Alice","Bob"],["Daniel","Bob"]]

Answer 2

Python (72)

f=lambda S,k:S and[T+S[:1]for T in f(S[1:],k-1)]+f(S[1:],k)or[[]]*(k==0)

The function f takes a list S and number k and returns a list of all sublists of length k of S. Rather than listing all subsets and then filtering by size, I only get the subsets of the needed size at each step.

I'd like to get S.pop() to work in order to combine getting S[:1] with passing S[1:] later, but it seems to consume the list too much.

To preempt the objection any such Python solution breaks the rule that "The code should work in any number of input variables" because of recursion limits, I'll note that the Stackless Python implementation has no recursion limits (though I haven't actually tested this code with it).

Demonstration:

S = [1, 2, 6, 8]
for i in range(-1,6):print(i, f(S,i))

#Output:    
-1 []
0 [[]]
1 [[1], [2], [6], [8]]
2 [[2, 1], [6, 1], [8, 1], [6, 2], [8, 2], [8, 6]]
3 [[6, 2, 1], [8, 2, 1], [8, 6, 1], [8, 6, 2]]
4 [[8, 6, 2, 1]]
5 []

Answer 3

Mathematica 10, 70 chars

Just a translation of the Haskell answer.

_~f~_={};_~f~0={{}};{x_,y___}~f~n_:=Join[Append@x/@f[{y},n-1],{y}~f~n]

Usage:

In[1]:= f[{1, 7, 4}, 2]

Out[1]= {{7, 1}, {4, 1}, {4, 7}}

Answer 4

Haskell + Data.List, 44 bytes

0%_=[[]]
n%y=do{a:b<-tails y;(a:)<$>(n-1)%b}

Try it online!

---

The 46 byte answer is pretty hard to beat but if you have tails from Data.List you can do 44 bytes.

Answer 5

Charcoal, 23 bytes

ＥΦＥＸ²Ｌθ⮌↨ι²⁼ΣιηΦ…θＬι§ιμ

Try it online! Link is to verbose version of code. Explanation:

    ²                   Literal 2
   Ｘ                    Raised to power
     Ｌ                  Length of
      θ                 Input array
  Ｅ                     Mapped over implicit range
         ι              Current index
        ↨               Converted to base
          ²             Literal 2
       ⮌                Reversed
 Φ                      Filtered on
            Σ           Digital sum of
             ι          Current base 2 value
           ⁼            Equal to
              η         Input `k`
Ｅ                       Mapped to
                 θ      Input array
                …       Chopped to length
                  Ｌ     Length of
                   ι    Current base 2 value
               Φ        Filtered on
                     ι  Current base 2 value
                    §   Indexed by
                      μ Current index

Answer 6

Python - 129

s is a list, k is the size of the combinations to produce.

def c(s, k):
    if k < 0: return []
    if len(s) == k: return [s]
    return list(map(lambda x: [s[0]]+x, c(s[1:], k-1))) + c(s[1:], k)

Answer 7

Python, 102

p=lambda s:p(s[1:])+[x+[s[0]]for x in p(s[1:])]if s else[s];c=lambda s,k:[x for x in p(s)if len(x)==k]

Call c to run:

c([5, 6, 7], 2) => [[6, 7], [5, 7], [5, 6]]

It gets all the permutations of the list s and filters the ones with length k.

Answer 8

Pyth, 28

DcGHR?+m+]'HdctGtHcGtHH*]Y!G

This is (heavily) based on the Haskell answer.

Explanation:

DcGH                           def c(G,H):
    R                          return
     ?                         Python's short circuiting _ if _ else _
       m+]'Hd                  map to [head(H)]+d
             ctGtH             c(G-1,tail(H))
       m+]'HdctGtH             map [head(H)]+d for d in c(tail(G),tail(H))
      +m+]'HdctGtHcGtH         (the above) + c(G,tail(H))
     ?                H        (the above) if H else (the below)
                       *]Y!G   [[]]*(not G)
     
     

Note: While the most recent version of Pyth, 1.0.9, was released tonight, and is therefore ineligible for this challenge, the same code works fine in 1.0.8.

Answer 9

05AB1E, 14 13 bytes

goLε¹ybRÏ}ʒgQ

Inspired by @Neil's Charcoal answer, so make sure to upvote him!

Try it online or verify a few more test cases.

If builtins were allowed this could have been 2 bytes:

.Æ

Try it online or verify a few more test cases.

Explanation:

g              # Get the length of the first (implicit) input-list
 o             # Take 2 to the power this length
  L            # Create a list in the range [1, 2**length]
   ε           # Map each integer `y` to:
    ¹          #  Push the first input-list again
     ybR       #  Convert integer `y` to binary, and reverse it
        Ï      #  And only keep values at truthy indices of `y` (so where the bit is a 1)
         }ʒ    # After the map: filter the list of lists by:
           g   #  Where the length of the inner list
            Q  #  Is equal to the (implicit) input-integer
               # (then the result is output implicitly)

.Æ             # Get all `b`-element combinations in list `a`,
               # where `b` is the first (implicit) input-integer,
               # and `a` is the second (implicit) input-list
               # (then the result is output implicitly)

Answer 10

APL(NARS), 80 chars, 160 bytes

{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

test and how to use it:

  f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
  o←⎕fmt
  o 5 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o 4 f 1 2 3 4 
┌1─────────┐
│┌4───────┐│
││ 1 2 3 4││
│└~───────┘2
└∊─────────┘
  o 3 f 1 2 3 4
┌4──────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 1 2 3│ │ 1 2 4│ │ 1 3 4│ │ 2 3 4││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊──────────────────────────────────┘
  o 2 f 1 2 3 4
┌6────────────────────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 2│ │ 1 3│ │ 1 4│ │ 2 3│ │ 2 4│ │ 3 4││
│└~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘2
└∊────────────────────────────────────────┘
  o 1 f 1 2 3 4
┌4──────────────────┐
│┌1─┐ ┌1─┐ ┌1─┐ ┌1─┐│
││ 1│ │ 2│ │ 3│ │ 4││
│└~─┘ └~─┘ └~─┘ └~─┘2
└∊──────────────────┘
  o 0 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o ¯1 f 1 2 3 4
┌0─┐
│ 0│
└~─┘
  o 3 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌4────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌3────────────────────┐ ┌3────────────────────┐ ┌3─────────────────────┐ ┌3─────────────────────┐│
││┌2───┐ ┌2───┐ ┌2────┐│ │┌2───┐ ┌2───┐ ┌2────┐│ │┌2───┐ ┌2────┐ ┌2────┐│ │┌2───┐ ┌2────┐ ┌2────┐││
│││ 0 0│ │ 1 2│ │ 3 ¯4││ ││ 0 0│ │ 1 2│ │ 4 ¯5││ ││ 0 0│ │ 3 ¯4│ │ 4 ¯5││ ││ 1 2│ │ 3 ¯4│ │ 4 ¯5│││
││└~───┘ └~───┘ └~────┘2 │└~───┘ └~───┘ └~────┘2 │└~───┘ └~────┘ └~────┘2 │└~───┘ └~────┘ └~────┘2│
│└∊────────────────────┘ └∊────────────────────┘ └∊─────────────────────┘ └∊─────────────────────┘3
└∊────────────────────────────────────────────────────────────────────────────────────────────────┘
  o 4 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌1──────────────────────────────┐
│┌4────────────────────────────┐│
││┌2───┐ ┌2───┐ ┌2────┐ ┌2────┐││
│││ 0 0│ │ 1 2│ │ 3 ¯4│ │ 4 ¯5│││
││└~───┘ └~───┘ └~────┘ └~────┘2│
│└∊────────────────────────────┘3
└∊──────────────────────────────┘
  o 1 f (0 0)(1 2)(3 ¯4)(4 ¯5)
┌4────────────────────────────────────┐
│┌1─────┐ ┌1─────┐ ┌1──────┐ ┌1──────┐│
││┌2───┐│ │┌2───┐│ │┌2────┐│ │┌2────┐││
│││ 0 0││ ││ 1 2││ ││ 3 ¯4││ ││ 4 ¯5│││
││└~───┘2 │└~───┘2 │└~────┘2 │└~────┘2│
│└∊─────┘ └∊─────┘ └∊──────┘ └∊──────┘3
└∊────────────────────────────────────┘
  o 2 f ('Charli')('Alice')('Daniel')('Bob')
┌6──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────────────────┐ ┌2──────────────────┐ ┌2───────────────┐ ┌2─────────────────┐ ┌2──────────────┐ ┌2───────────────┐│
││┌6──────┐ ┌5─────┐│ │┌6──────┐ ┌6──────┐│ │┌6──────┐ ┌3───┐│ │┌5─────┐ ┌6──────┐│ │┌5─────┐ ┌3───┐│ │┌6──────┐ ┌3───┐││
│││ Charli│ │ Alice││ ││ Charli│ │ Daniel││ ││ Charli│ │ Bob││ ││ Alice│ │ Daniel││ ││ Alice│ │ Bob││ ││ Daniel│ │ Bob│││
││└───────┘ └──────┘2 │└───────┘ └───────┘2 │└───────┘ └────┘2 │└──────┘ └───────┘2 │└──────┘ └────┘2 │└───────┘ └────┘2│
│└∊─────────────────┘ └∊──────────────────┘ └∊───────────────┘ └∊─────────────────┘ └∊──────────────┘ └∊───────────────┘3
└∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
  o ¯2 f ('Charli')('Alice')('Daniel')('Bob')
┌0─┐
│ 0│
└~─┘

the output seems ok... but bug are possible...

In practice it return void set as Zilde if input alpha out of range; if alpha is 1 it return the elements all one in its set (is it right?);

This below it seems a couple of char less but 2x slower above:

f←{(⍺>≢⍵)∨⍺≤0:⍬⋄1=⍺:,¨⍵⋄{w[⍵]}¨k/⍨{∧/</¨¯1↓{⍵,¨1⌽⍵}⍵}¨k←,⍳⍺⍴≢w←⍵}

Answer 11

JS - 117 188

(a,b,c=[])=>((d=(e,f,g=[])=>f*e?g.push(e)+d(e-1,f-1,g)+g.pop
()+d(e-1,f,g):f||c.push(g.map(b=>a[b-1])))(a.length,b),c)

(<source code>)(['Bob','Sally','Jonah'], 2)

     [['Jonah','Sally']['Jonah','Bob']['Sally','Bob']]

Array method madness

combination = (arr, k) =>
    Array
        .apply(0, { length: Math.pow(k+1, arr.length) })
        .map(Number.call, Number)
        .map(a => a
              .toString(arr.length)
              .split('')
              .sort()
              .filter((a, b, c) => c.indexOf(a) == b)
              .join(''))
        .filter((a, b, c) => a.length == k && c.indexOf(a) == b)
        .map(x => x.split('').map(y => arr[+y]))

Answer 12

C# (Visual C# Interactive Compiler), 141 bytes

l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new object[][]{new object[]{}};B=(n,l)=>A(l).Where(x=>x.Count()==n)

Sadly, Tio/Mono doesn't seem to support generic type T declaration, so I'm forced to lose a few bytes with the object type instead.

//returns a list of all the subsets of a list
A=l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new object[][]{new object[]{}};

//return the subsets of the required size
B=(n,l)=>A(l).Where(x=>x.Count()==n);

Try it online!