Questions tagged [sets]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
26 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
3
votes
1answer
49 views

A heuristic for finding the vector that is maximally distant from a set of vectors

I have two sets of vectors: A and B. I want to find the vector Bi in set ...
0
votes
1answer
38 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 ...
13
votes
2answers
943 views

Recover a set with the information of the sums of all its subsets

I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$? I have $2^n $ data. This is ...
0
votes
0answers
16 views

Algorithm for bipartite graph matching decision problem

Suppose I have a list of sets $$ L=\{A_1,A_2,\ldots ,A_n\} $$ And want and algorithm that solves the following decision problem Is it possible to select one element from each set such that no two ...
0
votes
1answer
25 views

Minimum spanning tree where weights of edges are intersecting sets

Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$. Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...
1
vote
2answers
53 views

What is the entropy of an unordered list?

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :) Each integer is 6-digits, so ...
0
votes
1answer
50 views

Tuple relational calculus: existential quantifiers

I have the following question and given answer: Question: List the names of managers who have at least one dependant. Answer: ...
1
vote
1answer
28 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
2
votes
1answer
62 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 ...
4
votes
0answers
74 views

Sequence where every subset exists as some contiguous subsequence

Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
2
votes
1answer
48 views

Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?

I'm looking to formally define a tree and then extract the leaves from it in a concise way. Does this look ok? What is the best way of doing this? $ Y = \{a,b,c,d,e,f,g\} \\ R = \{a \mapsto b, a \...
0
votes
1answer
42 views

Is this way to combine two functions into a new function called a function product?

I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, ...
1
vote
0answers
26 views

Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
2
votes
1answer
43 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 ...
1
vote
1answer
67 views

Algorithm to check Gibbs' Phase Rule

I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first. I have ...
1
vote
0answers
29 views

Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue. The problem is this: I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
0
votes
1answer
64 views

Is the empty string and some words of even length are elements of this set?

$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$. I have my answers, but I need confirmation: Is the empty string $\epsilon \in L$? Yes. Reason: ...
3
votes
1answer
85 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
1answer
73 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 ...
1
vote
1answer
15 views

Complement of $\{w\#x \mid w,x \in \Sigma^*, T(M_w) \neq \{x\}\}$

This is one of my homework assignment questions, that are quite difficult for me. The question states: Show that $L$ is not semi-decidable where $L = \{w\#x \mid w,x \in \Sigma^*, T(M_w)\neq \{x\}\}$ ...
4
votes
0answers
55 views

Combinatorics - how many $c$-distinct sets are possible?

I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here. I am given two ...
0
votes
1answer
16 views

Formal Description Of Data Structure For Infinite Sets Of Reals

The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it ...
1
vote
1answer
13 views

Set notation for ACL matrix

This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
2
votes
3answers
218 views

Set theory pertaining to category theory and functional programming

I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following: A power set of a set is the set of all its subsets. A script 'P' is used ...
1
vote
1answer
62 views

Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$

I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset. The sumset is $$ A + B = \{ a + b : a \in A , b \in B \} $$ and $R$ ...
1
vote
0answers
19 views

Streaming maximum pair matching with limited memory

I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of ...
1
vote
2answers
25 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
2
votes
1answer
52 views

What is the difference between Partition and Division?

While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different? Can anyone explain me their difference in ...
2
votes
0answers
34 views

Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
1
vote
0answers
61 views

Disjoint groups using maximum matching

In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter $k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on ...
1
vote
0answers
34 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
6
votes
1answer
159 views

Shared Elements Algorithm

I have a problem that I am working on an algorithm for: I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets) $S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\...
0
votes
2answers
39 views

Is this the correct answer for the cardinality of this set?

This is a question from a practice quiz at my university. Is the question asking for the cardinality of Σ1 = {a,b} to the power of four? if that's the case, then the set would still have a ...
1
vote
1answer
22 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
1
vote
4answers
462 views

What is the point of (Compactness theorem in the) Overspill principle?

The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states Let $\phi$ be a sentence of predicate logic such that for any natural number $n \geq 1$, there is a model of $\phi$ with ...
1
vote
1answer
36 views

Families of sets indexed by another set

I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets. If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is ...
21
votes
7answers
5k views

in O(n) time: Find greatest element in set where comparison is not transitive

Title states the question. We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal. Key points: Comparison is not transitive (think rock ...
3
votes
1answer
70 views

For two sets of points find if second one is result of linear transformation of the first

Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of ...
2
votes
2answers
33 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{...
0
votes
0answers
17 views

Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions?

I am trying to find an online/offline tool that can compute the following: Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation R = {(a1, a2),(...
2
votes
2answers
92 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
1
vote
1answer
591 views

What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

Background I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.: $$ \...
1
vote
1answer
25 views

Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement)

(originally asked on StackOverflow) Two recent questions on StackOverflow by the same author1 are generally solved by the same technique. This feels to me like it would be a studied and perhaps well-...
2
votes
2answers
1k 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: ...
1
vote
1answer
55 views

Need hint for bipartiteness proof

I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(...
1
vote
1answer
40 views

"The Annotated Turing" on listing all binary numbers between 0 and 1

In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote: These are binary numbers between 0 and 1, and (judging from the way we created these numbers) all ...
0
votes
0answers
55 views

String membership in hash set time complexity

Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
3
votes
1answer
121 views

How to detect "tree-able" set-families?

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
3
votes
0answers
27 views

Components of subset partial order

Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper. But is there any work on algorithms ...

1
2 3 4 5
8