Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
441 questions
1
vote
0
answers
21
views
Intersections of Sets of Strings (Alabama, Alaska, Arizona, Arkansas)
Consider the following four strings of text:
Alabama
Alaska
Arizona
Arkansas
These strings of text represent four names for four different states within the United States of America.
Suppose that ...
1
vote
1
answer
68
views
What's the real life uses of Reflexive Closure in computer science?
I was tasked to discuss Reflexive Closure, in relation to computer science. In Discrete Mathematics context, its basically a set that relates to an element itself. But I just can't find any ...
0
votes
0
answers
34
views
Question regarding coinduction
I'm rather stuck with the example of proof by coinduction, as generally known the principle is written as:
$$
P\subseteq F(P)\implies P\subseteq \nu F
$$
in an old problem When can the coinduction ...
- 143
1
vote
0
answers
30
views
Construction of a polynomial time algorithm
We are currently learning derandomization, which aims to transfer a probabilistic proof into a deterministic algorithm. My problem is as follows.
Given $n$, constructs in time polynomial in $n$, a ...
- 111
0
votes
1
answer
29
views
How to find the minimum set of members of many sets
Given many sets, what algorithm finds the minimum set(s) of members present in all those sets?
For example, given these sets:
{1,2}
{1,2,44}
{2,5,6}
{5,6}
The ...
- 101
2
votes
1
answer
714
views
Definition feels contradictory (Computational Complexity Theory)
I studied a definition for time complexity:
Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be:
for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural ...
- 23
3
votes
1
answer
64
views
Is there an algorithm for rearranging a set in a specific way while optimizing for minimum amount of moves?
Say I have an array that goes like [ a, c, b, d ] and I want it rearranged as [ d, c, a, b ]. The only type of change I'm allowed to make is plucking an element from one place and inserting it into ...
- 161
0
votes
1
answer
54
views
Binary subset rank and unrank
Let there be "N" bits.
We want to rank and unrank a specific subset of bit combinations based on the following criteria -
...
- 25
0
votes
0
answers
30
views
Can you make the following "coinductive" proof precise?
Question: I have a proof which overwhelmingly feels like it's a proof "by coinduction." Unfortunately I can't coinduct my way out of a paper bag, so I don't know if this actually works. I ...
- 131
1
vote
1
answer
87
views
Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
- 13
2
votes
1
answer
63
views
Decide whether this Problem NPC or P?
Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N.
Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n?
I read somewhere (without ...
- 59
2
votes
1
answer
172
views
Given two sets of integers find an integer in the first set furthest away from all members of the second set
If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two ...
- 123
0
votes
0
answers
91
views
CSES Sliding Cost - why is this formula for updating the cost correct?
In the CSES problem Sliding Window Cost, given an array and an integer k, we are asked to compute the minimum cost for each sliding window of fixed size ...
4
votes
0
answers
39
views
Cardinalities in set coverings
Let
$I$ be a set of items;
$C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And
$C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
2
votes
1
answer
72
views
"Consecutive statements" in Static control Part(SCoP)
Context:
I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.
Paper ...
- 123
2
votes
0
answers
119
views
SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic
Context:
While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
- 123
1
vote
1
answer
42
views
Does adding all of these sequences actually get us the set of all infinite sequences?
Section 1.9 Binary Strings of the textbook Introduction to Lattices and Order, second edition, by Davey and Priestley, says the following:
Let $\Sigma^\ast$ be the set of all finite binary strings, ...
- 217
1
vote
1
answer
66
views
If A U B and A ∩ B are recognizable, then is one of A, A', B, B' also recognizable?
I know that if decidability of $A \cap B$ and $A \cup B$ doesn’t
guarantee the decidability of any of $A$ or $B$. We can prove that:
ATM is not decidable. Since decidable languages are closed under ...
- 11
2
votes
0
answers
28
views
Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
- 542
0
votes
1
answer
25
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
1
vote
1
answer
28
views
Linked Lists, Ordered Pairs?
I would like to model linked lists using set theory similar to that in Scheme and LISP.
There is a set theoretic definition of the ordered pair:
$p = \{\{a, 1\}, \{b, 2\}\}$
My question is how does ...
- 111
1
vote
1
answer
66
views
Is this variant of multiset covering problem NP-hard?
Consider this variant of multiset 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$ and $s_k \neq \emptyset$ for all $k$...
- 11
1
vote
1
answer
92
views
Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
- 25
2
votes
1
answer
68
views
Algorithm to identify common subsets
Given a large dataset $D$ and multiple sets of filters that can be applied to $D$, e.g.
$setA = \{filterOnColorRed\}$
$setB = \{filterOnAgeGreaterThan20\}$
$setC = \{filterOnColorRed, ...
- 121
3
votes
1
answer
169
views
Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:
df1 for distributor 1.
...
- 292
1
vote
2
answers
148
views
Can we efficiently find the most common pair in a set of sets?
Given a collection of sets $C=\{S_1, S_2, \ldots, S_n\}$ with each $S\in C$ holding some integers, I would like to find a pair $\{x,y\}, x\ne y$ such that $\{x,y\}\subset S$ for the highest number of $...
- 913
0
votes
1
answer
147
views
Minimal Hitting Sets Problem
Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$.
We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
- 173
0
votes
1
answer
68
views
Constructing a Container for the Given Situation
I need to make a container in which I can store (x,y) as pairs, and for a given number 'a', I have to find a pair (p, q) such that p<=a and q is maximum possible.
Note the constraints: x>=1 and ...
0
votes
1
answer
151
views
Best balanced assignment
I'm at a problem I don't know better to name it... maybe it's already a well known problem?
It seems quite simple:
There are objects and labels in a n:m relation.
(Each of the n objects may be ...
- 1
8
votes
1
answer
307
views
Maximum set cover with non-overlap
Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that:
$s_i \in S$ $\forall ...
- 81
0
votes
1
answer
64
views
Assignment problem with maximal partitioning
Recently I came across a problem I don't get may hands on:
Given p binary positions.
Let s be the number of "set-bits" (1 < s < p * 2^(p-1) - 1).
I need the maximal set of assigments ...
- 1
3
votes
0
answers
141
views
Map-like data structure with subsets as keys
I am looking for a map-like data structure with the following properties:
it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime
the ...
- 131
1
vote
1
answer
27
views
Is there a practical algorithm for estimating antichain coverage of a superset?
Suppose I'm given a set $S$ and antichain $A \subset 2^S$ ($\forall a_1,a_2\in A: a_1\neq a_2 \iff a_1 \nsubseteq a_2$).
Let's call subset $b \in 2^S$ covered by $A$ if $\exists a \in A :b \subseteq a ...
- 133
0
votes
0
answers
47
views
Sending set of string in HTTP query string
I'd like to implement pagination for an API. The elements are ordered by time but there can be multiple elements with the same timestamp. So there can be some duplication between the last elements of ...
- 111
1
vote
1
answer
53
views
How is the direct product of the functions (A -> B) * (C -> D) equivalent to the function (A * C) -> (B * D)? Is there an error here?
In the simply typed lambda calculus we have type algebra - types can be added, multiplied and exponentiated, where addition corresponds to the sum type, multiplication to the product type, and ...
2
votes
1
answer
100
views
What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?
A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
- 817
0
votes
5
answers
1k
views
What is the difference between the set containing the empty string and the set containing nothing at all?
It's an exercise question from chapter 0 of Michael Sipser's book Introduction to the Theory of Computation.
e. The set containing the empty string
f. The set containing nothing at all
I guess the ...
- 11
0
votes
3
answers
149
views
Given two sets of coordinates, find out neighboring ones
I have two sets of 2-dimensional coordinates on an integer grid, $A$ and $B$
$A = \{(x_{A1},y_{A1}), (x_{A2}, y_{A2}), (x_{A3}, y_{A3}), \dots\}$
$B = \{(x_{B1},y_{B1}), (x_{B2}, y_{B2}), (x_{B3}, y_{...
- 203
1
vote
1
answer
77
views
4
votes
0
answers
90
views
Finding all sets which are not subsets of other sets
I have a set of sets, for example
{
{1, 2, 3},
{1, 2},
{2},
{2, 4}
}
I want to find all sets which are not subsets of another set. For example, ...
- 141
1
vote
0
answers
26
views
Randomly Split a Bar Into Beats
So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc.
As for now the randomisation works on tones building sequences of equal duration.
What I'd like to do is ...
- 111
-5
votes
3
answers
130
views
Let F be a function defined for all nonnegative integers by the following recursive definition
Let F be a function defined for all nonnegative integers by the following recursive
definition.
F(0) = 0, F(1)= 1
F(n + 2) = 2F(n) + F(n +1), n>0
Compute the first six values of F; that is, write ...
- 1
1
vote
1
answer
50
views
How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:
Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$.
For $u \in U$ let $r(u) := \lvert \...
- 457
0
votes
1
answer
113
views
Way to call and explain: "potentially infinite set of attributes" in databases
This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms.
Let's say we have a database in which one ...
0
votes
1
answer
95
views
Logical Consequence - Equivalent Assertions
I have the following slide in my notes and I'm having trouble understanding how the three assertions are equivalent. I understand to a degree how the 2nd and 3rd assertions are equivalent, but the ...
- 9
0
votes
1
answer
37
views
Reconstruction of the universal set from disjoint subsets
Before I even attempt coming up with an efficient algorithm, I tried googling for similar problems but didn't get far, most queries mentioning "sets" in them led to some sort of Multiple ...
0
votes
1
answer
345
views
Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?
Lets say the alphabet is Σ=∅,what are the possible languages of this alphabet?
According to my definitions:
I know that an alphabet is a finite set of symbols Σ
I know words is a set of all finite ...
- 3
0
votes
1
answer
35
views
Algorithm for allocating resources; one resource per one user who accepts it
I am looking for an algorithm for the following problem:
I have a set of users and a set of books.
Every user has their own set of favorite books, which may be empty, and is a subset the set of books.
...
- 113
0
votes
1
answer
77
views
Is there a computationally efficient algorithm which can map back and forth a multi-dimensional real number (R^n) to a single dimensional real (R)?
I believe its possible to achieve this with natural numbers.
The example below is for 2d to 1d conversions both ways, I do believe this generalizes to n-dimensions.
The mapping should work in a way ...
- 173
3
votes
2
answers
150
views
Find if a given number must be in a set that is closed under gcd and lcm with some given elements
Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).
There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
- 159