Only one from each set

Question

Your input is a non-empty set of non-empty sets of positive integers. For example:

{{1}, {2, 3}, {2,4}, {1,4}}

Your task is to output the maximal number of elements that can be picked from the sets with the following conditions:

• You can only pick at most 1 element from a set
• You can't pick the same element from 2 different sets

In this example you can pick 1 from the first set, 3 from the second set, 2 from the third set and 4 from the last set, for a total of 4 elements.

Io is flexible. You can take a list, instead of sets, etc.

There are no gaps in the numbers (eg. {{2,3},{3,4}} is not a valid input). Or in other words, the input flattened must contain all numbers [1,n] where n is the largest number in the input.

This is code-golf, so shortest code wins.

Examples

{{1}}
-> 1
{{1}, {2, 3}, {2,4}, {1,4}}
-> 4
{{1}, {2}, {1,2,3,4}}
-> 3
{{1}, {2}, {2,3}}
-> 3
{{1, 2, 3}, {2, 4, 5, 6}, {3, 5, 6, 7}, {1, 2}, {2, 3}, {1, 3}}
-> 5
{{1,2,3,4,5}, {1,2}, {2,3}, {1,3}}
-> 4
{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{5,6,7,8,9,10}}
-> 5
{{1,4}, {2,3}, {1,3}, {1,2,3}}
-> 4

Background

Recently @AnishSharma posted this question on Stack Overflow. This is a slightly modified version of that question

• Wheat Wizard: Is it acceptable to output a selection of the maximum number instead of the number?
• AnttiP: Do you mean like a set of picks? If so, the answer is no, just output the length of that set.
• aschepler: Is "3 from the second set, 2 from the second set" a typo for "3 from the second set, 2 from the third set"?

Answer 1

Python 3, 66 bytes

lambda x:max(map(len,map(set,product(*x))))
from itertools import*

Try it online!

Answer 2

Jelly, 6 bytes

ŒpQ€ẈṀ

Try It Online!

ŒpQ€ẈṀ Main Link
Œp Cartesian Product; get all possible selections
 Q€ Uniquify each
 Ẉ Length of each
 Ṁ Maximum result

Answer 3

Python 3, 63 bytes

f=lambda s,*v:s and max(f(s[1:],x,*v)for x in s[0])or len({*v})

Try it online!

Answer 4

JavaScript (ES6), 70 bytes

Expects an array of arrays.

f=([b,...a],s)=>b?Math.max(...b.map(v=>f(a,new Set(s).add(v)))):s.size

Try it online!

Commented

f = ( // f is a recursive function taking:
 [b, // b[] = next list
 ...a], // a[] = all remaining lists
 s // s = current set, initially undefined
) => //
b ? // if b[] is defined:
 Math.max( // return the maximum of ...
 ...b.map(v => // for each value v in b[]:
 f( // do a recursive call:
 a, // pass a[]
 new Set(s) // create a new set from s
 // (an empty set if s is undefined)
 .add(v) // add v to it
 ) // end of recursive call
 ) // end of map()
 ) // end of Math.max()
: // else:
 s.size // return the size of s

Answer 5

R, (削除) 55 (削除ここまで) 54 bytes

Edit: -1 byte thanks to pajonk

function(x)max(lengths(apply(expand.grid(x),1,table)))

Try it online!

Test setup stolen from pajonk's R answer.
48 bytes using R ≥ 4.1 by exchanging function for \.

• pajonk: TIL about lengths function. Thanks!
• Dominic van Essen: @pajonk - You're welcome. It's quite disconcerting when you accidentally learn something potentially useful while deliberately trying to write difficult-to-understand code, isn't it? This has often happened to me, too...
• pajonk: You're absolutely right... BTW, you "stole" the test setup from me, but not the table function (for -1) ;-)
• Dominic van Essen: @pajonk - Dang, you're right! But if I use table instead of unique, it'd be the same as you using lengths instead of sapply(,length)... we should flip a coin somehow do decide who gets to use the other's function...
• Dominic van Essen: "pajonk_guesses_heads" ends in letter s ≠ t (by odd/even position).

Answer 6

Haskell + hgl, 10 bytes

xMl<nb<<sQ

Works as of commit 4a9f6d27. Older version below.

Explanation

The functions involved are:

• sQ can do many things but on lists it performs the cartesian product.
• nb removes all duplicate lements from a list.
• xMl gets the length of the longest list in a list of lists

So we get the Cartesian product, nub the results and then get the maximum of their lengths.

Haskell + hgl, 13 bytes

mx<l.^nb.^sQ

This no longer works in recent versions of hgl since (.^) was renamed to (<<). To test it run:

mx<l<<nb<<sQ

Explanation

This works the same as the new implementation above except we have to get all the lengths and then get the maximum separately. The new functions are:

• l gets the length of a list
• mx gets the maximum of a list.

So we get the Cartesian product, nub the results and then get the maximum of their lengths.

Reflections

• First things first we don't have a set type. This is unfortunate and needs to be fixed at some point.
• l<nb seems like something that would be useful to have a builtin for.
• It would be nice to have some sort fold and sequence or fold and traverse combined function.
• (削除) I could have used a "maxmap". If we wanted to get the actual choices we could have done, xB l<nb.^sQ to save two bytes. But xB returns the original list not the modified version. (削除ここまで) This has been fixed in newer versions with the function is called xM, but xMl was also added which saves another byte.

Answer 7

Factor, 42 bytes

[ [ members ] product-map longest length ]

Try it online!

Uniqueify the elements of the product sequence of the input, then find the longest length.

Answer 8

R, 60 bytes

Or R>=4.1, 53 bytes by replacing the word function with a \.

function(x)max(sapply(apply(expand.grid(x),1,table),length))

Try it online!

---

Solution shorter in R>=4.1:

R, 66 bytes

Or R>=4.1, 52 bytes by replacing two function occurrences with \s.

function(x)max(apply(expand.grid(x),1,function(a)sum(table(a)|1)))

Try it online!

Answer 9

Vyxal, 6 bytes

Πv‡ULG

Try it Online!

Π # Cartesian product - get all possibilties
 v # Over each...
 ‡-- # Do the next two elements
 U # Uniquify 
 L # Get length
 G # Maximum

Answer 10

Charcoal, 32 bytes

I⌈EEΠEθLιEθ§λ÷ι∨ΠE...θμLν1LΦι=μ⌕ιλ

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

 θ Input array
 E Map over lists
 ι Current list
 L Take the length
 Π Take the product
 E Map over implicit range
 θ Input array
 E Map over lists
 λ Current list
 § Cyclically indexed by
 ι Outer value
 ÷ Integer divided by
 θ Input array
 ... Truncated to length
 μ Inner index
 E Map over array
 ν Innermost list
 L Take the length
 Π Take the product
 ∨ Logical Or
 1 Literal integer `1`
 E Map over lists
 ι Current list
 Φ Filtered where
 μ Inner index
 = Equal to
 ⌕ Index of
 λ Inner value
 ι In current list
 L Take the length
 ⌈ Take the maximum
I Cast to string
 Implicitly print

Answer 11

05AB1E, 10 bytes

.»âε ̧ ̃Ùg}à

Try it online or verify all test cases.

Explanation:

.» # (Left-)reduce the (implicit) input-list by:
 â # Cartesian product
ε # Then map over each inner list:
 ̧ # Wrap it into a list (workaround for input [[1]])
 ̃ # Flatten it
 Ù # Uniquify it
 g # Pop and push the length
}à # After the map: pop and push the maximum
 # (which is output implicitly as result)

Answer 12

Julia, 55

J(l)=maximum(length.(Set.(Iterators.product(l...))[:]))

ATO