# Questions tagged [partitions]

A partition or partitioning of a set A is a collection of disjoint sets whose union yields A.

143 questions
Filter by
Sorted by
Tagged with
167 views

### Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
1k views

118 views

### How to generate an instance for an NP_hard proof, where each element has two inputs?

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
66 views

### finding separating words (Nerode)

i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
907 views

### Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different. Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
353 views

### Complexity of a set partition derived problem

I am stuck at the complexity of the following problem: Given a multiset $S = \{x_1,..., x_n\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S_1,... S_j$ such that ...
97 views

### Karp hardness of directed monochromatic triangle problem

Monochromatic problem is a classic NP-complete problem. Does the complexity stay NP-complete if we use directed graph? DIRECTED MONOCHROMATIC TRIANGLE problem: Input: A digraph $G(V,A)$ Output: YES ...
185 views

### Is this an $NP$-complete problem: Product-2-Partition

I want to prove the NP-hardness of some problem P in scheduling theory. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say ...
223 views

### Can interval partition solve by sort by different approach

The interval partitioning problem is described as follows: Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of ...
72 views

### Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given: R = Red W = White B = Blue I have this unpartitioned array. ...
983 views

### Divide an array into two sub arrays such that their sums are equal and possibly maximum

Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays. For example, ...
81 views

### Proving that an equal partition does not exist

We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum. To prove that an equal partition exists, it is sufficient to show a partition. What is ...
1k views

### k-way set partition problem--dynamic programming solution

I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem Among other things, they present a DP approach to solving the equal subset ...
50 views

Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that $x_1a_1 + x_2a_2 + ... + x_na_n = 0$, $x_i$ $\in$ $\{-1,0,1\}... 2answers 611 views ### Question regarding Hoare's partitioning scheme and a slight modification to it This is the pseudocode on wikipedia for Hoare's partitioning scheme: ... 2answers 178 views ### Determine if an array is divisible in pairs of equal sum I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic: Let A be an unordered array of positive natural numbers. Write an ... 0answers 92 views ### Polygon decomposition into minimum star-shaped polygons As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any ... 0answers 673 views ### Even distribution algorithm Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ... 1answer 79 views ### sub-optimal but fast partition generation I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ... 0answers 101 views ### How to enumerate all partitioning of a set to k-subsets of size at most b I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size$n$to$k$non-empty subsets, each with size at most$b$. More specifically, given a set$V$where$...
I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all ...