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.

Filter by
Sorted by
Tagged with
1
vote
1answer
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: ...
1
vote
1answer
54 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
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.: $$ \...
2
votes
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,...
0
votes
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; ...
2
votes
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 ...
1
vote
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 $...
0
votes
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. ...
1
vote
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 ...
1
vote
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 ...
2
votes
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$ ...
10
votes
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 ...
32
votes
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 ...
5
votes
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 ...
0
votes
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 ...
3
votes
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 ...
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
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. ...
-1
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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, ...
2
votes
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 ...
0
votes
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 ...
3
votes
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 ...
2
votes
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 ...
7
votes
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 ...
1
vote
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 \...
4
votes
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 ...
1
vote
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 \...
1
vote
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 $...
0
votes
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 ...
1
vote
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 ...
0
votes
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(...
1
vote
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
5
votes
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 ...
2
votes
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 ...
3
votes
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 ...
2
votes
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$ ...
20
votes
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 ...
3
votes
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 ...
2
votes
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$, ...
3
votes
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/...
0
votes
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 \...
3
votes
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 $\...
1
vote
1answer
101 views

Efficient way to choose set from including conditions on sets

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,...
0
votes
2answers
72 views

Best way to fusion two list of clusters

Imagine the following sets : A = Set( sortedSet(1,2,3), sortedSet(4,8)) B = Set( sortedSet(3,4), sortedSet(5,6,7) ) Where each inner list represent a cluster ...