Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This question already has an answer here:

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 of input. If the input is a list of integers, the output should be a list of inputs as well. If the input is a string (array of characters), the output should be a string as well.
  • The code should work in any number of input variables.
  • Shortest code wins (in terms of bytes).
  • 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.
  • Tiebreaker: votes.
  • Duration: 1 week.

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

share|improve this question

marked as duplicate by Peter Taylor, Ventero, Kyle Kanos, Manu, user80551 Jul 14 at 9:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
How should input and output be done? (STDIN, function args, etc) –  Ypnypn Jul 13 at 21:58
1  
Although codegolf.stackexchange.com/questions/6380/… does have an additional restriction, its answers could be copied unchanged and would still be hard to beat. –  Peter Taylor Jul 13 at 22:06
1  
What should the output be if the input is negative? –  Ypnypn Jul 14 at 1:40
3  
I don't see how this question is a duplicate of "Generating combinations without recursion" when almost every answer so far uses recursion. –  xnor Jul 14 at 13:06
1  
The removal of a restriction is not a significant change. Also, using existing answers to determine what is or is not a duplicate is not a good idea, because you would be unable to identify duplicates until they were already answered. Sometimes you just have to use your head. –  Rainbolt Jul 16 at 13:12

7 Answers 7

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"]]

share|improve this answer
1  
Thanks Mark, I didn't even consider making it infix. –  ChaseC Jul 14 at 7:51
    
Incidentally, what does "bring it on" mean in your dialect? In mine it implies a challenge, but that doesn't make sense in context because your final version is still longer than my initial version in the question this duplicates. –  Peter Taylor Jul 17 at 13:30

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 []
share|improve this answer

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.

share|improve this answer

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]))
share|improve this answer

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)
share|improve this answer

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.

share|improve this answer

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}}

share|improve this answer

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