Introducción

Dobble / SpotIt es un juego de cartas, donde las personas deben detectar el mismo símbolo en un par de cartas en el menor tiempo posible, indicarlo y pasar al siguiente par. Cada tarjeta tiene múltiples símbolos (8 en la versión normal), pero exactamente uno es común entre cada par de tarjetas.

Ejemplo de copia física del juego:

Desafío

Escriba un programa, que dado el conjunto de símbolos (caracteres ascii individuales) y el número de símbolos en una sola tarjeta producirá tarjetas de listado de salida con símbolos para cada tarjeta. Obviamente, hay muchas combinaciones equivalentes, su programa solo tiene que escribir cualquiera de las combinaciones que produzca la mayor cantidad de tarjetas para la entrada dada.

Es un código de golf, así que más corto el código, mejor.

También sería genial si el cálculo terminara antes de la muerte por calor del universo para el caso más complicado.

Entrada

Dos argumentos para funcionar / stdin (su elección)

• El primero de ellos es la colección de símbolos, algo así como 'ABCDE "o [' A ',' B ',' C ',' D ',' E ']: su elección de formato, ya sea cadena, conjunto, lista, secuencia , o lo que sea idiomático para el idioma de elección. Los caracteres se darán del conjunto de [A-Za-z0-9], sin duplicados (por lo que el tamaño máximo del conjunto de símbolos de entrada es 62). No se ordenarán necesariamente en ( para que pueda obtener "yX4i9A" también para el caso de 6 símbolos).

• El segundo argumento es un número entero, que indica la cantidad de símbolos en una sola tarjeta. Será <= que el tamaño del conjunto de símbolos.

Salida

Imprima varias líneas separadas por nuevas líneas, cada una de las cuales contiene símbolos para una sola tarjeta.

Ejemplos

ABC
2
>>>>
AB
BC
AC

O

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

O

ABCDE
4
>>>>
ABCD

Consejos

• El número de cartas producidas no puede ser mayor que la cantidad de símbolos distintos y en muchas combinaciones será considerablemente menor
• Es posible que desee leer algunos antecedentes matemáticos si necesita ayuda con el lado matemático del problema

Este es mi primer desafío de código de golf, así que perdone posibles problemas con el formato / estilo. Intentaré corregir los errores si los señala en los comentarios.

Python 2 , 192 162 bytes

Tengo el argumento de que esto produce el conjunto máximo de tarjetas para cada escenario y maneja los 3 casos de prueba.

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

Pruébalo en línea!

Algoritmo

Dado un alfabeto ay un tamaño de tarjeta s, tome todas las combinaciones de selementos ay llámelo C, luego:

• Toma el primer elemento de C, llámaloC0
• Salvar C0
• Elimine todos los elementos Cque tengan una unión C0no igual a1
• Repita con el segundo elemento de C
• Continuar hasta que Cesté vacío

Luego imprima los elementos guardados.

Argumento

Un subconjunto no vacío de Ces nuestra solución máxima, K. Dado que contiene al menos un elemento y cualquiera de los dos elementos no se puede distinguir, elija un elemento arbitrario C0, de Cestar en K. Para cualquier elemento een el K, la cardinalidad de la eunión xes 1 para x != eadentro K; elimine todos los elementos en Ccuya unión con C0no tiene cardinalidad 1. Por el mismo razonamiento, elija un nuevo elemento arbitrario C, agréguelo Ky reduzca C. Eventualmente Ces el conjunto vacío y Kserá la solución máxima porque en ningún momento elegimos un elemento que fuera distinguible de cualquier otro elemento.

Casos de prueba

Estos casos de prueba fueron escritos antes de darme cuenta de que la impresión era un 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

Actualizar

• +9 [16-12-07] Se ajusta al requisito de impresión
• -11 [16-12-07] Golfed mi Rvariable
• -30 [16-12-09] Golfed mi Kvariable, ¡Gracias a @Leo !

Haskell, 175 156 bytes

Mi primera experiencia en el golf, avísame si he estropeado algo.

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)

Pruébalo en línea!

Gracias a @Paul Mutser por su mejora y -19 bytes

Versión original

Perl 6 , 88 77 bytes

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

Pruébalo en línea!