As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [sets]

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

418 questions
Filter by
Sorted by
Tagged with
37 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 ...
60 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 ...
129 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 ...
30 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 ...
25 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 ...
118 views

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 ...
1 vote
49 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 ...
60 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 ...
354 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 ...
63 views

63 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 ...
55 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 ...
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 ...
181 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 ...
22 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. ...
72 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 ...
134 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)$ ...
65 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. ...
209 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 ...
43 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....
140 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 = [...
152 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 ...
1 vote
42 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 ...
1 vote
90 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 ...
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 (...
44 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 ...
31 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 ...
39 views

33 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 ...
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)$ ...