7
\$\begingroup\$

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} 
\$\endgroup\$
7
  • 1
    \$\begingroup\$ You say v>2, but one of your test cases has v=2. Did you mean v≥2? \$\endgroup\$
    – xnor
    Jul 30 at 16:14
  • 3
    \$\begingroup\$ I think these are called covering designs. \$\endgroup\$
    – xnor
    Jul 30 at 16:16
  • \$\begingroup\$ May we use \$\{0,\dots,n-1\}\$ instead? \$\endgroup\$
    – Arnauld
    Jul 30 at 16:20
  • \$\begingroup\$ @xnor corrected v \$\endgroup\$
    – 2FaceMan
    Jul 30 at 16:26
  • \$\begingroup\$ @Arnauld if that helps, that's fine \$\endgroup\$
    – 2FaceMan
    Jul 30 at 16:27

4 Answers 4

3
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ I tried running (10, 6, 3) but it timed out \$\endgroup\$
    – 2FaceMan
    Jul 30 at 20:53
  • 1
    \$\begingroup\$ @2FaceMan it will, you'll have to run it on your own computer and wait several minutes (if not hours) probably \$\endgroup\$
    – Steffan
    Jul 30 at 20:54
  • 1
    \$\begingroup\$ @2FaceMan yep, too inefficient for that - it would construct a list of all \$2^{210}\$ collections of 6-tuples and then do the sort by number of 3-tuples covered. That will need quite a bit longer than 60 seconds! \$\endgroup\$ Jul 30 at 20:58
  • \$\begingroup\$ @Steffan you'll need an absolute tonne of memory too! (and I doubt it'd be hours even :p) \$\endgroup\$ Jul 30 at 21:00
  • \$\begingroup\$ @JonathanAllan Is there a way , getting count of set is less time consuming ? I can try validate against minimum count \$\endgroup\$
    – 2FaceMan
    Jul 31 at 8:09
2
\$\begingroup\$

Vyxal, 14 bytes

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

Try it Online!

Basically a port of Jelly, aka extremely slow.

Explanation coming soon.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Can you please also give normal java script code , just so I can understand it better \$\endgroup\$
    – 2FaceMan
    Jul 31 at 8:21
  • 1
    \$\begingroup\$ @2FaceMan I've added a commented version. \$\endgroup\$
    – Arnauld
    Jul 31 at 9:05
1
\$\begingroup\$

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

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.