Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
47 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 ...
2 votes
1 answer
41 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 ...
2 votes
1 answer
159 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 ...
0 votes
0 answers
42 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
36 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, ...
1 vote
1 answer
74 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 ...
0 votes
1 answer
65 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 ...
2 votes
1 answer
56 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 ...
0 votes
1 answer
56 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 ...
2 votes
0 answers
110 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 ...
0 votes
1 answer
52 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 vote
1 answer
40 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, ...
2 votes
1 answer
78 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 ...
1 vote
1 answer
45 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 ...
25 votes
4 answers
9k views

Data Structure for Set Intersection?

Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated? Init an empty set. Add an ...
2 votes
0 answers
24 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 $...
2 votes
1 answer
83 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. ...
0 votes
1 answer
22 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 \...
0 votes
0 answers
50 views

Binary range identification in terms of subset

Given a range of "K" bit numbers, we want to identify the whole range by using a subset within that range, with the following criteria - If there are > "n" consecutive 0s, it ...
1 vote
1 answer
25 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 ...
1 vote
1 answer
55 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$...
3 votes
2 answers
141 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)$ ...
1 vote
1 answer
74 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 ...
1 vote
3 answers
533 views

Check whether set of strings is prefix-free via lexicographic sort?

I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So ...
2 votes
1 answer
57 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, ...
1 vote
2 answers
101 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 $...
0 votes
1 answer
48 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 ...
0 votes
1 answer
136 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 ...
0 votes
0 answers
36 views

Finding Minimum Elements for Longest Path in Disjoint Set

I want to know the minimum number of elements needed to create a tree with the longest path having n edges. How can I approach this problem using the forest implementation of disjoint sets with union ...
3 votes
0 answers
158 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 ...
0 votes
0 answers
27 views

Find a set of elements with minimal costs that contains at least one element of given subsets

I have encountered at my work currently a problem where I want to find an efficient algorithm for, although I suspect this might be hard problem. Maybe you can help me to tell if this is a NP hard ...
6 votes
0 answers
1k views

Time complexity of obtaining the support set of an unsorted sequence?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
3 votes
0 answers
99 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 ...
2 votes
1 answer
92 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 ...
0 votes
0 answers
16 views

Trying to figure out how to model the structure of a multilingual dictionary for several constructed languages (basically Wiktionary for my conlangs)

Okay, so, this will be quite a bit, sorry. I'm working on several constructed languages for a worldbuilding project. Up until this point, I have been using a spreadsheet to store the vocab; each row ...
2 votes
1 answer
77 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 ...
1 vote
1 answer
52 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 ...
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 ...
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 ...
0 votes
5 answers
793 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 ...
0 votes
3 answers
113 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_{...
1 vote
1 answer
64 views

Binary subsets for a given set

Lets take an example of the range of N=32 bits ...
4 votes
0 answers
82 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, ...
1 vote
0 answers
21 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 ...
-4 votes
2 answers
61 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 vote
1 answer
39 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 \...
3 votes
1 answer
124 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 ...
0 votes
1 answer
82 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 ...
17 votes
4 answers
6k views

What exactly is the semantic difference between category and set?

In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of ...
6 votes
0 answers
43 views

How to find the minimum number of elements to distinguish several given sets?

Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum? For example, given $\{...

1
2 3 4 5
9