Generate number set with conditions using n numbers

Question

Generate \$T=\{T_1,...,T_x\}\$, the minimum number of \$k\$-length subsets of \$\{1,...,n\}\$ such that every \$v\$-length subset of \$\{1,...,n\}\$ is a subset of some set in \$T\$

1. Here, \$n > k > v\$ and \$v \ge 2\$
2. Any number can appear only once in 1 set
3. Order of numbers is not important

Answer with code & explanation

Test Cases

\$(n,k,v) \to output \$

(4, 3, 2)  ->  {1  2  3}    
               {1  2  4}
               {1  3  4}
                    

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

Answer 1

Jelly, 15 bytes

œcŒPṚœc€⁵ẎQLƲÞṪ

A full program that accepts alphabet size (n), block size (k), and subset size (v) and prints a minimum covering design.

Try it online!

How?

Naive brute-force, and about as inefficient as possible!

œcŒPṚœc€⁵ẎQLƲÞṪ - Main Link: n, k
œc              - k-combinations of [1..n] without repeats
  ŒP            - powerset
    Ṛ           - reverse (to be from longest to shortest)
             Þ  - (stable) sort (these proposed solutions) by:
            Ʋ   -   last four links as a monad:
        ⁵       -     with right argument = third program argument (v)
       €        -       for each k-tuple in the proposed solution:
     œc         -         v-combinations of the k-tuple
         Ẏ      -     tighten to a list of the covered v-tuples
          Q     -     deduplicate
           L    -     length -> number of distinct v-tuples covered
              Ṫ - tail -> i.e. (one of) the shortest valid proposed solution(s)
                - implicit print

---

Aside:

A greedy method of adding the lexicographically first unused block that covers the most so far uncovered subsets gets an optimal covering design sometimes and a fairly good alternative (slightly larger number of blocks) other times. Using other orderings (than lexicographic) with the same selection criteria will find optimal coving designs sometimes too. See New Constructions for Covering Designs (Daniel M. Gordon, Greg Kuperberg, Oren Patashnik)

This Python code does this with the lexicographic ordering - it gets a different, optimal solution for n=10 k=6 v=3 (also 10 blocks), but a non-optimal one for (for example) n=6 k=4 v=3 (one too many blocks).

Answer 2

Vyxal, 14 bytes

ɾḋṗṘµ⁰vḋÞfUL;t

Try it Online!

Basically a port of Jelly, aka extremely slow.

Explanation coming soon.

Answer 3

JavaScript (ES10), 188 bytes

Another brute-force solution that is unlikely to solve the second test case before the heat death of the universe.

Results are 0-indexed.

(n,k,v)=>(g=(v,i=n,a=[])=>i--?g(v,i,a).concat(g(v-1,i,[i,...a])):v?[]:[a],F=s=>s.find(c=>g(v).every(b=>c.some(a=>b.every(v=>a.includes(v)))))||F(s.flatMap(a=>g(k).map(b=>[...a,b]))))([[]])

Try it online!

Commented

Helper function

\$g\$ is a helper function that, given \$v\$, returns the list of all subsets of \$[0\dots n-1]\$ of length \$v\$. (Note that it is meant to be defined in the scope of the main function so that \$n\$ is known.)

g = (                   // g is a recursive function taking:
  v,                    //   v = expected length
  i = n,                //   i = counter, initialized to n
  a = []                //   a[] = current subset
) =>                    //
  i-- ?                 // decrement i; if it was not zero:
    g(                  //   do a recursive call where
      v, i, a           //     nothing is changed
    )                   //
    .concat(            //   append the result of
      g(                //   another recursive call where
        v - 1,          //     v is decremented
        i,              //     and
        [i, ...a]       //     i is inserted at the beginning of a[]
      )                 //
    )                   //
  :                     // else:
    v ? []              //   ignore this subset if its length is not v
      : [a]             //   otherwise, append it to the output list

Main function

(n, k, v) => (          // f is the main function, taking n, k, v
  F =                   // F is a recursive function taking a list of
  s =>                  // lists of k-subsets
  s.find(c =>           // is there a list c[] in s[] satisfying ...
    g(v)                //   build all v-subsets
    .every(b =>         //   for each v-subset b[]:
      c.some(a =>       //     is there some k-subset a[] in c[] ...
        b.every(v =>    //       such that each value v in b[] ...
          a.includes(v) //         can be found in a[]?
        )               //       end of every()
      )                 //     end of some()
    )                   //   end of every()
  )                     // end of find()
  ||                    // if no solution was found:
    F(                  //   do a recursive call:
      s.flatMap(a =>    //     for each entry a[] in s[]:
        g(k)            //       build all k-subsets
        .map(b =>       //       for each k-subset b[]:
          [...a, b]     //         append b[] to a[]
        )               //       end of map()
      )                 //     end of flatMap()
    )                   //   end of recursive call
)([[]])                 // initial call to F with a single empty list

Answer 4

Python, 168 165 bytes

from itertools import*
def f(n,k,v):
 c,r,i=combinations,range(n),0
 while i:=i+1: 
  for t in c(c(r,k),i):
   if not{*c(r,v)}-{*chain(*[c(s,v)for s in t])}:return t

Attempt This Online!

Explanation

A brute-force solution. It iterates through all possible sizes of output sets \$i=1,2,\ldots\$, then checks the condition on each, and returns the first set of sets that meets the condition.

---

-3 bytes from @Steffan for extraneous parens

Answer 5

JavaScript (Node.js), 173 bytes

(n,k,v)=>(h=(e,...z)=>(g=(k,m=n,z=[])=>m--?[...g(k,m,z),...g(~-k,m,[m,...z])]:k?[]:[z])(v).every(i=>e.join`
`.match(i.join`,(.*,)?`))?e:h(...z,...g(k).map(x=>[...e,x])))([])

Try it online!

(n,k,v)=>(
  h=(e,...z)=> // Take first
    g(v).every( // For each n choose v
      i=>e
        .join`\n` // Arrays separated by newline
                  // which won't match `.`
        .match(i.join`,(.*,)?`))?
                  // Match at least one line
        e:h(...z,...g(k).map(x=>[...e,x])) 
            // If one fail then append another and throw to end
)
([]) // Starts with nothing

See Arnauld's answer for explanation of g