Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
30 views

Optimally find one of the total orderings for a poset based on some metadata about the elements

Given a finite, partially ordered set with the following two properties: Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
2
votes
1answer
19 views

Uniquely identifying bits

Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them? Is this problem NP-Hard? For example, given the $4$ unique ...
0
votes
1answer
27 views

Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

hope you all are doing well. I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien....
2
votes
1answer
20 views

Maximizing integer sets intersection (with integer delta)

There are two sets of integers with different numbers of items in them. ...
0
votes
0answers
18 views

Benefits of linked lists over forests for disjoint sets

CLRS discusses two specific data structures for disjoint sets: Single linked lists, where each set is represented by a single linked list, and each node has two pointers, one to the list head and ...
1
vote
1answer
26 views

Efficiently finding the intersections of sets that yield a desired set

Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as ...
2
votes
1answer
46 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 information it ...
2
votes
1answer
28 views

Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?

Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong. I have a puzzle: ...
2
votes
1answer
23 views

Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality. Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
1
vote
0answers
21 views

Algorithm for finding the set of systems of distinct representatives

Given a collection of finite sets, is there an algorithm for finding the set (unordered) of all systems of distinct representatives for the collection? Example: S: {{1, 2}, {1, 2, 3}} Unordered ...
3
votes
1answer
67 views

Smallest set of balls under hamming distance that covers all $n$-bit strings

Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that, $$S_{y_i} = \{y \in S\...
1
vote
1answer
44 views

Is the powerset of a regular set also a regular set?

If so, where can I find a proof of it? If not, is there a counterexample? By powerset of a regular language I mean the set of all subsets of a regular language. Thank you, Marcus.
3
votes
1answer
234 views

How to get an element from an existential proposition in Type theory proof assistant (Lean prover)

I am trying to implement set theory in type theory from scratch, just for self pedagogical purposes. Specifically, I'm using the Lean Prover, and defining the element-of relation from scratch using ...
1
vote
1answer
48 views

Generate all combinations of a set/array with specific conditions

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions: ...
0
votes
0answers
20 views

Minimum pair-wise XOR of elements from two sets

I have two sets, $A$ and $B$, which both contain a large amount of hashed values. What is the most efficient way of computing: $$\min_{i,j} A_i \otimes B_j$$
1
vote
1answer
51 views

Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals

Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line. Suppose we have four integer numbers, A, B, C and D. For example: ...
0
votes
0answers
32 views

Data structure for overlapping sets

Is there a good data structure for storing overlapping sets? Consider having multiple sets which can overlap in various ways and would like to store them in the memory and access efficient way. ...
0
votes
1answer
113 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
0
votes
1answer
25 views

Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2?

Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes of 1 and 2? I can't really see the equivalence classes of infinite sets. Only by having a ...
0
votes
1answer
43 views

Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

Given a set of positive integers : $ \\ D = \{ D_1, D_2, ..., D_n\}$ and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
1
vote
1answer
50 views

Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?

I have 2 large sets of strings (actually they are product names). "Large" means few millions of strings. Example: Set 1: ...
1
vote
1answer
50 views

How to speed up finding a subset of a given set?

Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data? For example, let's say that I have a collection of sets: ...
1
vote
1answer
20 views

Algorithm to compute decomposition of a union of sets to a disjoint union of intersections

A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets. This clearly generalizes. If ...
1
vote
0answers
26 views

What is the maths name for a set which contains the Domain and Codomain of a function? [closed]

Im interested in this so that I can name a type parameter in a program I'm writing. There is function that that has three parameters. D, Domain C, Codomain X, where D is a subset of X and C is a ...
2
votes
1answer
29 views

Demonstrating that probability for every possible result is uniform at the end of an algorithm

I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At ...
2
votes
1answer
108 views

How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

I am struggling to answer the following question: How many different languages over the unary alphabet {a} are recognized by 2-state DFAs? According to the textbook, the hint was to first ...
0
votes
0answers
54 views

How to maximize $f$ while minimizing $g$ at the same time?

Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly. The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
0
votes
0answers
46 views

Why is A(B ∩ C) ≠ AB ∩ AC? [duplicate]

I am told A(B ∩ C) ≠ AB ∩ AC I am unsure as to why they are not equal. Using examples and following them I am unable to show that they are not. e.g Let A = {m} B = {s, p} C = {p, r} A(B ∩ C) = A{p} =...
0
votes
2answers
97 views

How is the set of functions from ${\{a,b\}}$ to $N$ countable?

Assume a set of functions from ${\{a,b\}}$ to $N$ Where $N$ is the set of Natural numbers. Let us assume that the size of $N$ is $n$. i.e $|N|=n$ The first element $a$ have $n$ choices for mapping....
3
votes
1answer
49 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
1
vote
1answer
51 views

Given a set of sets, what is the largest common intersection between them?

Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to ...
1
vote
1answer
46 views

Largest number of unique values in sets

Let's say I have 100 sets of values, and each set contains roughly 100,000 values. From these sets, I want to find the 10 sets that collectively have the largest number of unique values. The brute ...
2
votes
1answer
135 views

Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

I came across following facts: Set of finite languages over a finite alphabet is countable. Set of languages over finite alphabet is uncountable. I believe proof of this will be similar to ...
3
votes
1answer
50 views

Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
2
votes
1answer
22 views

How to find number of combinations of choosing one from k subsets

Consider we have set S: S = {1,2,3,4,5,6} and 3 (say k) subsets of S: S_1 = {1,2,3} S_2 = {2,3,4,5} S_3 = {1,3,6} What is the total number of cases choosing one element from each subsets? Same ...
2
votes
1answer
37 views

largest bitwise-or subset with a maximum number of on bits?

Suppose I have the following set of bit sets: ...
2
votes
1answer
161 views

Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
3
votes
1answer
32 views

A problem on sets

Given a collection C of sets, with union U, find a choice function which chooses a distinct element from each of the sets such that the union of the singleton distinct elements is U. As an example, ...
2
votes
1answer
43 views

Efficient data structure for matching 3D lines

I'd like to Store a set of many infinite undirected 3D lines. Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?" The incidence-...
2
votes
0answers
77 views

Set of maximum overlaps

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap. I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
0
votes
2answers
52 views

How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
1
vote
1answer
71 views

How can $A \cup B$ be decidable if $B$ is undecidable?

My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
3
votes
1answer
46 views

Proof of sparsification lemma: What exactly does the $\pi$ operator do?

In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$: For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family ...
0
votes
1answer
48 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
3
votes
1answer
83 views

Lambda Calculus as a branch of set theory

This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about: The functional paradigm, for example, was developed mathematically (...
0
votes
0answers
25 views

For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of ...
2
votes
1answer
116 views

Suggest a Data Structure To Manage 2 Sets

I was given the following problem which really baffled me, and I would like some guidance in solving it. I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I ...
3
votes
1answer
82 views

Fast hash function for set equality

I'm searching an hash function for integer set equality that must be fast. It must support update (adding an element already in the set must not change the hash) and union. MinHash has these 2 ...
1
vote
1answer
185 views

Finding longest subset arithmetic progression with given difference

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D. For example, given D = 5, with the set of numbers 1, 5, ...
0
votes
1answer
61 views

How do you compute the Pareto Front of a set?

I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst ...

1
2 3 4 5
7