Integer partitioning problem - for fun

Also, you can check what the differences between each consecutive term in the list are, as well as the differences between each term and the first term (##x_i-x_0##).In summary, the conversation discusses a system that generates a list of integers based on user input, and then randomly deletes certain rows from the list. The system is not able to remember the original input, and the question arises of how to determine the values of the input from the resulting list. One suggestion is to statistically analyze the differences between consecutive terms in the list and between each term and the first term. However, in general, it is not possible to determine the original input without knowing the values of ##N## and ##M##.
  • #1
Pepper Mint
91
139
I have a user input of 2 integers (m,n)
Then my system will generate 1 list of M (m,n < M) integers that start at m and end at Mth integer of value xM. The formula to calculate xM is followed by
[itex]x_0=m[/itex]
[itex]x_M=x_{M-1}+n[/itex]
After the list is generated I randomly delete N (N << M) rows from it and given that my system isn't allowed to remember (m,n), how can I find out what values (m,n) were ?

For example
(m,n)=(2,5)
M=5 => L={2,7,12,17,22}
deleting L2,4 yields L={2,12,22}
 
Physics news on Phys.org
  • #2
In general case you can't.

I would start checking what all xi-xi-1 (actually every xi-xj) have in common.
 
  • Like
Likes Pepper Mint
  • #3
As Borek says, you can't do this if you don't know ##N## and ##M##. But you can statistically analyze what the ##n## and ##m## values likely might have been.
 
  • Like
Likes Pepper Mint

Related to Integer partitioning problem - for fun

What is the Integer Partitioning Problem?

The Integer Partitioning Problem is a mathematical problem that involves breaking a number into smaller whole numbers that add up to the original number. For example, the integer partition of 5 would be 5 = 4 + 1, 5 = 3 + 2, 5 = 3 + 1 + 1, and so on.

What is the significance of the Integer Partitioning Problem?

The Integer Partitioning Problem has applications in various fields, such as number theory, combinatorics, and computer science. It can also be used to solve other mathematical problems, such as the famous Goldbach's conjecture.

How is the Integer Partitioning Problem solved?

There is no known general formula for solving the Integer Partitioning Problem. However, there are algorithms that can be used to find all possible partitions for a given number. One of the most common algorithms is the recursive algorithm, which breaks down the problem into smaller subproblems.

What is the difference between integer partitioning and integer factorization?

The main difference between integer partitioning and integer factorization is that in integer partitioning, the numbers being added together can be repeated, whereas in integer factorization, the numbers being multiplied must be unique. For example, the integer partition of 6 can include 2 + 2 + 2, whereas the prime factorization of 6 is 2 x 3.

Is the Integer Partitioning Problem NP-complete?

No, the Integer Partitioning Problem is not currently known to be NP-complete. However, it is considered to be a difficult problem, and no efficient algorithm exists for solving it. It is classified as a weakly NP-hard problem, which means that its complexity may depend on the input size and other factors.

Similar threads

Replies
7
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Replies
64
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Atomic and Condensed Matter
Replies
3
Views
1K
  • Programming and Computer Science
Replies
17
Views
1K
  • Electrical Engineering
Replies
4
Views
967
  • Engineering and Comp Sci Homework Help
Replies
21
Views
2K
Replies
1
Views
872
Replies
6
Views
1K
Back
Top