Dobble/SpotIt card generator

Question

Introduction

Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal version), but exactly one is common between each pair of cards.

Example from physical copy of game:

Challenge

Write a program, which given set of symbols (single ascii characters) and number of symbols on single card will produce output listing cards with symbols for each card. There are obviously many equivalent combinations, your program just has to write any of combinations which produces largest amount of cards for given input.

It is a code-golf, so shorter the code, better.

It would be also great if computation will finish before heat death of universe for most complicated case.

Input

Two arguments to function/stdin (your choice)

• First of them being collection of symbols, something like 'ABCDE" or ['A','B','C','D','E'] - your choice of format, be it string, set, list, stream, or whatever is idiomatic for language of choice. Characters will be given from set of [A-Za-z0-9], no duplicates (so maximum size of input symbol set is 62). They won't be neccesarily ordered in (so you can get "yX4i9A" as well for 6-symbol case).

• Second argument is integer, indicating amount of symbols on single card. It will be <= than size of symbol set.

Output

Print multiple lines separated by newlines, each one of them containing symbols for single card.

Examples

ABC
2
>>>>
AB
BC
AC

Or

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

Or

ABCDE
4
>>>>
ABCD

Hints

• Number of cards produced cannot be larger than amount of distinct symbols and in many combinations it will be considerably smaller
• You might want to read up Some math background if you need help with math side of the problem

This is my first code golf challenge, so please forgive possible issues with formatting/style - I'll try to correct errors if you point them in comments.

Edit: There is a very nice youtube video explaining the math behind the Dobble setup here:

Answer 1

Python 2, 192 162 bytes

I have an argument that this produces the maximum set of cards for every scenario and it does handle the 3 test cases.

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

Try it online!

Algorithm

Given an alphabet a and a card size s, take all combinations of s elements in a and call it C, then:

• Take the first element of C, call it C0
• Save C0
• Remove all elements fromC that have a union with C0 not equal to 1
• Repeat with second element of C
• Continue until C is empty

Then print the saved elements.

Argument

Some non-empty subset of C is our maximal solution, K. Since it contains at least one element and any two elements are indistinguishable, choose an arbitrary element, C0, of C to be in K. For any element e in the K, the cardinality of e union x is 1 for x != e in K; so eliminate all elements in C whose union with C0 does not have cardinallity 1. By the same reasoning, choose a new arbitrary element in C, add it to K, and reduce C. Eventually C is the empty set and K will be the maximal solution because at no point did we choose an element that was distinguishable from any other element.

---

Test Cases

These test cases were written before I realized that the printing was a requirement.

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

Update

• +9 [16-12-07] Fit the print requirement
• -11 [16-12-07] Golfed out my R variable
• -30 [16-12-09] Golfed out my K variable, Thanks to @Leo!

Answer 2

Haskell, 175 156 bytes

My first take at golfing, let me know if I've messed something up.

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)

Try it online!

Thank to @Paul Mutser for improvement and -19 bytes

---

Original version

Answer 3

Perl 6, 88 77 bytes

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

Try it online!