Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
351
questions
1
vote
1answer
29 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$ ...
1
vote
3answers
174 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 ...
1
vote
0answers
17 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 ...
1
vote
2answers
22 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 ...
2
votes
1answer
37 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 ...
2
votes
0answers
33 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 :
...
1
vote
0answers
53 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 ...
1
vote
0answers
31 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 ...
0
votes
1answer
37 views
Relational Algebra: existential quantifiers
So i have the following question and template answer:
Question: List the names of managers who have at least one dependant.
Answer: {e.Fname, e.Lname | EMPLOYEE(e) AND (∃d)(∃t)(DEPARTMENT(d) AND ...
6
votes
1answer
155 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\...
0
votes
2answers
35 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 ...
1
vote
1answer
22 views
Efficient cardinality of set overlap relation
Assume that we have a set S of sets s.
Every pair (s,s') in ...
1
vote
1answer
34 views
Families of sets indexed by another set
I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.
If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is ...
3
votes
1answer
38 views
For two sets of points find if second one is result of linear transformation of the first
Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of ...
0
votes
0answers
15 views
Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions?
I am trying to find an online/offline tool that can compute the following:
Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation
R = {(a1, a2),(...
2
votes
2answers
83 views
Maximize number of subsets
Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words,
$...
1
vote
1answer
22 views
Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement)
(originally asked on StackOverflow)
Two recent questions on StackOverflow by the same author1 are generally solved by the same technique. This feels to me like it would be a studied and perhaps well-...
0
votes
1answer
25 views
Find sets of weighted objects to maximize number of sets with weight >= X
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
0
votes
1answer
34 views
How to implement conditional probability distribution on set-valued Random Variables
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
1
vote
1answer
34 views
“The Annotated Turing” on listing all binary numbers between 0 and 1
In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote:
These are binary numbers between 0 and 1, and (judging from the way we
created these numbers) all ...
0
votes
0answers
32 views
String membership in hash set time complexity
Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
3
votes
0answers
26 views
Components of subset partial order
Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper.
But is there any work on algorithms ...
3
votes
1answer
121 views
How to detect “tree-able” set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
2
votes
1answer
62 views
Efficient Implementation of Boolean Lattice-Esque Operation
Let $X = \{1,2,\dots n\}$, and $Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$. I am interested in "avoidance sets" $A \subset Y_n$. We say a subset $S \subset X$ is valid with respect to an ...
0
votes
1answer
54 views
Combinations of set unions
I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$...
6
votes
2answers
163 views
Spanning tree in a graph of intersecting sets
Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words
$$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\...
2
votes
1answer
95 views
Find two disjoint set
Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in ...
2
votes
1answer
39 views
Optimal Selection of Non-Overlapping Jobs
I'm trying to find what the family of problem is - as well as an approach - for the following:
I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri.
Each task ...
1
vote
0answers
47 views
Clustering sets by set difference
Suppose you have $n$ nonequal sets $S_1, \ldots, S_n$ and some constant $0 \le k < n$. The goal of set clustering is to find a partition of the set $\mathbf{S} = \{S_1, \ldots, S_n\}$ such that the ...
2
votes
1answer
385 views
C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?
I'm working on the problem: Count smaller elements on right side using Set in C++ STL
The solution is to add each element to the set and then to count the elements on the left, the distance function ...
1
vote
1answer
61 views
Algorithm to check Gibbs' Phase Rule
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have ...
1
vote
1answer
52 views
Need hint for bipartiteness proof
I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(...
0
votes
1answer
72 views
Splitting a group of numbers into $k$ sorted groups
I have this first task:
You have a set of numbers $S =\{ \dots \}$ of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$
Your task is to write an algorithm (...
1
vote
1answer
78 views
Sets in Mathematics are immutable but in Computer Science sets are mutable and called “Dynamic Sets” - truth of the statement
While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:
Sets are as fundamental to computer science as they are to mathematics. Whereas ...
1
vote
0answers
33 views
Set data structure for data too large to fit into memory
I'm trying to solve the following exercise:
Given N data items and memory that can hold M/B blocks of size B.
Describe a data structure that needs at most N/B blocks of external memory and allows ...
0
votes
1answer
154 views
What is the time complexity of subset testing?
Consider the following problem:
Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be
two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted.
...
0
votes
1answer
52 views
Is the empty string and some words of even length are elements of this set?
$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.
I have my answers, but I need confirmation:
Is the empty string $\epsilon \in L$? Yes. Reason: ...
0
votes
0answers
27 views
Computing Follow sets of Grammar for LL(1) parser
I am trying to compute the Follow set of the following Grammar:
E -> E' E A
A -> + | *
E -> num
E' -> num
I start by adding the end of string symbol, ...
1
vote
0answers
34 views
Optimally find one of the total orderings for a poset based on some metadata about the elements
Given a finite, partially ordered set with the following two properties:
Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
2
votes
1answer
24 views
Uniquely identifying bits
Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them?
Is this problem NP-Hard?
For example, given the $4$ unique ...
0
votes
1answer
77 views
Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question
hope you all are doing well.
I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien....
2
votes
1answer
26 views
Maximizing integer sets intersection (with integer delta)
There are two sets of integers with different numbers of items in them.
...
1
vote
1answer
29 views
Efficiently finding the intersections of sets that yield a desired set
Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as ...
3
votes
1answer
62 views
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it ...
2
votes
1answer
35 views
Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.
I have a puzzle: ...
2
votes
2answers
31 views
Data structure for or-lookups over bit-field associations maps
For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.
Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
1
vote
0answers
25 views
Algorithm for finding the set of systems of distinct representatives
Given a collection of finite sets, is there an algorithm for finding the set (unordered) of all systems of distinct representatives for the collection?
Example:
S: {{1, 2}, {1, 2, 3}}
Unordered ...
3
votes
1answer
76 views
Smallest set of balls under hamming distance that covers all $n$-bit strings
Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,
$$S_{y_i} = \{y \in S\...
1
vote
1answer
121 views
Is the powerset of a regular set also a regular set?
If so, where can I find a proof of it? If not, is there a counterexample?
By powerset of a regular language I mean the set of all subsets of a regular language.
Thank you, Marcus.
3
votes
1answer
293 views
How to get an element from an existential proposition in Type theory proof assistant (Lean prover)
I am trying to implement set theory in type theory from scratch, just for self pedagogical purposes. Specifically, I'm using the Lean Prover, and defining the element-of relation from scratch using ...
