Questions tagged [sets]

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

1
vote
1answer
122 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
128 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
832 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 ...
31
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
104 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
80 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
154 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
18 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
59 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
48 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, ...
0
votes
1answer
287 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
19 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
60 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
97 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
852 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
66 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
280 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
44 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
32 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
51 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
113 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
36 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
76 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
109 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
258 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
34 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
82 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$ ...
21
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
117 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
51 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$, ...
2
votes
1answer
78 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
55 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
53 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
70 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 ...
2
votes
1answer
42 views

An efficient method to compute a minimum set of sets that form the union of these sets?

Let's say we have a set of sets: $$\mathfrak S = \lbrace S_1, S_2, ... , S_n\rbrace$$ And the union of the all the sets in this set: $$\mathfrak U = \bigcup\limits_{i=1}^{n} S_{i}$$ And so there ...
2
votes
1answer
42 views

How can a set of N players be split into M teams, given certain rules?

A lot of times, I’ve needed to split a given set of people into a given number of teams but with some complications, like: Alice and Bob CANNOT be on the same team. Carol and David just HAVE TO BE on ...
3
votes
2answers
253 views

Find non-overlapping subsets that maximize the sum of their values

Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value. Has this ...
6
votes
1answer
55 views

Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
4
votes
2answers
88 views

Datastructure for managing (abstract) sets

I am looking for a datastructure to represent the complex relationships between a bunch of abstract sets. The "abstract" means that these sets are not defined by their elements, but by their ...
2
votes
1answer
30 views

Minimum number of intersections to arrive at specific set

Say I have a large number of sets (on the order of ~1000) with a smaller number of potential entries (~200), and a widely varying number of entries per set. An example: $s_1 = \{1, 42, 133\}$ $s_2 = ...
1
vote
1answer
43 views

Logic, “and” operator between a set of formulas and a formula

Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$...
3
votes
1answer
42 views

Algorithmic complexity of a Maximum Capacity Representatives variant

I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can ...
3
votes
2answers
582 views

Efficient implementation of sets

Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge). I create many arbitrary subsets of U in running time (These sets may be or may not be ...