<p><strong>Problem.</strong> Let <span class="math-container">$x = (x_1,...,x_N) \in K^{N}$</span>, i.e., each element <span class="math-container">$x_j$</span> of <span class="math-container">$x$</span> can take <span class="math-container">$K$</span> discrete values. Let <span class="math-container">$x_{(i)}$</span>, for <span class="math-container">$i \in 1,...,I,$</span> be a vector of overlapping subsets of <span class="math-container">$x$</span>. For example, for <span class="math-container">$K = 2$</span>, <span class="math-container">$N= 3$</span>, and <span class="math-container">$I = 2$</span> we may have <span class="math-container">$x_{(1)} = (x_1,x_2)$</span> and <span class="math-container">$x_{(2)} = (x_2,x_3)$</span>.</p>
<p>I am looking for an algorithm that constructs a set of elements <span class="math-container">$y \in K^{N}$</span>
covering set of combinations for all <span class="math-container">$x_{(i)}$</span>. To clarify, consider the simple example above. The possible <span class="math-container">$x$</span> are:
<span class="math-container">$$
\{000,001,010,011,100,101,110,111\}
$$</span>
In this case, the choice for the above mentioning cover set is simple: <span class="math-container">$\{000,111,010,101\}$</span>.</p>
<p>However, I was wondering if there is an algorithm that builds such a set automatically in the general case. It would be nice for the algorithm to be efficient for large <span class="math-container">$K, N$</span> and such that it builds the above-mentioned set with minimal size.</p>

CC BY-SA 4.0
2022-09-28T23:51:07.060Z
Subsets, or contiguous sequence?  Could you have $x_{(1)}=(x_1,x_7)$?
D.W.
CC BY-SA 4.0
2022-09-28T23:52:04.183Z
What does "covering set of combinations for all $x_{(i)}$" mean?  That isn't even grammatical.  Please specify the problem clearly in general form.  An example is not a substitute for a clear specification of the problem.
D.W.
CC BY-SA 4.0
2022-09-29T11:03:49.490Z
@D.W. subsets, they can be non-contiguous
Apprentice
CC BY-SA 4.0
2022-09-29T11:04:22.030Z
Covering set of combinations means that all the local combinations of $x_{(i)}$ are in the covering sets
Apprentice
CC BY-SA 4.0
2022-09-29T16:55:00.180Z
Please don't answer in the comments.  Instead, [edit] your question so it is clear to someone who encounters this for the first time.
D.W.
CC BY-SA 4.0
2022-09-29T16:55:44.963Z
Your response just raises more questions for me.  You haven't defined what you mean by "local combinations".  I don't know what you mean by "covering sets" - the previous sentences says "constructs a set", singular.  I suggest you try formulating the problem statement in mathematics, specify the inputs and outputs for the algorithm, and the mathematical conditions under which the output is correct.
D.W.
<co.combinatorics><combinatorics><interaction-combinators>
Combinations of subsets
Apprentice
# Combinations of subsets

(Asked by: username_0 on 2022-09-28)

**Problem.** Let $x = (x\_1,...,x\_N) \in K^{N}$, i.e., each element $x\_j$ of $x$ can take $K$ discrete values. Let $x\_{(i)}$, for $i \in 1,...,I,$ be a vector of overlapping subsets of $x$. For example, for $K = 2$, $N= 3$, and $I = 2$ we may have $x\_{(1)} = (x\_1,x\_2)$ and $x\_{(2)} = (x\_2,x\_3)$.

I am looking for an algorithm that constructs a set of elements $y \in K^{N}$
covering set of combinations for all $x\_{(i)}$. To clarify, consider the simple example above. The possible $x$ are:
$$
\{000,001,010,011,100,101,110,111\}
$$
In this case, the choice for the above mentioning cover set is simple: $\{000,111,010,101\}$.

However, I was wondering if there is an algorithm that builds such a set automatically in the general case. It would be nice for the algorithm to be efficient for large $K, N$ and such that it builds the above-mentioned set with minimal size.

**Tags:** co.combinatorics, combinatorics, interaction-combinators

> **Comments:**
> **username_1**: Subsets, or contiguous sequence?  Could you have $x_{(1)}=(x_1,x_7)$?  
> **username_1**: What does "covering set of combinations for all $x_{(i)}$" mean?  That isn't even grammatical.  Please specify the problem clearly in general form.  An example is not a substitute for a clear specification of the problem.  
> **username_0**: @username_1 subsets, they can be non-contiguous  
> **username_0**: Covering set of combinations means that all the local combinations of $x_{(i)}$ are in the covering sets  
> **username_1**: Please don't answer in the comments.  Instead, [edit] your question so it is clear to someone who encounters this for the first time.  
> **username_1**: Your response just raises more questions for me.  You haven't defined what you mean by "local combinations".  I don't know what you mean by "covering sets" - the previous sentences says "constructs a set", singular.  I suggest you try formulating the problem statement in mathematics, specify the inputs and outputs for the algorithm, and the mathematical conditions under which the output is correct.  

---

## 0 answers

