10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Although codegolf.stackexchange.com/questions/6380/… does have an additional restriction, its answers could be copied unchanged and would still be hard to beat. \$\endgroup\$ – Peter Taylor Jul 13 '14 at 22:06
  • 1
    \$\begingroup\$ By The input may be any type of data. do you mean any type of iterable data or an iterable filled with any type of data? e.g. is combos('ab', 1) -> ['a', 'b'] valid? \$\endgroup\$ – Calvin's Hobbies Jul 14 '14 at 0:58
  • 1
    \$\begingroup\$ What should the output be if the input is negative? \$\endgroup\$ – Ypnypn Jul 14 '14 at 1:40
  • 5
    \$\begingroup\$ I don't see how this question is a duplicate of "Generating combinations without recursion" when almost every answer so far uses recursion. \$\endgroup\$ – xnor Jul 14 '14 at 13:06
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Rainbolt Jul 16 '14 at 13:12

12 Answers 12

13
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks Mark, I didn't even consider making it infix. \$\endgroup\$ – ChaseC Jul 14 '14 at 7:51
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jul 17 '14 at 13:30
7
\$\begingroup\$

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 []
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 23 bytes

EΦEX²Lθ⮌↨ι²⁼ΣιηΦ…θLι§ιμ

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

    ²                   Literal 2
   X                    Raised to power
     L                  Length of
      θ                 Input array
  E                     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`
E                       Mapped to
                 θ      Input array
                …       Chopped to length
                  L     Length of
                   ι    Current base 2 value
               Φ        Filtered on
                     ι  Current base 2 value
                    §   Indexed by
                      μ Current index
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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←⍵}
\$\endgroup\$
1
\$\begingroup\$

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]))
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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