52 questions
0
votes
2
answers
216
views
What is a faster way to find all unique partitions of an integer and their weights?
I have seen loads of posts on this topic, but none are exactly what I am looking for.
I want to find all ways a positive integer N that is greater than 1 can be expressed as the sum of at most N ...
- 3,930
0
votes
2
answers
303
views
How to generate random numbers that roughly follow a normal distribution that also add up to a specific total?
I'm trying to generate a random set of numbers that add up to a specific total, and a specific maximum value that the numbers can reach.
However each approach I seem to have come across have some flaw ...
- 29
3
votes
2
answers
79
views
Nested partitions of integers
I want to create all nested partitions of an integer - with all possible permutations of numbers and brackets (nests) at all possible positions.
For example, for n = 3, I would like to have
(3,)
(1, 2)...
- 465
2
votes
1
answer
148
views
Check if a set of numbers can be produced by continuously halving a single starting number
Given a set of numbers, I want to check if it is possible to produce the full set of numbers by repeatedly splitting one single starting number into its halves and doing the same for each of the ...
- 61
1
vote
2
answers
214
views
Uniformly randomly generate a vector of k unsigned ints that sums to N
Another phrasing is: randomly partition N identical items into k buckets, allowing some buckets to be empty.
For this discussion:
an "integer partition of N", to match the usual definition ...
- 329
0
votes
0
answers
416
views
Airflow BigQueryInsertJobOperator: how to create partitioned table?
I have a simple DAG, where I am calling BigQueryInsertJobOperator Is there any way to create a partitioned table?
article= BigQueryInsertJobOperator(
task_id="article",
...
- 149
1
vote
1
answer
299
views
Number of integer partitioning into exactly k parts (calculating for large integer )
Following this thread python-integer-partitioning-with-given-k-partitions
I want to find the number of such partitions (where the minimum part is equal to 1), but the following solution (in the thread ...
- 119
4
votes
3
answers
212
views
Rank of Partition with specific length
How can I determine the rank/index of a partition of integer n with length k?
For instance, if n=10 and k=3, the possible partitions (sorted in reverse lexicographic order) are:
0 (8, 1, 1)
1 (7, 2, 1)...
- 552
0
votes
1
answer
141
views
Integer partition N into M parts in parallel
I am trying to randomly generate integer partitions (N into M parts) in pytorch with a minimum partition size of 1.
For example, (3, 1, 1) and (4, 1, 0) are both partitions of 5 into 3 parts but (4, 1,...
- 3,705
1
vote
0
answers
177
views
Partitioning algorithm for a list of lists in Python
I'm working on a music related problem and I need some help with a crucial step.
I have four lists of numbers from 0 to 11 (including). These lists are to be thought of as vertically aligned. I want ...
1
vote
1
answer
134
views
Randomly sampling integer partitions (without restriction on number of parts)
I have an integer N and I wish to generate one of its possible partitions uniformly at random. For example, N=5 has 7 partitions:
(5) - K=1 part
(4, 1) - K=2 parts
(3, 2) - K=2 parts
(3, 1, 1) - K=3 ...
- 11
1
vote
0
answers
91
views
Turning a Python generator into a C function
I am trying to translate a Python generator into a function in C. If it's worth mentioning, I'm trying to write a program that partitions an integer n, into l distinct parts. I believe that I've got ...
- 674
4
votes
3
answers
843
views
Optimize: Restricted integer partioning with max value
with the following code, I count the restricted integer partitions(each number can only occure once in each partition) with k numbers in each partition, each number is equal or greater than 1 and not ...
- 608
2
votes
2
answers
790
views
Count integer partions with k parts, each below some threshold m
I want to count the number of ways we can partition the number n, into k distinct parts where each part is not larger than m.
For k := 2 i have following algorithm:
public int calcIntegerPartition(int ...
- 608
1
vote
2
answers
532
views
Algorithm to find some rows from a matrix, whose sum is equal to a given row
For example, here is a matrix:
[1, 0, 0, 0],
[1, 1, 0, 0],
[1, 0, 1, 0],
[1, 1, 1, 0],
[1, 1, 1, 1],
I want to find some rows, whose sum is equal to [4, 3, 2, 1].
The expected answer is rows: {0,1,3,...
- 1,896
2
votes
2
answers
872
views
Distinct partitions of an integer excluding repetitious combinations
I found this code online somewhere and I'm trying to make sense of how it works. You supply the partitions() function with an integer and the code returns the number of distinct partitions that do NOT ...
- 69
1
vote
0
answers
621
views
Number of ways to get sum of number(Integer Partition) using recursion or other methods
Question from codewars https://www.codewars.com/kata/52ec24228a515e620b0005ef/python
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a ...
- 85
0
votes
0
answers
54
views
How are recursive partition numbers found step by step on the program?
The "recursive partition numbers" code written using GAP 4.10.2 are as follows.
For example, could you explain the working steps of the GAP programming for nrparts(15)? How did we get ...
0
votes
1
answer
208
views
How to improve integer partitioning with n,m,k?
My program counts the integer partitions of n, which have k distinct partition elements, each is smaller or equal to m. How can I improve the performance? I already cache intermediate results.
public ...
- 608
0
votes
1
answer
278
views
Count subsets consisting strictly k elements
I want to count the subsets of a with k subset elements which sum to n. The possible subset elements are defined through a given array a with distinct positive elements. Possible subset elements can ...
- 608
1
vote
1
answer
218
views
Count integer partitions with k parts when partition elements given
I want to count the integer partitions of n with k partition elements. The possible partition elements are defined through a given vector v with distinct elements. Partition elements can be choosen ...
- 608
0
votes
1
answer
2k
views
BigQuery: How to create integer partitioned table via DML?
I try to understand how the integer partitioned tables work. So far however, I could not create one.
What is wrong with this query:
#standardSQL
CREATE or Replace TABLE temp.test_int_partition
...
- 1,063
2
votes
1
answer
2k
views
Generate restricted weak integer compositions (or partitions) of an integer n into k parts in Python
(Re-posting, as I did not get any response to my previous post)
I am trying to write a Python code to generate weak integer compositions (partitions) of a number 'n' into 'k' parts but with a MINIMUM ...
- 77
2
votes
1
answer
611
views
Finding A List of All Combinations of 6 Numbers That Add up to 10
So I've seen similar versions of this question asked before (Getting all combinations which sum up to 100 using R) but I'm struggling to find a way to figure out what I need to run specifically. I'm ...
- 23
1
vote
1
answer
99
views
Reconstruct bitsequence from a Set of properties
I want to reconstruct a Bitsequence from given Sets of ones, the number x and other properties. In the bitsequence the first bit has the value 1, second the value 2, the third is 3. etc.
For example ...
- 608
2
votes
1
answer
559
views
Rank and unrank integer partition with k parts
For positive integers n and k, let a "k-partition of n" be a sorted list of k distinct positive integers that add up to n, and let the "rank" of a given k-partition of n be its position in the sorted ...
- 608
1
vote
1
answer
228
views
How to index doubly restricted integer partitions?
When enumerating all partitions of a positive integer with the following 2 restrictions:
the size of each partition is always PartitionSize
all elements of these partitions are less than or equal to ...
- 2,420
0
votes
2
answers
426
views
Python and Number Theory: How can we create the generating function for q(n) (the number of partitions of n into distinct parts)?
From https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_partitions, we know that the number of partitions of an integer p(n) is given by
Can be written in python as:
def ...
- 175
0
votes
2
answers
142
views
Fastest way for the computer to find combinations of non-negative integers x_1<=x_2<=...<= x_n and sum to 100
I want to find an efficient way for computer to handle LARGE NUMBER OF VARIABLES (say 50: x1, ... , x50) that do something like this:
find ALL combinations [x1,x2,x3]
satisfying:
0 <= x1 <= x2 &...
- 587
0
votes
0
answers
182
views
How to convert to a Definite Clause Grammar
I'm trying to write a definite clause grammar that outputs the partitions of a number. For example ?- w(3,L,[]) should output :
[1,1,1]
[2,1]
[1,2]
[3]
My code looks as follows:
w(PosNumber) --> {...
- 15
1
vote
0
answers
493
views
Restricted integer partitions in Python
I want to find out how many ways there are to make 500 using only 1, 2, 5, 10, 20, 50, 100, and 200.
I understand that there exist greedy algorithms etc that can solve this type of question, but I ...
- 69
3
votes
1
answer
3k
views
variable number of dependent nested loops
Given two integers n and d, I would like to construct a list of all nonnegative tuples of length d that sum up to n, including all permutations. This is similar to the integer partitioning problem, ...
- 59.6k
0
votes
1
answer
1k
views
Integer partitioning in Java
I'm trying to implement a program that returns the number of existing partitions of an integer n as part of an assignment. I wrote the code below, but it returns the wrong number (Partitions n returns ...
- 25
-1
votes
2
answers
867
views
Divide an integer evenly with a maximum [closed]
I need an algorithm for the following:
I'm given a specified target sum n, and a specified limit m. These are both positive integers.
I want to find an integer partition of the target sum n that has ...
- 23
3
votes
1
answer
510
views
Unique permutations of fixed length integer partitions where each element has a maximum
This question is similar to a question I had several months ago: Generating a numpy array with all combinations of numbers that sum to less than a given number.
In that question, I wanted to generate ...
- 1,565
1
vote
1
answer
933
views
Number of Integer Composition with the number which is in a specific list
Each positive integer n has 2^(n−1) distinct compositions. what If I want the number of composition which is only have specific number which is in my list:
for example composition of 4 is
4
3 1
1 3
...
- 157
5
votes
3
answers
1k
views
All possible permutations of decimal numbers (hundredths) that sum up to 1 for a given length
Consider vector s as follows:
s=seq(0.01, 0.99, 0.01)
> s
[1] 0.01 0.02 0.03 0.04 0.05 0.06 0.07
0.08 0.09 .......... 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99
Now given s and a ...
- 13k
0
votes
1
answer
424
views
Integer partition iterative code optimization
I have been working on code to iteratively partition integers and use previous results to fully partition the numbers, with the idea that using previous partitions can increase speed. So far, I have ...
0
votes
1
answer
7k
views
Return value for recursive function with two arguments
Considering the following code for Integer Partition:
int p (int n, int m)
{
if (n == m)
return 1 + p(n, m - 1);
if (m == 0 || n < 0)
return 0;
if (n == 0 || m == 1)
...
- 135
15
votes
6
answers
7k
views
Is there an efficient algorithm for integer partitioning with restricted number of parts?
I have to create a method that takes two integers, let them be n and m, and returns how many ways there are to sum m positive numbers to get n.
For example, a method call like this partition(6, 2) ...
- 245
0
votes
1
answer
352
views
Algorithm to find the number of ways a number can be written as a sum of two or more positive numbers
It's a homework question and has to be solved using Dyanmic Programming approach.
What I've managed to do so far is that:
Let f(x) denote the number of times x can be written:
Then f(x) = f(x - 1) +...
- 131
0
votes
1
answer
2k
views
Get n in exact k parts. Recursion and partition algorithm. p(n,k)
I'm looking to enumerate all the partitions of n in k parts.
So for p(5,3) i'd get 2 partitions of k = 3 => (3,1,1), (2,2,1).
Here's what I found from searching and looking through stackoverflow :
...
- 374
1
vote
1
answer
344
views
Combining permutation groups
I am developing a probability analysis program for a board game. As part of an algorithm* I need to calculate the possible permutations of partitions of a number (plus some padding), such that all ...
- 11
1
vote
1
answer
133
views
Different ways to calculate number
I need to write a function that will return the number of ways in which can be n (n is a natural number) written as the sum of natural numbers.
For example: 4 can be written as 1+1+1+1, 1+1+2, 2+2, 3+...
- 75
10
votes
3
answers
576
views
conjugate integer partitions in place
I'm building a C++ library that includes a Partitions class. I'm trying to implement conjugation (explained below) in place, and I cannot get it to work.
My class members are:
size_t _size;
size_t ...
- 48.4k
0
votes
2
answers
903
views
Recursive method for the integer partition algorithm
I need to find one of the possible partitions of a number (N) by the number of elements (M) involved, like this:
Number 4
Partitions
4
3 1
2 2
2 1 1
1 3
1 1 1 1
I need to create a function P(N, M), ...
- 8,187
5
votes
4
answers
4k
views
Partition of an Integer + Number of partitions
A partition of an integer n is a way of writing n as a sum of positive integers. For example, for n=7, a partition is 1+1+5.
I need a program that finds all the partitions of an integer n using r ...
- 119
9
votes
2
answers
2k
views
Find the lexicographic order of an integer partition
For permutations, given N and k, I have a function that finds the kth permutation of N in lexicographic order. Also, given a permutation perm, I have a function that finds the lexicographic index of ...
- 944
6
votes
2
answers
969
views
Generating integer partition by its number
I'm trying to generate decent partition of given integer number N numbered K in lexicographical order, e.g. for N = 5, K = 3 we got:
5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + ...
- 61
25
votes
4
answers
16k
views
Python Integer Partitioning with given k partitions
I'm trying to find or develop Integer Partitioning code for Python.
FYI, Integer Partitioning is representing a given integer n as a sum of integers smaller than n. For example, an integer 5 can be ...
user2211319