# Questions tagged [sets]

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

436 questions
Filter by
Sorted by
Tagged with
0 votes
0 answers
47 views

2 votes
1 answer
83 views

### Algorithm to find intersection between collection of sets

I have two dataframes representing products two distributors sell. They look like this: df1 for distributor 1. ...
0 votes
1 answer
22 views

1 vote
2 answers
101 views

0 votes
0 answers
27 views

### Find a set of elements with minimal costs that contains at least one element of given subsets

I have encountered at my work currently a problem where I want to find an efficient algorithm for, although I suspect this might be hard problem. Maybe you can help me to tell if this is a NP hard ...
6 votes
0 answers
1k views

### Time complexity of obtaining the support set of an unsorted sequence?

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 ...
3 votes
0 answers
99 views

### Map-like data structure with subsets as keys

I am looking for a map-like data structure with the following properties: it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime the ...
2 votes
1 answer
92 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 ...
0 votes
0 answers
16 views

### Trying to figure out how to model the structure of a multilingual dictionary for several constructed languages (basically Wiktionary for my conlangs)

Okay, so, this will be quite a bit, sorry. I'm working on several constructed languages for a worldbuilding project. Up until this point, I have been using a spreadsheet to store the vocab; each row ...
2 votes
1 answer
77 views

### What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?

A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This ...
1 vote
1 answer
52 views

### How is the direct product of the functions (A -> B) * (C -> D) equivalent to the function (A * C) -> (B * D)? Is there an error here?

In the simply typed lambda calculus we have type algebra - types can be added, multiplied and exponentiated, where addition corresponds to the sum type, multiplication to the product type, and ...
1 vote
1 answer
27 views

1 vote
1 answer
64 views

### Binary subsets for a given set

Lets take an example of the range of N=32 bits ...
4 votes
0 answers
82 views

### Finding all sets which are not subsets of other sets

I have a set of sets, for example { {1, 2, 3}, {1, 2}, {2}, {2, 4} } I want to find all sets which are not subsets of another set. For example, ...
1 vote
0 answers
21 views

### Randomly Split a Bar Into Beats

So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc. As for now the randomisation works on tones building sequences of equal duration. What I'd like to do is ...
-4 votes
2 answers
61 views

### Let F be a function defined for all nonnegative integers by the following recursive definition

Let F be a function defined for all nonnegative integers by the following recursive definition. F(0) = 0, F(1)= 1 F(n + 2) = 2F(n) + F(n +1), n>0 Compute the first six values of F; that is, write ...
1 vote
1 answer
39 views