# Generate number set with conditions using n numbers

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

## 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}

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

# 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:
⁵       -     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).

• I tried running (10, 6, 3) but it timed out Commented Jul 30, 2022 at 20:53
• @2FaceMan it will, you'll have to run it on your own computer and wait several minutes (if not hours) probably Commented Jul 30, 2022 at 20:54
• @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! Commented Jul 30, 2022 at 20:58
• @Steffan you'll need an absolute tonne of memory too! (and I doubt it'd be hours even :p) Commented Jul 30, 2022 at 21:00
• @JonathanAllan Is there a way , getting count of set is less time consuming ? I can try validate against minimum count Commented Jul 31, 2022 at 8:09

# Vyxal, 14 bytes

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


Try it Online!

Basically a port of Jelly, aka extremely slow.

Explanation coming soon.

• "Explanation coming soon." Commented Dec 14, 2022 at 19:24

# 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

• Can you please also give normal java script code , just so I can understand it better Commented Jul 31, 2022 at 8:21
• @2FaceMan I've added a commented version. Commented Jul 31, 2022 at 9:05

# 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

# 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