Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [sets]

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

278 questions
Filter by
Sorted by
Tagged with
80 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: ...
54 views

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\}... 0answers 60 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.: $$\... 1answer 96 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,... 1answer 88 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; ... 0answers 41 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 ... 1answer 46 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 ... 2answers 1k 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. ... 1answer 29 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 ... 1answer 148 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 ... 1answer 138 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 ... 4answers 1k 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 ... 4answers 3k 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 ... 1answer 109 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 ... 1answer 110 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 ... 1answer 173 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 ... 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 ... 1answer 63 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. ... 1answer 20 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 ... 0answers 76 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 ... 1answer 59 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 ... 1answer 23 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, ... 1answer 328 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 ... 1answer 22 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 ... 0answers 65 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 ... 0answers 125 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 can read, write and compare them in O(1) time with arbitrary positions). What's known ... 2answers 882 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 ... 1answer 32 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 \... 2answers 67 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 ... 1answer 337 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 \... 1answer 25 views Evaluating correctness of various definitions countable sets [closed] I was trying to understand the definition of countable set (again!!!). Wikipedia has a very great explanation: A set S is countable if there exists an \color{red}{\text{injective}} function ... 1answer 45 views Algorithm to find most efficent partitioning of a set Given a set S with a finite number of elements, where each s_i\in S is itself a set with a finite number of elements, how do you partition S using as few partitions as possible, such that all ... 1answer 37 views an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S)) I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with ... 2answers 56 views Space efficient data structure for subsets of [1:n] Let S= \{1,2,3...,n\} be a set and I want to store a subset of A \subseteq S. Is there exists any data structure such that insert(x), delete (x) can be done in amortised O(1) time and search(... 1answer 44 views Checking if the mimimum is unique We have a finite poset and its subset S. We can enumerate elements of S using an iterator. I need to check if there are more than one minimal elements of S (regarding the above poset). The ... 1answer 121 views Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria Given a collection of sets S_i of disjoint subsets sub_i of a set X, find a set A of disjoint subsets asub such that each one of these subsets is subset or equal to at most one subset in ... 1answer 37 views What algorithm could I use to find the largest set of disjoint members from a set of subsets of a set? I've written a political quiz based on data from the public whip. They group politicians' votes by policy; each vote can belong to many policies. There are too many policies for me to ask a question ... 1answer 77 views Is this problem NP-complete? Let there be a set of cardinality n\in \mathbb{N}. Let there also be n subsets of that set. What is the smallest k such that union of some n-k of those subsets is of cardinality at most k? The ... 1answer 113 views Introduction to type theory for a beginner? I'm interested to read about type theory, but I'm quite a beginner. I know what sets are and how to work with them, but I don't have a deep understanding of set theory. I don't really understand the ... 0answers 292 views hash-table subsets Having trouble figuring this out. If I have 2 sets of integers how would I use a hash table to test if set A is a subset of set B (in pseudocode). I think I understand that basically I would need to ... 1answer 37 views Compute the union of two sets between two endpoints minimizing communication complexity I have two endpoints, a and b, that can communicate through a channel. a is storing a set of fixed-length strings A = \{a_1, \ldots, a_{N_A}\}, and b is storing another set of fixed-length ... 0answers 89 views Minimum overlap partitioning We are given N sets of M non-unique elements each. The amount of overlap (computed as the element count in the set intersection) between the elements of these sets is stored in a N \times N ... 6answers 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 ... 1answer 119 views Compact mapping from an involuted set Let S be a set (say positive integers \leq N) and f an involution (f is bijective, f\cdot f=id, e.g. xor with a constant). g is a idempotent mapping choosing an arbitrary representative ... 1answer 52 views Algorithm to determine a set given the size of its intersection with sets you choose I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, U, and a hidden target T \subset U. I submit S \subset U, ... 1answer 90 views Looking for a succinct dynamic sorted dictionary I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset S of a universe U = \{0, \ldots, u\} with member/... 1answer 57 views How is it possible that L_1 is NP? The question is from my complexity-theory course. The question If L_1,L_2,L_3 \in \lbrace 0,1 \rbrace^*, and different from \lbrace 0,1 \rbrace^* and from the empty language, prove that if L_1 \... 2answers 55 views Are typical sets larger, when information is messier? Let 0\le q<p\le \frac{1}{2}, and let P,Q be two Bernoulli Random Variables such that:$$Pr[P=1]=p ; Pr[P=0]=1-p$$and$$Pr[Q=1]=q ; Pr[Q=0]=1-q$$My question: Does it follow that, for any$\...
Let $m, n \in \mathbb{N}$ and $n \le m$. Given $k$ subsets $X_1, X_2, \dots, X_k$ of $\{ 1, 2, \dots, m \}$ and $k$ nonnegative integers $a_1, a_2, \dots, a_k$, find all subsets $Y$ of \$\{ 1, 2, \dots,...