# Questions tagged [sets]

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

427 questions
Filter by
Sorted by
Tagged with
12 views

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 ...
1 vote
22 views

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
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$...
1 vote
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 ...
52 views

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 ...
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 ...
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 ...
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 ...
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 ...
141 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
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 ...
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 ...
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 ...
89 views

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 ...
1 vote
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 ...
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 ...
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 ...
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. ...
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 ...
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)$ ...
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. ...
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 ...
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....
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 = [...
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 ...
1 vote
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 ...
1 vote
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 ...
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 (...
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 ...
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 ...