The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
85 views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
-1
votes
1answer
26 views

Algorithm for random generation of two connected partitions of a finite set [closed]

Given the set $X=\{1,2,\ldots,n\}$; $\,\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers. Please help me to programme an algorithm that realizes random generation of the following two partitions of ...
2
votes
1answer
89 views

Finding a specific “balls-into-bins” partition given its index in the lexicographical ordering

Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins. Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in ...
2
votes
1answer
68 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
1
vote
1answer
38 views

Applications in Computer Sciences of Partition Functions

A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$. These were studied ...
2
votes
2answers
45 views

Partition area using test function

I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f ...
3
votes
1answer
35 views

Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
1
vote
1answer
79 views

Permute the subintervals of an interval partition to most closely align with a model partition

You are given two things: A fixed initial 'model' partition of an interval, e.g. I------I---I-----I-------I----... where each ...
0
votes
2answers
309 views

Partition array into K subsets, each with balanced sum

Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that $A'_{1} = \{a_{1}, ...,a_{x}\}$ $A'_{2} = \{a_{x+1},...,a_{y}\}$ ...
5
votes
1answer
209 views

What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly ...
2
votes
1answer
364 views

reducing subset-sum to partition

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis) Partition: Given a list, can it ...
6
votes
0answers
143 views

How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
1
vote
1answer
367 views

Showing a partition-like problem is NP-complete

Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that $|p_{i}|=a_{i}$, and $\sum_{i = 1,}^{n}p_{i} = 0$. This problem is ...
13
votes
0answers
200 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
4
votes
1answer
307 views

Data structure for partition of a set

A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent ...