Dado um conjunto de nelementos, o desafio é escrever uma função que lista todas as combinações de kelementos deste conjunto.

Exemplo

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

Exemplo

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

Regras (editadas)

• A ordem da saída é de sua escolha.
• A entrada pode ser qualquer tipo de dado. Mas a saída deve ser do mesmo tipo que a entrada. Se a entrada for uma lista de números inteiros, a saída também deverá ser uma lista de números inteiros. Se a entrada for uma string (matriz de caracteres), a saída também deverá ser uma string.
• O código deve funcionar com qualquer número de variáveis ​​de entrada.
• Você pode usar qualquer linguagem de programação.
• A resposta deve ser capaz de usar qualquer coisa (string, int, duplo ...) como entrada e saída também.
• Quaisquer funções integradas relacionadas a combinações e permutações são proibidas.
• O menor código vence (em termos de bytes).
• Desempate: votos.
• Duração: 1 semana.

PS Cuidado com as entradas extremas , como números negativos, 0, etc.

Haskell - 57 46 bytes

Vamos lá, golfscripters.

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

Caso de uso (a mesma função funciona polimorficamente):

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

3% "trapaça" ➔ ["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"]]

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)

A função fpega uma lista Se um número ke retorna uma lista de todas as sublistas de comprimento kde S. Em vez de listar todos os subconjuntos e, em seguida, filtrar por tamanho, só recebo os subconjuntos do tamanho necessário a cada etapa.

Eu gostaria de começar S.pop()a trabalhar para combinar ficar S[:1]com a passagem S[1:]mais tarde, mas parece consumir muito a lista.

Para impedir a objeção, qualquer solução Python quebra a regra de que "O código deve funcionar em qualquer número de variáveis ​​de entrada" por causa dos limites de recursão, observarei que a implementação do Stackless Python não tem limites de recursão (embora eu não tenha realmente testado este código).

Demonstração:

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

Mathematica 10, 70 caracteres

Apenas uma tradução da resposta de Haskell.

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

Uso:

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

Saída [1] = {{7, 1}, {4, 1}, {4, 7}}

Carvão , 23 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

    ²                   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

Python - 129

s é uma lista, k é o tamanho das combinações a serem produzidas.

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)

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]

Chame c para executar:

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

Ele obtém todas as permutações da lista se filtra aquelas com comprimento k.

Pyth , 28

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

Isto é (fortemente) baseado na resposta de Haskell.

Explicação:

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)

Nota: Embora a versão mais recente do Pyth, 1.0.9, tenha sido lançada hoje à noite e, portanto, não seja elegível para esse desafio, o mesmo código funciona bem no 1.0.8.

Haskell + Data.List , 44 bytes

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

Experimente online!

A resposta 46 byte é muito difícil de bater, mas se tiver tailsde Data.Listque você pode fazer 44 bytes.

05AB1E , 14 13 bytes

goLε¹ybRÏ}ʒgQ

Inspirado na resposta do @Neil 's Charcoal , certifique-se de votar nele!

Experimente online ou verifique mais alguns casos de teste .

Se builtins fossem permitidos, isso poderia ter sido de 2 bytes :

.Æ

Experimente online ou verifique mais alguns casos de teste .

Explicação:

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)

APL (NARS), 80 caracteres, 160 bytes

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

teste e como usá-lo:

  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│
└~─┘

a saída parece ok ... mas são possíveis erros ...

Na prática, ele retorna nulo definido como Zilde se a entrada alfa estiver fora da faixa; se alfa for 1, ele retornará todos os elementos em seu conjunto (está certo?);

Abaixo, parece um par de caracteres a menos, mas 2x mais lento acima:

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

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)

(<código fonte>) (['Bob', 'Sally', 'Jonah'], 2)

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

Loucura do método Array

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

C # (compilador interativo do Visual C #) , 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)

Infelizmente, o Tio / Mono parece não suportar a declaração genérica do tipo T , então sou forçado a perder alguns bytes com o tipo de objeto .

//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);

Experimente online!