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

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 \.

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

Ｉ⌈ＥＥΠＥθＬιＥθ§λ÷ι∨ΠＥ…θμＬν¹ＬΦι⁼μ⌕ιλ

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

      θ                             Input array
     Ｅ                              Map over lists
        ι                           Current list
       Ｌ                            Take the length
    Π                               Take the product
   Ｅ                                Map over implicit range
          θ                         Input array
         Ｅ                          Map over lists
            λ                       Current list
           §                        Cyclically indexed by
              ι                     Outer value
             ÷                      Integer divided by
                   θ                Input array
                  …                 Truncated to length
                    μ               Inner index
                 Ｅ                  Map over array
                      ν             Innermost list
                     Ｌ              Take the length
                Π                   Take the product
               ∨                    Logical Or
                       ¹            Literal integer `1`
  Ｅ                                 Map over lists
                          ι         Current list
                         Φ          Filtered where
                            μ       Inner index
                           ⁼        Equal to
                             ⌕      Index of
                               λ    Inner value
                              ι     In current list
                        Ｌ           Take the length
 ⌈                                  Take the maximum
Ｉ                                   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