Questions tagged [sets]

Questions about finite and infinite sets and multisets, related data structures and concepts.

Filter by
Sorted by
Tagged with
1 vote
1 answer
27 views

Find the largest subset of unpaired elements [duplicate]

I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired? Example ...
user avatar
  • 113
1 vote
1 answer
22 views

Pair points between to sets minimizing the global distance

I have two set of points in the plane or space, which could be for instance radar contacts over two successive scans. I'd like to pair them so that the sum of squared distances is minimal. One ...
user avatar
  • 111
0 votes
0 answers
19 views

Algorithms for computing "optimal set growth order"

Imagine you have a collection of possible "components" (C) and a set of "recipes" assembled from those components (...
user avatar
  • 101
0 votes
1 answer
27 views

If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular

Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular. I think that this one is true, but I am stuck: Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
user avatar
  • 5
0 votes
0 answers
26 views

Prove that a predicate is not computable

Prove that the following predicate is not computable: $P_e(n) = \begin{cases} 1 & \textrm{if } \phi_n(n) = e \\ 0 & \textrm{otherwise} \end{cases}$ Could someone explain how to approach ...
user avatar
0 votes
0 answers
12 views

Is the closure of a Linear Time Property closed under union and intersection?

Defining the closure of a linear time property $P$ to be the set of all infinite traces $x$ such that the set of prefixes of $x$ is a subset of the set of prefixes of $P$, is $closure(P \cup P') = ...
user avatar
0 votes
0 answers
51 views

Find non intersecting elements quantity of the few unknown sets

There is group of sets. All sets have the same number of elements. Elements are unknown, but I know sizes of operation results for each pair of sets. (union, intersection, symmetric difference, ...
user avatar
2 votes
1 answer
23 views

Finding all combinations of length k that has at least one of the pairs of T is in it

Let there be a list of $n$ elements $S$. Let $T$ be a set with $m$ elements ($m \leq nC2$), with each element in $T$ being a pair of distinct elements of $S$. For $k\geq2$, is there a polynomial-time ...
user avatar
3 votes
1 answer
48 views

Fast algorithm for computing minimal closure of a set of sets under intersection?

A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $S$) under intersection", ...
user avatar
1 vote
0 answers
35 views

Prove that a dominating set has minimum cardinality in a "unit interval graph"

I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
user avatar
  • 149
1 vote
1 answer
21 views

Locality Sensitive Hashing for Sets

Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
user avatar
1 vote
0 answers
26 views

Find sets which are subsets of the given search set?

The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, ...
user avatar
  • 121
3 votes
0 answers
144 views

Changing a family of sets to become laminar

A family of sets $F = \{S_1, \dots, S_n\}$ on the ground set $S$ is laminar, if for every $1\leq i < j \leq n$, either $S_i \subsetneq S_j$ or $S_j \subsetneq S_i$ or $S_i \cap S_j = \varnothing$ ...
user avatar
  • 287
0 votes
1 answer
29 views

Is the equality of Bloom filters analogous to set equivalence?

I have two multisets $A$, $B$ where $A \subseteq B$. Using these two sets, we construct two Bloom filters $BF(A), BF(B)$; both using bitsets of size $n$ with the same $k$ hash functions. What's the ...
user avatar
  • 123
1 vote
0 answers
45 views

Is there a distributed streaming algorithm to verify set cover?

I have $k$ sets of similar sizes, that cover a universe $U$. e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$: $S_0 = \{1, 2, 4\}$ $S_1 = \{2, 3, 4\}$ $S_2 = \{4, 5, 6\}$ I have another larger set $C$ ...
user avatar
  • 123
1 vote
1 answer
23 views

DFA and a Partition of $\Sigma^*$

So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^*$. As an example, given a language $L$, a partition of $\Sigma^*$ would be $\{...
user avatar
0 votes
0 answers
31 views

How to generate supersets from a finite number of subsets efficiently

Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$: $ ${ a,b },$\{b,c\},${a,d} I want to create every possible set of cardinality ...
user avatar
  • 111
2 votes
1 answer
47 views

Union of multiple overlapping sets efficiently?

I have $n$ sets, each of which overlaps heavily with the other sets, and I want the union of all of them. The obvious solution is to take the union of each set, one by one, which results in $O(n^2)$ ...
user avatar
2 votes
1 answer
47 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
user avatar
2 votes
1 answer
72 views

Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ for all $k$. The problem is, divide $S$ ...
user avatar
  • 69
1 vote
1 answer
49 views

How to efficiently see if a value is in a set

I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
user avatar
  • 113
3 votes
1 answer
53 views

Deciding whether a set of relations can be composed to the empty relation

Is there an efficient algorithm to solve the following decision problem? Given a finite set $S$ and a set of relations $\mathcal R$ from $S$ to $S$, determine whether there is any sequence of ...
user avatar
1 vote
1 answer
90 views

Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
user avatar
1 vote
1 answer
56 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
user avatar
3 votes
1 answer
57 views

A heuristic for finding the vector that is maximally distant from a set of vectors

I have two sets of vectors: A and B. I want to find the vector Bi in set ...
user avatar
0 votes
0 answers
32 views

Algorithm for bipartite graph matching decision problem

Suppose I have a list of sets $$ L=\{A_1,A_2,\ldots ,A_n\} $$ And want and algorithm that solves the following decision problem Is it possible to select one element from each set such that no two ...
user avatar
  • 519
0 votes
1 answer
28 views

Minimum spanning tree where weights of edges are intersecting sets

Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$. Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...
user avatar
1 vote
2 answers
77 views

What is the entropy of an unordered list?

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :) Each integer is 6-digits, so ...
user avatar
2 votes
1 answer
49 views

Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?

I'm looking to formally define a tree and then extract the leaves from it in a concise way. Does this look ok? What is the best way of doing this? $ Y = \{a,b,c,d,e,f,g\} \\ R = \{a \mapsto b, a \...
user avatar
  • 143
4 votes
0 answers
86 views

Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
user avatar
1 vote
0 answers
30 views

Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
user avatar
14 votes
2 answers
993 views

Recover a set with the information of the sums of all its subsets

I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$? I have $2^n $ data. This is ...
user avatar
  • 293
2 votes
0 answers
82 views

Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue. The problem is this: I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
user avatar
0 votes
1 answer
61 views

Is this way to combine two functions into a new function called a function product?

I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, ...
user avatar
  • 143
1 vote
1 answer
16 views

Complement of $\{w\#x \mid w,x \in \Sigma^*, T(M_w) \neq \{x\}\}$

This is one of my homework assignment questions, that are quite difficult for me. The question states: Show that $L$ is not semi-decidable where $L = \{w\#x \mid w,x \in \Sigma^*, T(M_w)\neq \{x\}\}$ ...
user avatar
4 votes
1 answer
70 views

Combinatorics - how many $c$-distinct sets are possible?

I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here. I am given two ...
user avatar
  • 10.7k
0 votes
1 answer
19 views

Formal Description Of Data Structure For Infinite Sets Of Reals

The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it ...
user avatar
  • 2,467
1 vote
1 answer
16 views

Set notation for ACL matrix

This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
user avatar
  • 83
1 vote
1 answer
67 views

Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$

I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset. The sumset is $$ A + B = \{ a + b : a \in A , b \in B \} $$ and $R$ ...
user avatar
  • 13
2 votes
3 answers
235 views

Set theory pertaining to category theory and functional programming

I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following: A power set of a set is the set of all its subsets. A script 'P' is used ...
user avatar
  • 121
1 vote
0 answers
20 views

Streaming maximum pair matching with limited memory

I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of ...
user avatar
1 vote
2 answers
33 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
user avatar
  • 131
2 votes
1 answer
70 views

What is the difference between Partition and Division?

While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different? Can anyone explain me their difference in ...
user avatar
  • 39
2 votes
0 answers
37 views

Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
user avatar
  • 139
1 vote
0 answers
65 views

Disjoint groups using maximum matching

In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter $k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on ...
user avatar
  • 103
1 vote
0 answers
39 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
user avatar
  • 131
0 votes
1 answer
58 views

Tuple relational calculus: existential quantifiers

I have the following question and given answer: Question: List the names of managers who have at least one dependant. Answer: ...
user avatar
  • 27
6 votes
1 answer
165 views

Shared Elements Algorithm

I have a problem that I am working on an algorithm for: I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets) $S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\...
user avatar
  • 61
0 votes
2 answers
39 views

Is this the correct answer for the cardinality of this set?

This is a question from a practice quiz at my university. Is the question asking for the cardinality of Σ1 = {a,b} to the power of four? if that's the case, then the set would still have a ...
user avatar
  • 185
1 vote
1 answer
31 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
user avatar

1
2 3 4 5
8