Introdução

Dobble / SpotIt é um jogo de cartas, no qual as pessoas precisam identificar o mesmo símbolo no par de cartas no menor tempo possível, indicá-lo e passar para o próximo par. Cada cartão possui vários símbolos (8 na versão normal), mas exatamente um é comum entre cada par de cartões.

Exemplo da cópia física do jogo:

Desafio

Escreva um programa cujo conjunto de símbolos (caracteres simples ASCII) e o número de símbolos no cartão único produzirão cartões de listagem de saída com símbolos para cada cartão. Obviamente, existem muitas combinações equivalentes, seu programa apenas precisa escrever qualquer combinação que produza a maior quantidade de cartões para determinada entrada.

É um código de golfe, então, quanto mais curto o código, melhor.

Também seria ótimo se a computação terminasse antes da morte por calor do universo, para os casos mais complicados.

Entrada

Dois argumentos para funcionar / stdin (sua escolha)

• O primeiro deles é a coleção de símbolos, algo como 'ABCDE "ou [' A ',' B ',' C ',' D ',' E '] - sua escolha de formato, seja string, conjunto, lista, fluxo ou o que for idiomático para o idioma de escolha. Os caracteres serão fornecidos no conjunto de [A-Za-z0-9], sem duplicatas (o tamanho máximo do conjunto de símbolos de entrada é 62). Eles não serão solicitados necessariamente em ( para que você possa obter "yX4i9A" também para caixa com 6 símbolos).

• O segundo argumento é inteiro, indicando a quantidade de símbolos no cartão único. Será menor que o tamanho do conjunto de símbolos.

Resultado

Imprima várias linhas separadas por novas linhas, cada uma delas contendo símbolos para um único cartão.

Exemplos

ABC
2
>>>>
AB
BC
AC

Ou

ABCDEFG
3
>>>>
ABC
BDE
CEF
BFG
AEG
CDG
ADF

Ou

ABCDE
4
>>>>
ABCD

Dicas

• O número de cartões produzidos não pode ser maior que a quantidade de símbolos distintos e, em muitas combinações, será consideravelmente menor
• Você pode ler alguns conhecimentos matemáticos se precisar de ajuda com o lado matemático do problema

Este é o meu primeiro desafio de golfe com código, por isso, perdoe possíveis problemas com formatação / estilo - tentarei corrigir erros se você os apontar nos comentários.

Python 2 , 192 162 bytes

Eu tenho um argumento de que isso produz o conjunto máximo de cartões para cada cenário e lida com os 3 casos de teste.

from itertools import*
def m(a,s):
    C=["".join(x)for x in combinations(a,s)]
    while len(C):
        print C[0]
        C=list(set(A for A in C if len(set(A)&set(C[0]))==1<s))

Experimente online!

Algoritmo

Dado um alfabeto ae um tamanho de cartão s, pegue todas as combinações de selementos ae chame-o C, então:

• Pegue o primeiro elemento de C, chame-oC0
• Salve  C0
• Remova todos os elementos Cque possuem uma união diferente C0de1
• Repita com o segundo elemento de C
• Continue até que Cesteja vazio

Em seguida, imprima os elementos salvos.

Argumento

Algum subconjunto não vazio de Cé a nossa solução máxima K,. Como ele contém pelo menos um elemento e quaisquer dois elementos são indistinguíveis, escolha um elemento arbitrário C0, Cpara estar K. Para qualquer elemento eno K, a cardinalidade da eunião xé 1 para x != edentro K; portanto, elimine todos os elementos Ccuja união com C0não possui cardinalidade 1. Pelo mesmo raciocínio, escolha um novo elemento arbitrário C, inclua-o Ke reduza-o C. Eventualmente, Cé o conjunto vazio e Kserá a solução máxima, porque em nenhum momento escolhemos um elemento que fosse distinguível de qualquer outro elemento.

Casos de teste

Esses casos de teste foram escritos antes que eu percebesse que a impressão era um requisito.

a=["a","b","c"]
b=2
c=3
d=m(a,b)
print d,len(d)==c
>> ['bc', 'ab', 'ac'] True

a=["a","b","c","d","e","f","g"]
b=3
c=7
d=m(a,b)
print d,len(d)==c
>> ['aef', 'abc', 'bde', 'ceg', 'adg', 'cdf', 'bfg'] True

a=["a","b","c","d","e"]
b=4
c=1
d=m(a,b)
print d,len(d)==c
>> ['abcd'] True

Atualizar

• +9 [16-12-07] Ajuste ao requisito de impressão
• -11 [16-12-07] Jogou fora minha Rvariável
• -30 [16-12-09] Jogou fora minha Kvariável, graças a @Leo !

Haskell, 175 156 bytes

Minha primeira tentativa no golfe, deixe-me saber se eu errei alguma coisa.

import Data.List
f 0_=[[]]
f n a=g$c n a
c n a=[a!!i:x|i<-[0..(length a)-1],x<-f(n-1)(drop(i+1)a)]
g[]=[]
g(x:t)=x:g(filter(\z->length(z`intersect`x)<= 1)t)

Experimente online!

Obrigado a @Paul Mutser pela melhoria e -19 bytes

Versão original

Perl 6 , 88 bytes

{+(combinations($^a,$^n),{my \d=.[0];say d.join;grep *∩d==1,.[1..*]}...!*)}

Experimente online!