Questions tagged [sets]
Questions about finite and infinite sets and multisets, related data structures and concepts.
2
votes
3answers
102 views
N subsets with a given sum?
How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?
¹⁾ Not as in $P$, I just want something smarter than $O(n^...
1
vote
0answers
39 views
Find a partition of multiset of binomial coefficients with constriants
Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $
0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
1
vote
1answer
37 views
Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?
Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.
We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
2
votes
1answer
37 views
Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:
$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$
$A_i$ ...
3
votes
2answers
46 views
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$
I recently thought of the following problem:
Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.
For ...
1
vote
2answers
42 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
24 views
Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?
Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
2
votes
1answer
31 views
Minimal set of subintervals that 'covers' any subinterval in K subintervals
I have a big interval $I = [a, b]$ of size n.
I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
2
votes
0answers
28 views
Algorithm / data structure to filter documents by number of missing words
Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?
Problem Definition
We ...
2
votes
1answer
35 views
Parser theory: How to systematically compute FOLLOW sets?
Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
1
vote
1answer
37 views
PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?
In Practical Foundations for Programming
Languages, on page 138 (page 156 of the pdf), it says:
Requiring solutions to all type equations may seem suspicious, because
we know by Cantor’s Theorem ...
0
votes
1answer
36 views
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).
I know that ...
1
vote
0answers
22 views
Algorithm for Minimum Subset Needed to Satisfy all Constraints
I was wondering what is the most efficient algorithm to solve something like the following:
You have $P$ people.
You have $T$ tasks, each of which is a set of sets that represent all of the possible ...
-1
votes
0answers
47 views
Finding all subsets of a set
I have a set, and i want to find all its subsets. what is the best time complexity to find it?
What is the most efficient algorithm to find all subsets of a set?
3
votes
0answers
267 views
Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family
I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family
Concretely:
For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j ...
2
votes
1answer
40 views
What is the algorithm for a decider to get the language accepted by a DFA?
I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
1
vote
1answer
43 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
2
votes
2answers
205 views
Prove: Every decidable set is Turing reducible to the empty set
Question-
Prove: Every decidable set is Turing reducible to the empty set.
Can anyone help me with this please?
All reductions tutorials I've seen use practical examples of reduction such as sipser'...
0
votes
1answer
66 views
Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
The Problem:
I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:
...
1
vote
1answer
46 views
For each given set choosing either it or its complement such that their union exactly has a given size
Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
1
vote
0answers
27 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
65 views
Find 2 sets with an empty intersection
I have the following problem. The problem can be formulated in three different ways
Given sets $B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$.
Find $i,j \in \{-n,\ldots,n\}$ with $|i| \neq |j|$ and $i,...
0
votes
1answer
24 views
What is the optimal algorithm for finding all sets of overlapping ranges?
I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; ...
2
votes
0answers
38 views
Abstract Data Type
I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
1
vote
1answer
43 views
number of random sets needed to generate subset
Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.
How many $...
0
votes
2answers
388 views
Given n numbers How to find out a set of numbers whose sum equal to a certain given number
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.
...
0
votes
0answers
17 views
What does it mean for a set to be NP-complete? [duplicate]
For homework I have the task
Assuming P ≠ NP, is the following set NP-complete:
{(G,w) | G is a Graph and w is a Hamilton cycle in G}
and I don't understand how to show that a set is NP-complete.
I ...
1
vote
1answer
25 views
complexity of outputting the union of a collection of subsets of a set
This question concerns the time complexity of outputting the unions of subsets of a given set.
Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with ...
1
vote
1answer
82 views
Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$
I have the following problem:
Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array ...
2
votes
1answer
114 views
Find the sum of the first K subsets of integer array
We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ ...
0
votes
0answers
23 views
Lower Bound Space complexity one pass algorithm / Heavy-Hitters Problem
I am confronted with the following problem:
Let S be the family of all m-subsets of $[n] = [2m]$
let $S_1, S_2 \in S$ be distinct sets and let the state of storage be $State_1$ after stream $S_1$ is ...
9
votes
4answers
647 views
What exactly is the semantic difference between category and set?
In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of ...
28
votes
4answers
2k views
What exactly is the semantic difference between set and type?
EDIT: I've now asked a similar question about the difference between categories and sets.
Every time I read about type theory (which admittedly is rather informal), I can't really understand how it ...
5
votes
1answer
100 views
Is there a formal difference between $f:X \to X$ and $f\in X \to X$?
We can denote by $X\to X$ the set of all functions from $X$ to $X$.
Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$:
$$f\in X\to X$$
But we usually state ...
0
votes
1answer
54 views
inclusion and concatenation of languages
so for a homework assignment i need to prove the following:
We have arbitrary languages L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4*
Prove that the followging is either true or ...
4
votes
1answer
79 views
Does this “set intersection” problem have a different name?
I've been back and forth about this one. I have the following theoretical homework problem, which describes the SET-INTERSECTION problem. In my homework, it's ...
5
votes
1answer
54 views
Among a number of sets, how to find the one that includes the highest number of other sets?
I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets.
A ...
1
vote
1answer
62 views
Determining possible data structures given a set of required operations
This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs.
You have a collection of comparable objects and want to be able to do the following:
1. ...
-1
votes
1answer
16 views
Count points on same distance from set of points
Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
0
votes
0answers
34 views
Pruning a powerset based on a graph
I have a list of nodes l = [1, 2, 3, ... , n] and a list of tuples p = [(1, 2), (2, 3), ...], where the latter represents which ...
1
vote
1answer
41 views
Data-structure for dynamic disjoint-sets
I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).
This is just a simple (javascript) array ...
0
votes
1answer
21 views
How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?
Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings.
Let $B$ denote a set of sets such that each subset contains a (relatively small, ...
0
votes
1answer
195 views
How to read off the set represented by a van-Emde-Boas tree?
I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
0
votes
1answer
17 views
In two sets, identify set of pairs with maximal sum of connections
Given two sets of items
$A = { a_1, .., a_N }, B = { b_1, .., b_M },$
and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how ...
4
votes
0answers
50 views
effective, efficient algorithms on antichains
In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable.
Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such ...
2
votes
0answers
76 views
What is the deterministic time complexity of obtaining the set of distinct elements?
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we have can read, write and compare them in O(1) time with arbitrary positions). What's ...
7
votes
2answers
786 views
Is the intersection of infinitely many recursive sets recursive?
Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable?
I know the union need not be recursive, because deciding if ...
1
vote
1answer
31 views
Intersection of two independent sets
I am trying to make sure my intuition for the following question from an assignment is correct
Prove or disrove: if $G = (V, E)$ is a graph and $I_1$ and $I_2$ are independent sets in $G$, then $I_1 \...
4
votes
2answers
63 views
Finding the number of ways to partition $\{1,…,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$
I am trying to think of how to optimize the following problem:
Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
1
vote
1answer
185 views
Reverse cartesian product matching all given rows
I´m looking for an efficient algorithm that will find reverse cartesian products.
Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \...
