Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
12 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 $...
chausies's user avatar
  • 532
0 votes
1 answer
21 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 \...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
47 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 ...
Dave's user avatar
  • 23
1 vote
1 answer
22 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 ...
notaorb's user avatar
  • 111
1 vote
1 answer
51 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$...
Josh's user avatar
  • 11
1 vote
1 answer
63 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 ...
Dave's user avatar
  • 23
2 votes
1 answer
52 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, ...
foo's user avatar
  • 121
2 votes
1 answer
74 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. ...
nepee's user avatar
  • 280
1 vote
2 answers
95 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 $...
FUZxxl's user avatar
  • 876
0 votes
1 answer
46 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 ...
matteo_c's user avatar
  • 133
0 votes
1 answer
63 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 ...
enerneo's user avatar
  • 13
0 votes
1 answer
135 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 ...
User42's user avatar
  • 1
0 votes
0 answers
32 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 ...
user159841's user avatar
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 ...
P. Sherman's user avatar
3 votes
0 answers
141 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 ...
in_question's user avatar
0 votes
1 answer
50 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 ...
User42's user avatar
  • 1
3 votes
0 answers
80 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 ...
Minop's user avatar
  • 131
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 ...
Parm's user avatar
  • 1
1 vote
1 answer
25 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 ...
NooneAtAll3's user avatar
0 votes
0 answers
45 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 ...
Karsten's user avatar
  • 101
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 ...
Wasabi Kurosawa's user avatar
2 votes
1 answer
66 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 ...
J. Schmidt's user avatar
0 votes
5 answers
628 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 ...
Gabe Ebag's user avatar
0 votes
3 answers
89 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_{...
2080's user avatar
  • 191
1 vote
1 answer
60 views

Binary subsets for a given set

Lets take an example of the range of N=32 bits ...
Dave's user avatar
  • 23
4 votes
0 answers
67 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, ...
Daniel M.'s user avatar
  • 141
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 ...
Carlo Moretti's user avatar
-4 votes
2 answers
57 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 ...
Max's user avatar
  • 1
1 vote
1 answer
37 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 \...
3nondatur's user avatar
  • 457
0 votes
1 answer
72 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 ...
Lucas Johnston's user avatar
1 vote
1 answer
65 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 ...
A. Boy's user avatar
  • 11
0 votes
1 answer
31 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 ...
Mantas Kandratavičius's user avatar
0 votes
1 answer
233 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 ...
MohG's user avatar
  • 3
0 votes
1 answer
25 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. ...
rapt's user avatar
  • 113
0 votes
1 answer
73 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 ...
newlogic's user avatar
  • 165
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)$ ...
Minh Đức Hoàng's user avatar
0 votes
2 answers
71 views

Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?

I get that the argument for this set $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. ...
linuxxx's user avatar
0 votes
1 answer
316 views

Does order of elements in a set matter in Dijkstra's Algorithm?

When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
Rasmus IN's user avatar
2 votes
0 answers
44 views

Lowest total cardinality mutually exclusive construction of a superset

Let there be $N$ sequences containing at least one set each. Each set has at least one element each. Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
Reinderien's user avatar
2 votes
1 answer
224 views

Efficient algorithm to count number of intersections of n sets

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets. Example: Set a = [...
 snow's user avatar
  • 23
2 votes
2 answers
217 views

Dictionary with sets as keys where lookup can be set intersection

Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic ...
mathlete42's user avatar
1 vote
1 answer
59 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 ...
cubiii's user avatar
  • 113
1 vote
1 answer
127 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 ...
galinette's 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 (...
copumpkin's user avatar
  • 101
0 votes
1 answer
49 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 ...
Mish's user avatar
  • 5
0 votes
0 answers
33 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 ...
felifreee's user avatar
6 votes
0 answers
42 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 $\{...
user avatar
2 votes
1 answer
28 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 ...
DrownedSuccess's user avatar
3 votes
1 answer
72 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", ...
adamcatto's user avatar
  • 131
1 vote
0 answers
55 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 ...
NiRvanA's user avatar
  • 159

1
2 3 4 5
9